Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR12-092 | 6th July 2012 17:12

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

TR12-092
Authors: Pavol Duris
Publication: 16th July 2012 17:34
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.