Seminar of Theoretical Computer Science - Rastislav Královič (27.4.2018)
Friday 27.4.2018 at 11:00, Lecture room M/213
By: Rastislav Královič
Tight Hierarchy of Data-Independent Multi-Head Automata
We study the expressive power of 1-way data-independent finite automata with multiple heads. The data-independence means that the trajectory of each head during a computation on an input word w depends only on the length of w. An important question in the understanding of various versions of multi-head automata, is whether additional heads increase the expressive power. For the data-dependent 1-way automata, the famous result by Yao and Rivest established, as early as in 1978, a tight hierarchy that L(1DFA(k)) is a strict subset of L(1DFA(k + 1)). In 1980, Monien proved similar tight hierarchy for 2-way automata, both deterministic and non-deterministic. As noted by Holzer in 2002, Monien’s results yield a tight hierarchy for 2-way data-independent automata. However, somewhat surprisingly, no such hierarchy has been known for the 1-way data-independent automata. We show not only the tight hierarchy for 1-way data-independent automata, but even stronger result as well, that for each k>0, there are languages that can be recognized by a data-independent automaton with k + 1 heads, but cannot be recognized with k heads even with non-deterministic data-dependent automaton. On the other hand, we show that if the non-deterministic automaton is allowed to be two-way, 8 heads are sufficient to simulate all data-independent 1-way automata. Finally, we remark that the restriction of data-independence cannot be compensated by adding more heads, as there are languages that can be recognized by a 1-way deterministic automaton with 2 heads, but cannot be recognize by any data-independent automaton, regardless of the number of heads.