Další formáty:
BibTeX
LaTeX
RIS
@article{916021,
author = {Masopust, Tomáš},
article_location = {Poland},
article_number = {1-2},
language = {eng},
issn = {0169-2968},
journal = {Fundamenta Informaticae},
title = {Regulated Nondeterminism in Pushdown Automata: The Non-Regular Case},
url = {http://dx.doi.org/10.3233/FI-2010-338},
volume = {104},
year = {2010}
}
TY - JOUR
ID - 916021
AU - Masopust, Tomáš
PY - 2010
TI - Regulated Nondeterminism in Pushdown Automata: The Non-Regular Case
JF - Fundamenta Informaticae
VL - 104
IS - 1-2
SP - 111-124
EP - 111-124
PB - IOS Press, The Netherlands
SN - 01692968
UR - http://dx.doi.org/10.3233/FI-2010-338
N2 - 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.
ER -
MASOPUST, Tomáš. Regulated Nondeterminism in Pushdown Automata: The Non-Regular Case. \textit{Fundamenta Informaticae}. Poland: IOS Press, The Netherlands, 2010, roč.~104, 1-2, s.~111-124. ISSN~0169-2968.
|
