Detail publikace

Reducing Deep Pushdown Automata and Infinite Hierarchy

KŘIVKA Zbyněk, MEDUNA Alexander a SCHÖNECKER Rudolf. Reducing Deep Pushdown Automata and Infinite Hierarchy. In: MEMICS 2006 Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Mikulov: Fakulta informačních technologií VUT v Brně, 2006, s. 214-221. ISBN 80-214-3287-X.
Název česky
Redukující hluboké zásobníkové automaty a nekonečná hierarchie
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Abstrakt
Příspěvek prezentuje redukující variantu hlubokých zásobníkových automatů. Hluboké zásobníkové automaty jsou nové zobecnění klasického zásobníkového automatu. Základní myšlenka modifikace se skládá s umožnění těmto automatům přistupovat hlouběji do zásobníku a tam redukovat neprázdné řetězce na nevstupní symboly. Princip je podobný analýze zdola nahoru simulující bezkontextovou gramatiku prostřednictvím klasického zásobníkového automatu až na to, že čteme vstup zprava doleva.
Dále článek prezentuje výsledky o ekvivalenci redukujících zásobníkových automatů s n-limitovanými stavovými gramatikami a o nekonečné hierarchii na této ekvivalenci založené. V závěru zmiňuje modifikace a otevřený problém.
Rok
2006
Strany
214-221
Sborník
MEMICS 2006 Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Konference
2nd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science -- MEMICS'06, Mikulov, CZ
ISBN
80-214-3287-X
Vydavatel
Fakulta informačních technologií VUT v Brně
Místo
Mikulov, CZ
BibTeX
@INPROCEEDINGS{FITPUB8193,
   author = "Zbyn\v{e}k K\v{r}ivka and Alexander Meduna and Rudolf Sch{\"{o}}necker",
   title = "Reducing Deep Pushdown Automata and Infinite Hierarchy",
   pages = "214--221",
   booktitle = "MEMICS 2006 Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
   year = 2006,
   location = "Mikulov, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "80-214-3287-X",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8193"
}
Nahoru