Abstract. The question whether nondeterminism is more powerful than determinism for two-way automata is one of the most famous old open problems on the border between formal language theory and automata theory. An exponential gap between the number of states of two-way nondeterministic finite automata (2NFA) and their deterministic counterparts (2DFA) was proved only for some restricted versions of two-way automata up to now. This problem is also related to the famous DLOG vs. NLOG problem . An exponential gap between 2NFAs and 2DFAs on words of polynomial length in the parameter of a complete language of Sipser and Sakoda for the 2DFA vs. 2NFAs problem would imply that DLOG is a proper subset of NLOG.

The goal of this paper is rst to survey the attempts to solve the 2DFA vs. 2NFA problem. After that we discus why this problem is so hard in spite of the fact that one has a very clear intuition why nondeterminism has to be more powerful than determinism for this computing model. It seems that the hardness lies in the fact that, when trying to prove lower bounds on the number of states of 2DFAs, we are not able to force the states to have a clear meaning. When designing an automaton, we always assign an unambiguous interpretation to each state. Starting from this point we introduce a new restriction on two-way automata depending on some logic. We force that each state has a clear meaning corresponding to some logical expression about the word currently processed. One has the choice of the logic of the states in that sense that one can x which atom statements are allowed and which logical connections are used. For two such reasonable logics we prove an exponential gap between 2NFAs and 2DFAs. Moreover, using our concept of assigning meaning to the states of 2DFAs we show that there is no exponential gap between general 2NFAs and 2DFAs on inputs of a polynomial length of the complete language of Sakoda and Sipser.