String-matching cannot be done by a two-head one-way deterministic finite automaton
Ming Li, Yaacov Yesha · Information Processing Letters · 1986
We show that string-matching cannot be performed by a two-head one-way deterministic finite automaton (or even by a Turing machine with two one-way input heads and o(n) storage space). Thus, we answer the special case k = 2 of the open question, due to Galil and Seiferas (1983), whether a k-head one-way deterministic finite automaton can perform string-matching.