• 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 Ibarra, Juhani Karhumäki, Alexander Okhotin, On Stateless Multihead Automata: Hierarchies and the Emptiness Problem. In: Eduardo Laber, Claudson Bornstein, Loana Nogueira, Luerbio Faria (Eds.), LATIN 2008: Theoretical Informatics, 94-105, Springer, 2008.

http://dx.doi.org/10.1007/978-3-540-78773-0_9

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.

BibTeX entry:

@INPROCEEDINGS{inpIbKaOk08a,
  title = {On Stateless Multihead Automata: Hierarchies and the Emptiness Problem},
  booktitle = {LATIN 2008: Theoretical Informatics},
  author = {Ibarra, Oscar and Karhumäki, Juhani and Okhotin, Alexander},
  editor = {Laber, Eduardo and Bornstein, Claudson and Nogueira, Loana and Faria, Luerbio},
  publisher = {Springer},
  pages = {94-105},
  year = {2008},
}

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

Edit publication