Regulated nondeterminism in pushdown automata : the non-regular case

Kód výsledku v IS VaVaI

RIV/67985840:_____/10:00353078 - isvavai.cz

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Regulated nondeterminism in pushdown automata : the non-regular case

Popis výsledku v původním jazyce

We continue the investigation of pushdown automata which are allowed to make a non-deterministic decision if and only if their pushdown content forms a string belonging to a given control language. We prove that if the control language is linear and non-regular, then the power of pushdown automata regulated in this way is increased to the power of Turing machines. From a practical point of view, however, it is inefficient to check the form of the pushdown content in each computational step. Therefore, we prove that only two checks of the pushdown content are of interest for these machines to be computationally complete. Based on this observation, we introduce and discuss a new model of regulated pushdown automata.

Název v anglickém jazyce

Regulated nondeterminism in pushdown automata : the non-regular case

Popis výsledku anglicky

We continue the investigation of pushdown automata which are allowed to make a non-deterministic decision if and only if their pushdown content forms a string belonging to a given control language. We prove that if the control language is linear and non-regular, then the power of pushdown automata regulated in this way is increased to the power of Turing machines. From a practical point of view, however, it is inefficient to check the form of the pushdown content in each computational step. Therefore, we prove that only two checks of the pushdown content are of interest for these machines to be computationally complete. Based on this observation, we introduce and discuss a new model of regulated pushdown automata.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2010

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 periodika

Fundamenta Informaticae

ISSN

0169-2968

e-ISSN

—

Svazek periodika

104

Číslo periodika v rámci svazku

1-2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

14

Strana od-do

—

Kód UT WoS článku

000285459400006

EID výsledku v databázi Scopus

—