Representing the
Meaning of States by Logical Formulae
Juraj Hromkovic, Rastislav Kralovic, Richard Kralovic, Richard Stefanec |
---|

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. |