A hierarchy theorem for regular languages over free bisemigroups

Németh, Zoltán L.: A hierarchy theorem for regular languages over free bisemigroups. In: Acta cybernetica, (16) 4. pp. 567-577. (2004)

Cikk, tanulmány, mű

Download (172kB) | Preview


In this article a question left open in [2] is answered. In particular, we show that it is essential that in the definition of parenthesizing automata an arbitrary number of parentheses can be used. Moreover, we prove that the classes Regm of languages accepted by a parenthesizing automaton with at most m pairs of parentheses form a strict hierarchy. In fact, this hierarchy is proper for all alphabets.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2004
Volume: 16
Number: 4
ISSN: 0324-721X
Page Range: pp. 567-577
Language: angol
Related URLs: http://acta.bibl.u-szeged.hu/38518/
Uncontrolled Keywords: Természettudomány, Informatika
Additional Information: Bibliogr.: p. 576-577.; Abstract
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2021. Mar. 24. 14:43
URI: http://acta.bibl.u-szeged.hu/id/eprint/12741

Actions (login required)

View Item View Item