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)

[thumbnail of Nemeth_2004_ActaCybernetica.pdf]
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: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38518/
Uncontrolled Keywords: Számítástechnika, Nyelvészet - számítógép alkalmazása
Additional Information: Bibliogr.: p. 576-577. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2022. Jun. 15. 10:36
URI: http://acta.bibl.u-szeged.hu/id/eprint/12741

Actions (login required)

View Item View Item