A hierarchy theorem for regular languages over free bisemigroups

Authors

  • Zoltán L. Németh

Abstract

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.

Downloads

Download data is not yet available.

Downloads

Published

2004-01-01

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

Issue

Section

Regular articles

Most read articles by the same author(s)