We consider two-tape automata where one tape contains the input word w, and the other contains an advice string for some function . 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 . 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 . 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 (resp. ). We show that for advice of size there is no gap between determinism and non-determinism. In general, we can show that the gap is not more than exponential.
DLT
2021-08-06
2024-04-03