Regulated Nondeterminism in PDAs: The Non-Regular Case
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Regulated Nondeterminism in PDAs: The Non-Regular Case
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA)
ISBN
978-3-85403-256-4
ISSN
—
e-ISSN
—
Number of pages
14
Pages from-to
—
Publisher name
Austrian Computer Society
Place of publication
Wroclaw
Event location
Wroclaw, Poland
Event date
Aug 31, 2009
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—