MASOPUST, Tomáš a Alexander MEDUNA. On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops. In Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings. Balatonfured, Hungary: Computer and Automation Research Institute, Hungarian Academy of Sciences, 2008, s. 325-336. ISBN 978-963-311-367-7.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
Název česky O čistých zásobníkových automatech, které provádí úplný zásobníkový pop
Autoři MASOPUST, Tomáš a Alexander MEDUNA.
Vydání Balatonfured, Hungary, Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings, od s. 325-336, 12 s. 2008.
Nakladatel Computer and Automation Research Institute, Hungarian Academy of Sciences
Další údaje
Typ výsledku Stať ve sborníku
Utajení není předmětem státního či obchodního tajemství
Organizační jednotka Fakulta informatiky
ISBN 978-963-311-367-7
Klíčová slova anglicky pure multi-pushdown automaton, complete-pushdown pop, infinite hierarchy
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. RNDr. Tomáš Masopust, Ph.D., DSc., učo 4030. Změněno: 18. 12. 2008 22:18.
Anotace
This paper introduces and discusses pure multi-pushdown automata that remove symbols from their pushdowns only by performing complete-pushdown pops. During this operation, the entire pushdown is compared with a prefix of the input, and if they match, the pushdown is completely emptied 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. If these automata are allowed to join their pushdowns and create new pushdowns, then they define another infinite hierarchy of language families according to the number of pushdowns.
Anotace česky
Článek zavádí a studuje čisté zásobníkové automaty, které vymazávají symboly ze zásobníků pouze provedením úplného zásobníkového popu. Během této operace se celý zásobník porovná s prefixem vstupního řetězce a když se shodují, tak je celý zásobník vyprázdněn a čtecí hlava se na vstupu posune za tento řetězec. Článek dokazuje, že tyto automaty definují nekonečnou hierarchii jazykových tříd. Rovněž je studován případ, kdy automat může svoje zásobníky spojovat a vytvářet nové zásobníky.
VytisknoutZobrazeno: 12. 6. 2024 05:20