kOne-Way Heads Cannot Do String-Matching

摘要

We settle a conjecture raised by Z. Galil and J. Seiferas 14 years ago (J. Comput. System Sci.26(1983), 280–294):k-head one-way deterministic finite automata cannot perform string-machine (i.e., accept the language {x#y∣∃u ∃v y=uxv}), for anyknonsensing heads.