Two-Way Non-uniform Finite Automata

Abstract

We consider two-tape automata where one tape contains the input word w, and the other contains an advice string $\alpha (|w|)$ for some function $\alpha :\mathbb {N}\rightarrow \varSigma ^*$. Such an automaton recognizes a language L if there is an advice function for which every word on the input tape is correctly classified. This model has been introduced by Küçük with the aim to model non-uniform computation on finite automata. So far, most of the results concerned automata whose tapes are both 1-way. First, we show that making even one of the tapes 2-way increases the model’s power. Then we turn our attention to the case of both tapes being 2-way, which can also be viewed as a restricted version of the non-uniform families of automata used by Ibarra and Ravikumar to define the class $\mathsf{NUDSPACE}$. We show this restriction to be not very significant since, e. g., , i. e., languages recognized by automata with 2-way input and advice tape with polynomial advice equals $\mathsf{NUDSPACE} (O(\log (n)))$. Hence, we can show that many interesting problems concerning the state complexity of families of automata carry over to the problems concerning advice size of non-uniform automata. In particular, the question whether there can be a more than polynomial gap in advice between determinism and non-determinism is of great interest: e. g., the existence of a language that can be recognized by some 2-way NFA with some k heads on the advice tape and with polynomial (resp. logarithmic) advice, while a corresponding 2-head DFA would need exponential (resp. polynomial) advice, would imply $\mathsf {L\not =NL}$ (resp. $\mathsf {LL\not =NLL}$). We show that for advice of size $(\log n)^{o(1)}$ there is no gap between determinism and non-determinism. In general, we can show that the gap is not more than exponential.

R. Královič—The research has been supported by the grant 1/0601/20 of the Slovak Scientific Grant Agency VEGA.