Multihead one-way finite automata (Q1183574)

One of the hardest tasks in complexity theory is to prove nontrivial lower bounds on the complexity of concrete computing problems. The main contribution of this paper is not the result itself, but the original and involved proof technique introduced in order to get the result. The computing model considered are multihead one-way finite automata, and the complexity measure is the number of heads of these multihead finite automata. It is proved that no one-way \(k\)-head automaton can recognize the language \(P_ m=\{1^{a_ 1}c 1^{a_ 2}c\dots c 1^{a_ m}d1^{a_ m}c 1^{a_{m-1}}c\dots c 1^{a_ 1}\}\) for \(m>k^ 3/2\). The previous lower bound methods for multihead automata based on the paper by \textit{A. C. Yao} and \textit{R. L. Rivest} [\(K+1\) heads are better than \(K\), J. Assoc. Comput. Machin. 25, 337-340 (1978; Zbl 0372.68017)] cannot help to get this result. The lower bound method introduced here is nontrivial and valuable.