Detail publikace

On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops

MASOPUST Tomáš a MEDUNA Alexander. On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops. Acta Cybernetica, roč. 19, č. 2, 2009, s. 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
angličtina
Autoři
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{FITPUB9084,
   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 = "https://www.fit.vut.cz/research/publication/9084"
}
Nahoru