期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 2k heads for such automata
