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...

  • $\begingroup$ Currently, I do not how easy it is, but, I have a "candidate" language: $L_{k,l} = \{u_1 \# u_2 \# \cdots \# u_k\} $ such that $ l < k $, each binary subword ($u_1,\ldots,u_k$) has the same length, and, for each index $i \in \{1,\ldots,|u_1|\}$, there are exactly $l$ subwords whose $i^{th}$ symbols are the same. $\endgroup$ Jul 14, 2013 at 23:39
  • $\begingroup$ Is l part of the input, or for some l? Do you want to separate k and k-1? $\endgroup$
    – domotorp
    Jul 15, 2013 at 5:15
  • $\begingroup$ $l$ is not part of the input. For each $i \in \{1,\ldots,k\}$, $ u_{i} \in \{a,b\}^* $. Moreover, $ |u_1| = |u_2| = \cdots = |u_k| > 0 $. I thought we could separate $k$ and $k-1$ and no new pass/read would help us. Subwords' lenghts can be arbitrary long and, for each index, there can different $l$ subwords. Do you think $k-1$ head is enough with one-pass? I still could not see it. Maybe, I am missing something obvious(?) $\endgroup$ Jul 15, 2013 at 7:37
  • $\begingroup$ It does look convincing enough, although of course I have no clue how to prove it... $\endgroup$
    – domotorp
    Jul 15, 2013 at 8:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.