Regulated Nondeterminism in PDAs: The Non-Regular Case

MASOPUST, Tomáš. Regulated Nondeterminism in PDAs: The Non-Regular Case. In Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA). Wroclaw, Poland: [e-mail], Band 256, Austrian Computer Society, 2009, s. 181-194. ISBN 978-3-85403-256-4.

Základní údaje

Originální název

Regulated Nondeterminism in PDAs: The Non-Regular Case

Autoři

MASOPUST, Tomáš

Vydání

Wroclaw, Poland, Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA), od s. 181-194, 2009

Nakladatel

[e-mail], Band 256, Austrian Computer Society

---

Další údaje

Typ výsledku

Stať ve sborníku

Utajení

není předmětem státního či obchodního tajemství

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

ISBN

978-3-85403-256-4

Klíčová slova anglicky

Pushdown automata, regulation, computational power, descriptional complexity.

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

In this paper, we discuss pushdown automata which can make a nondeterministic decision only if the pushdown content forms a string that belongs to a given control language. It proves that if the control language is linear and non-regular, then the computational power of pushdown automata regulated in this way is increased to the power of Turing machines. Naturally, checking the pushdown content in each computational step is not practically efficient. Therefore, we also prove that two checks of the form of the pushdown content during any computation are sufficient for these automata to be computationally complete. Finally, some descriptional complexity results are discussed.

Česky

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.