TY - JOUR

T1 - On stateless multihead automata

T2 - Hierarchies and the emptiness problem

AU - Ibarra, Oscar H.

AU - Karhumäki, Juhani

AU - Okhotin, Alexander

PY - 2010/1/6

Y1 - 2010/1/6

N2 - We look at stateless multihead finite automata in their two-way and one-way, deterministic and nondeterministic variations. The transition of a k-head automaton depends solely on the symbols currently scanned by its k heads, and every such transition moves each head one cell left or right, or instructs it to stay. We show that stateless (k + 4)-head two-way automata are more powerful than stateless k-head two-way automata. In the one-way case, we prove a tighter result: stateless (k + 1)-head one-way automata are more powerful than stateless k-head one-way automata. Finally, we show that the emptiness problem for stateless 2-head two-way automata is undecidable.

AB - We look at stateless multihead finite automata in their two-way and one-way, deterministic and nondeterministic variations. The transition of a k-head automaton depends solely on the symbols currently scanned by its k heads, and every such transition moves each head one cell left or right, or instructs it to stay. We show that stateless (k + 4)-head two-way automata are more powerful than stateless k-head two-way automata. In the one-way case, we prove a tighter result: stateless (k + 1)-head one-way automata are more powerful than stateless k-head one-way automata. Finally, we show that the emptiness problem for stateless 2-head two-way automata is undecidable.

KW - Multihead automata

KW - Stateless automata

UR - http://www.scopus.com/inward/record.url?scp=71849096133&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2009.09.001

DO - 10.1016/j.tcs.2009.09.001

M3 - Article

AN - SCOPUS:71849096133

VL - 411

SP - 581

EP - 593

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 3

ER -