Detail publikačního výsledku

Regulated Nondeterminism in PDAs: The Non-Regular Case

MASOPUST, T.

Originální název

Regulated Nondeterminism in PDAs: The Non-Regular Case

Anglický název

Regulated Nondeterminism in PDAs: The Non-Regular Case

Druh

Stať ve sborníku mimo WoS a Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

Pushdown automata, regulation, computational power, descriptional complexity.

Klíčová slova v angličtině

Pushdown automata, regulation, computational power, descriptional complexity.

Autoři

MASOPUST, T.

Rok RIV

2010

Vydáno

06.07.2009

Nakladatel

Austrian Computer Society

Místo

Wroclaw

ISBN

978-3-85403-256-4

Kniha

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

Edice

books@ocg.at Band 256

Strany od

181

Strany do

194

Strany počet

14

BibTex

@inproceedings{BUT33731,
  author="Tomáš {Masopust}",
  title="Regulated Nondeterminism in PDAs: The Non-Regular Case",
  booktitle="Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA)",
  year="2009",
  series="books@ocg.at Band 256",
  pages="181--194",
  publisher="Austrian Computer Society",
  address="Wroclaw",
  isbn="978-3-85403-256-4"
}