A hierarchy theorem for regular languages over free bisemigroups
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Published: |
2004
|
| Series: | Acta cybernetica
16 No. 4 |
| Kulcsszavak: | Számítástechnika, Nyelvészet - számítógép alkalmazása |
| Subjects: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12741 |
| LEADER | 01192nab a2200217 i 4500 | ||
|---|---|---|---|
| 001 | acta12741 | ||
| 005 | 20220615103636.0 | ||
| 008 | 161015s2004 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Németh Zoltán L. | |
| 245 | 1 | 2 | |a A hierarchy theorem for regular languages over free bisemigroups |h [elektronikus dokumentum] / |c Németh Zoltán L. |
| 260 | |c 2004 | ||
| 300 | |a 567-577 | ||
| 490 | 0 | |a Acta cybernetica |v 16 No. 4 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Nyelvészet - számítógép alkalmazása | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12741/1/Nemeth_2004_ActaCybernetica.pdf |z Dokumentum-elérés |