Detail publikace

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

MASOPUST, T.; MEDUNA, A. On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops. Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings. Balatonfured: Computer and Automation Research Institute, Hungarian Academy of Sciences, 2008. p. 325-336. ISBN: 978-963-311-367-7.
Název česky
O čistých zásobníkových automatech, které provádí úplný zásobníkový pop
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Klíčová slova

pure multi-pushdown automaton, complete-pushdown pop, infinite hierarchy

Abstrakt

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

Rok
2008
Strany
325–336
Sborník
Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings
Konference
AFL 2008, Balatonfured, HU
ISBN
978-963-311-367-7
Vydavatel
Computer and Automation Research Institute, Hungarian Academy of Sciences
Místo
Balatonfured
BibTeX 
@inproceedings{BUT27768,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops",
  booktitle="Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings",
  year="2008",
  pages="325--336",
  publisher="Computer and Automation Research Institute, Hungarian Academy of Sciences",
  address="Balatonfured",
  isbn="978-963-311-367-7"
}
Nahoru