2009
On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops
MASOPUST, Tomáš a Alexander MEDUNAZákladní údaje
Originální název
On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops
Název česky
O čistých multi-zásobníkových automatech, které provádí úplný zásobníkový pop
Autoři
MASOPUST, Tomáš a Alexander MEDUNA
Vydání
Acta Cybernetica, Szeged, University Szeged, 2009, 0324-721X
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10201 Computer sciences, information science, bioinformatics
Utajení
není předmětem státního či obchodního tajemství
Označené pro přenos do RIV
Ne
Organizační jednotka
Fakulta informatiky
Klíčová slova anglicky
Pure multi-pushdown automaton, complete pushdown pop, infinite hierarchy.
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 22. 12. 2009 18:21, doc. RNDr. Tomáš Masopust, Ph.D., DSc.
V originále
This paper introduces and discusses pure multi-pushdown automata that remove symbols from their pushdowns only by performing complete pushdown pops. This means that during a pop operation, the entire pushdown is compared with a prefix of the input, and if they match, the whole contents of the pushdown is erased and the input is advanced by the prefix. The paper proves that these automata define an infinite hierarchy of language families identical with the infinite hierarchy of language families resulting from right linear simple matrix grammars. In addition, this paper discusses some other extensions of these automata with respect to operations they can perform with their pushdowns. More specifically, it discusses pure multi-pushdown automata that perform complete pushdown pops that are allowed to join two pushdowns and/or create a new pushdown.
Česky
Článek diskutuje čisté multizásobníkové automaty, které odstraňují symboly ze zásobníků pouze tak, že provedou úplný zásobníkový pop. To znamená, že během operace pop je celý obsah zásobníku porovnán s prefixem vstupu a pokud se shodují, celý obsah zásobníku je smazán a odpovídající prefix vstupu přečten. V článku je ukázáno, že tyto automaty definují nekonečnou hierarchii tříd jazyků, jenž je shodná s nekonečnou hierarchií tříd jazyků generovaných pravě lineárními prostými maticovými gramatikami. Navíc jsou diskutována některá rozšíření těchto automatů, jako např. možnost spojit dva zásobníky v jeden, či vytvoření zásobníku nového.