Conference paper

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.
Publication language:english
Original title:On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
Title (cs):O čistých zásobníkových automatech, které provádí úplný zásobníkový pop
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
Place:Balatonfured, HU
Year:2008
ISBN:978-963-311-367-7
Publisher:Computer and Automation Research Institute, Hungarian Academy of Sciences
Keywords
pure multi-pushdown automaton, complete-pushdown pop, infinite hierarchy
Annotation
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.
BibTeX:
@INPROCEEDINGS{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php?id=8610}
}

Your IPv4 address: 54.81.157.56
Switch to IPv6 connection

DNSSEC [dnssec]