• 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. Theoretical Computer Science 411(3), 581–593 , 2010.

http://dx.doi.org/10.1016/j.tcs.2009.09.001

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:

@ARTICLE{jIbKaOk10a,
  title = {On Stateless Multihead Automata: Hierarchies and the Emptiness Problem},
  author = {Ibarra, Oscar and Karhumäki, Juhani and Okhotin, Alexander},
  journal = {Theoretical Computer Science},
  volume = {411},
  number = {3},
  pages = {581–593 },
  year = {2010},
}

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

Publication Forum rating of this publication: level 2

Edit publication