On stateless multihead automata: Hierarchies and the emptiness problem



: Ibarra Oscar H, Karhumäki Juhan, Okhotin Alexander

Publisher: ELSEVIER SCIENCE BV

: 2010

: Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 411

: 3

: 581

: 593

: 13

: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2009.09.001


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. (C) 2009 Elsevier B.V. All rights reserved.



Last updated on 2024-26-11 at 12:15