TY - GEN
T1 - On Stateless multihead finite automata and multihead pushdown automata
AU - Frisco, Pierluigi
AU - Ibarra, Oscar H.
PY - 2009
Y1 - 2009
N2 - A stateless k-head two-way deterministic finite automaton (k-head 2DFA), has only one state, hence the designation stateless. Its transitions depends solely on the symbols currently scanned by its k heads, and in every such transition each head can move one cell left, right, or remain stationary. An input, which is delimited by end markers, is accepted if the machine, when started with all heads on the left end marker, reaches the configuration where all the heads are on the right end marker. The nondeterministic version is denoted by k-head 2NFA. We prove that stateless (k+1)-head 2DFAs (resp., 2NFAs) are computationally more powerful than k-head 2DFAs (resp., 2NFAs), improving a recent result where it was shown that (k+4) heads are better than k heads. We also study stateless multihead pushdown automata in their two-way and one-way, deterministic and nondeterministic variations and show that for all these varieties, k+1 heads allow more computational power than k heads. Finally, we give some characterizations of stateless multihead finite and multihead pushdown automata. © 2009 Springer Berlin Heidelberg.
AB - A stateless k-head two-way deterministic finite automaton (k-head 2DFA), has only one state, hence the designation stateless. Its transitions depends solely on the symbols currently scanned by its k heads, and in every such transition each head can move one cell left, right, or remain stationary. An input, which is delimited by end markers, is accepted if the machine, when started with all heads on the left end marker, reaches the configuration where all the heads are on the right end marker. The nondeterministic version is denoted by k-head 2NFA. We prove that stateless (k+1)-head 2DFAs (resp., 2NFAs) are computationally more powerful than k-head 2DFAs (resp., 2NFAs), improving a recent result where it was shown that (k+4) heads are better than k heads. We also study stateless multihead pushdown automata in their two-way and one-way, deterministic and nondeterministic variations and show that for all these varieties, k+1 heads allow more computational power than k heads. Finally, we give some characterizations of stateless multihead finite and multihead pushdown automata. © 2009 Springer Berlin Heidelberg.
U2 - 10.1007/978-3-642-02737-6_19
DO - 10.1007/978-3-642-02737-6_19
M3 - Conference contribution
SN - 3642027369
SN - 9783642027369
VL - 5583 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 240
EP - 251
BT - Developments in Language Theory - 13th International Conference, DLT 2009, Proceedings
T2 - 13th International Conference on Developments in Language Theory
Y2 - 30 June 2009 through 3 July 2009
ER -