Regulated Nondeterminism in Pushdown Automata: The Non-Regular Case

MASOPUST, Tomáš. Regulated Nondeterminism in Pushdown Automata: The Non-Regular Case. Fundamenta Informaticae. Poland: IOS Press, The Netherlands, 2010, roč. 104, 1-2, s. 111-124. ISSN 0169-2968.

Základní údaje

Originální název

Regulated Nondeterminism in Pushdown Automata: The Non-Regular Case

Autoři

MASOPUST, Tomáš

Vydání

Fundamenta Informaticae, Poland, IOS Press, The Netherlands, 2010, 0169-2968

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

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

Odkazy

URL

Impakt faktor

Impact factor: 0.522

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

UT WoS

000285459400006

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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.