__
TR12-092 | 6th July 2012 17:12
__

#### A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata.

**Abstract:**
In this paper we deal with one-way multi-head data-independent finite automata. A $k$-head finite automaton $A$ is data-independent, if the position of every head $i$ after step $t$ in the computation on an input $w$ is a function that depends only on the length of the input $w$, on $i$ and on $t$ (i.e. the trajectories of heads must be the same on the inputs of the same length). It is known that

$k(k+1)/2+4$ heads are better than $k$ for one-way $k$-head data-independent finite automata. We improve here this result by showing that $2k+2$ heads are better than $\sqrt{2}k$ heads for such automata.