A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On stateless multihead automata: Hierarchies and the emptiness problem
Tekijät: Ibarra Oscar H, Karhumäki Juhan, Okhotin Alexander
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2010
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 411
Numero: 3
Aloitussivu: 581
Lopetussivu: 593
Sivujen määrä: 13
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2009.09.001
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali