A hierarchy theorem for regular languages over free bisemigroups
AbstractIn this article a question left open in  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.
Download data is not yet available.
How to Cite
Németh, Z. L. (2004). A hierarchy theorem for regular languages over free bisemigroups. Acta Cybernetica, 16(4), 567-577. Retrieved from https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3642