Informace o publikaci
Regulated Nondeterminism in PDAs: The Non-Regular Case
| Autoři | |
|---|---|
| Rok publikování | 2009 |
| Druh | Článek ve sborníku |
| Konference | Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Klíčová slova | Pushdown automata, regulation, computational power, descriptional complexity. |
| Popis | V tomto článku jsou diskutovány zásobníkové automaty, jenž mohou provést nedeterministický krok pouze tehdy, když obsah jejich zásobníku tvoří slovo patřící do daného kotrolního jazyka. Je dokázáno, že pokud je kontrolní jazyk lineární a neregulární, pak síla takovýchto automatů je stejná jako síla Turingova stroje. Jelikož kontrolování obsahu zásobníku v každém kroku výpočtu není příliš efektivní, je rovněž ukázáno, že stačí tuto kontrolu provést pouze dvakrát během výpočtu. |