On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops

MASOPUST, Tomáš a Alexander MEDUNA. On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops. Acta Cybernetica. Szeged: University Szeged, 2009. ISSN 0324-721X.

Zá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

• Originální 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í
• 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

Anotace

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.

Anotace č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.