Detail publikace
Reducing Deep Pushdown Automata and Infinite Hierarchy
Automata Theory, Top-Down Parser, Bottom-Up Parser, Deep Pushdown Automata, Infinite hierarchy, Reduction Operation, Shift Operation
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.
@inproceedings{BUT22277,
author="Rudolf {Schönecker} and Zbyněk {Křivka} and Alexandr {Meduna}",
title="Reducing Deep Pushdown Automata and Infinite Hierarchy",
booktitle="MEMICS 2006 Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
year="2006",
pages="214--221",
publisher="Faculty of Information Technology BUT",
address="Mikulov",
isbn="80-214-3287-X"
}