A1 Refereed original research article in a scientific journal
On stateless multihead automata: Hierarchies and the emptiness problem
Authors: Ibarra Oscar H, Karhumäki Juhan, Okhotin Alexander
Publisher: ELSEVIER SCIENCE BV
Publication year: 2010
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 411
Issue: 3
First page : 581
Last page: 593
Number of pages: 13
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2009.09.001(external)
Abstract
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.
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.
UTU Research Portal