Regulated Nondeterminism in PDAs: The Non-Regular Case

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F09%3APU82636" target="_blank" >RIV/00216305:26230/09:PU82636 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Regulated Nondeterminism in PDAs: The Non-Regular Case

Popis výsledku v původním jazyce

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 formof the pushdown content during any computation are sufficient for these automata to be computationally complete. Finally, some descriptional complexity results are discussed.

Název v anglickém jazyce

Regulated Nondeterminism in PDAs: The Non-Regular Case

Popis výsledku anglicky

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 formof the pushdown content during any computation are sufficient for these automata to be computationally complete. Finally, some descriptional complexity results are discussed.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2009

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA)

ISBN

978-3-85403-256-4

ISSN

—

e-ISSN

—

Počet stran výsledku

14

Strana od-do

—

Název nakladatele

Austrian Computer Society

Místo vydání

Wroclaw

Místo konání akce

Wroclaw, Poland

Datum konání akce

31. 8. 2009

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—