Journal article

MASOPUST Tomáš and MEDUNA Alexander. On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops. Acta Cybernetica. 2009, vol. 19, no. 2, pp. 537-552. ISSN 0324-721X.
Publication language:english
Original title:On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops
Title (cs):O čistých multi-zásobníkových automatech, které provádí úplný zásobníkový pop
Pages:537-552
Place:US
Year:2009
Journal:Acta Cybernetica, Vol. 19, No. 2, US
ISSN:0324-721X
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. This means that during a pop operation, the entire pushdown is compared with a prefix of the input, and if they match, the whole contents of the pushdown is erased 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. In addition, this paper discusses some other extensions of these automata with respect to operations they can perform with their pushdowns. More specifically, it discusses pure multi-pushdown automata that perform complete pushdown pops that are allowed to join two pushdowns and/or create a new pushdown.
BibTeX:
@ARTICLE{
   author = {Tom{\'{a}}{\v{s}} Masopust and Alexander Meduna},
   title = {On Pure Multi-Pushdown Automata that Perform Complete
	Pushdown Pops},
   pages = {537--552},
   journal = {Acta Cybernetica},
   volume = {19},
   number = {2},
   year = {2009},
   ISSN = {0324-721X},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9084}
}

Your IPv4 address: 54.161.25.213
Switch to IPv6 connection

DNSSEC [dnssec]