Tight hierarchy of data-independent multi-head automata

摘要

We study the expressive power of 1-way data-independent finite automata with k heads (1DiDFA(k)). The data-independence means that the trajectory of each head during a computation depends only on the length of the input word. It has long been known that “k+1 heads are better than k” for the (data-dependent) 1DFA(k), and (2-way) 2DiDFA(k). However, somewhat surprisingly, no such hierarchy has been known for the 1DiDFA(k). In this paper we show not only the tight head hierarchy for 1DiDFA(k) but even stronger result as well, that for each k≥1, there are languages that can be recognized by a 1DiDFA(k+1), but cannot be recognized by k one-way heads even with a non-deterministic data dependent automaton. On the other hand, we show that if the data-independent automaton is allowed to be two-way, 3 heads are sufficient to simulate all 1DiDFA(k). Finally, we remark that the restriction of data-independence cannot be compensated by adding more heads.