On Pure Multi-Pushdown Automata that Perform Complete-Pushdown
Pops

D 2008

On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops

MASOPUST, Tomáš a Alexander MEDUNA

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í

Označené pro přenos do RIV

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ěněno: 18. 12. 2008 22:18, doc. RNDr. Tomáš Masopust, Ph.D., DSc.

Anotace

ORIG CZ

V originále

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.

Č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.

Citovat

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.

@inproceedings{800003,
   author = {Masopust, Tomáš and Meduna, Alexander},
   address = {Balatonfured, Hungary},
   booktitle = {Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings},
   keywords = {pure multi-pushdown automaton, complete-pushdown pop, infinite hierarchy},
   location = {Balatonfured, Hungary},
   isbn = {978-963-311-367-7},
   pages = {325-336},
   publisher = {Computer and Automation Research Institute, Hungarian Academy of Sciences},
   title = {On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops},
   year = {2008}
}

TY  - CONF
ID  - 800003
AU  - Masopust, Tomáš - Meduna, Alexander
PY  - 2008
TI  - On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
PB  - Computer and Automation Research Institute, Hungarian Academy of Sciences
CY  - Balatonfured, Hungary
SN  - 9789633113677
KW  - pure multi-pushdown automaton, complete-pushdown pop, infinite hierarchy
N2  - 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.
ER  -

MASOPUST, Tomáš a Alexander MEDUNA. On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops. In \textit{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.

Přehled o publikaci