• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On Stateless Multihead Automata: Hierarchies and the Emptiness Problem

Oscar H. Ibarra, Juhani Karhumaki, Alexander Okhotin, On Stateless Multihead Automata: Hierarchies and the Emptiness Problem. TUCS Technical Reports 848, Turku Centre for Computer Science, 2007.

Abstract:

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

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tIbKaOk07a,
  title = {On Stateless Multihead Automata: Hierarchies and the Emptiness Problem},
  author = {Ibarra, Oscar H. and Karhumaki, Juhani and Okhotin, Alexander},
  number = {848},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2007},
  keywords = {Multihead automata, stateless automata},
  ISBN = {978-952-12-1967-2},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication