Consider the deterministic (resp. non-deterministic) one-way finite automaton that is defined in the usual way except that it has k heads and in each step can decide which head to move. (It is allowed to run until all heads reach the end-marker of the input.) These automata are denoted by k-DFA (resp. k-FA) and it was shown in several papers that k+1 heads are better than k, i.e., their is a language that can be recognized only with more heads. Probably the simplest of these arguments is by Yao and Rivest (http://people.csail.mit.edu/rivest/pubs/YR78.pdf).However, notice that if we allow the k-headed automata to read the input k+1 times, then it can also recognize the language given as a counterexample. (Here define reading t times as you would like to - when the first reading is finished, start the second one etc. OR run the machines in parallel t times from t different starting states and then take some boolean function of their final states.)So my question:Is there a language that can be recognized by a k+1-headed automaton but by no k-headed automaton that is allowed to read the input t times? (Here t can depend on the language but not on the input.)Note: Please do not link me to papers asking if I have seen it! I have read many related things...
Are k+1 heads better than k for multiread finite automata?
automata theory;dfa;hierarchy theorems