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 α(|w|) for some function α : N → Σ∗. 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 NUDSPACE. We show this restriction to be not very significant since, e. g., L (2I2ADFA/poly), i. e., languages recognized by automata with 2-way input and advice tape with polynomial advice equals 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 nonuniform automata. In particular, the question whether there can be a more than polynomial gap in advice between determinism and nondeterminism 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 L = NL (resp. LL = 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.