<p>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 (<a href="http://people.csail.mit.edu/rivest/pubs/YR78.pdf">http://people.csail.mit.edu/rivest/pubs/YR78.pdf</a>).</p>

<p>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.)</p>

<p>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.)</p>

<p>Note: Please do not link me to papers asking if I have seen it! I have read many related things...</p>

CC BY-SA 3.0
2013-07-14T23:39:20.867Z
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.
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-07-15T05:15:04.167Z
Is l part of the input, or for some l? Do you want to separate k and k-1?
domotorp
CC BY-SA 3.0
2013-07-15T07:37:21.737Z
$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(?)
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-07-15T08:28:10.167Z
It does look convincing enough, although of course I have no clue how to prove it...
domotorp
<automata-theory><dfa><hierarchy-theorems>
Are k+1 heads better than k for multiread finite automata?
domotorp
# Are k+1 heads better than k for multiread finite automata?

(Asked by: username_0 on 2013-07-14)

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

**Tags:** automata-theory, dfa, hierarchy-theorems
> **Comments:**
> **username_1**: 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.  
> **username_0**: Is l part of the input, or for some l? Do you want to separate k and k-1?  
> **username_1**: $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(?)  
> **username_0**: It does look convincing enough, although of course I have no clue how to prove it...  

---

## 0 answers

