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. Acta Cybernetica, 2009, vol. 19, no. 2, p. 537-552. ISSN: 0324-721X.
Název česky
O čistých multi-zásobníkových automatech, které provádí úplný zásobníkový pop
Typ
článek v časopise
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 diskutuje čisté multizásobníkové automaty, které odstraňují symboly ze zásobníků pouze tak, že provedou úplný zásobníkový pop. To znamená, že během operace pop je celý obsah zásobníku porovnán s prefixem vstupu a pokud se shodují, celý obsah zásobníku je smazán a odpovídající prefix vstupu přečten. V článku je ukázáno, že tyto automaty definují nekonečnou hierarchii tříd jazyků, jenž je shodná s nekonečnou hierarchií tříd jazyků generovaných pravě lineárními prostými maticovými gramatikami. Navíc jsou diskutována některá rozšíření těchto automatů, jako např. možnost spojit dva zásobníky v jeden, či vytvoření zásobníku nového.

Rok
2009
Strany
537–552
Časopis
Acta Cybernetica, roč. 19, č. 2, ISSN 0324-721X
BibTeX 
@article{BUT49617,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops",
  journal="Acta Cybernetica",
  year="2009",
  volume="19",
  number="2",
  pages="537--552",
  issn="0324-721X"
}
Nahoru