Publication Details

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

MASOPUST Tomáš and MEDUNA Alexander. 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: Computer and Automation Research Institute, Hungarian Academy of Sciences, 2008, pp. 325-336. ISBN 978-963-311-367-7.
Czech title
O čistých zásobníkových automatech, které provádí úplný zásobníkový pop
Type
conference paper
Language
english
Authors
Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Keywords

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

Abstract

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.

Published
2008
Pages
325-336
Proceedings
Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings
Conference
The 12th International Conference on Automata and Formal Languages, Balatonfured, HU
ISBN
978-963-311-367-7
Publisher
Computer and Automation Research Institute, Hungarian Academy of Sciences
Place
Balatonfured, HU
BibTeX 
@INPROCEEDINGS{FITPUB8610,
   author = "Tom\'{a}\v{s} Masopust and Alexander Meduna",
   title = "On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops",
   pages = "325--336",
   booktitle = "Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings",
   year = 2008,
   location = "Balatonfured, HU",
   publisher = "Computer and Automation Research Institute, Hungarian Academy of Sciences",
   ISBN = "978-963-311-367-7",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8610"
}
Back to top