ECCC-Report TR12-092https://eccc.weizmann.ac.il/report/2012/092Comments and Revisions published for TR12-092en-usMon, 16 Jul 2012 17:34:00 +0300
Paper TR12-092
| A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata. |
Pavol Duris
https://eccc.weizmann.ac.il/report/2012/092In 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.
Mon, 16 Jul 2012 17:34:00 +0300https://eccc.weizmann.ac.il/report/2012/092