Two-way unary automata versus logarithmic space
We show that if L = NL (the classical logarithmic space classes), then each unary 2NFA (a two-way nondeterministic finite automaton) can be converted into an equivalent 2DFA (a deterministic two-way automaton), keeping the number of states polynomial. (Unlike other results of this kind, here the deterministic simulation is valid for inputs of all lengths, not only polynomially long ones.) This shows a connection between the standard logarithmic space complexity and the state complexity of two-way unary automata: it indicates that L could be separated from NL by proving a superpolynomial gap, in the number of states, for the conversion from unary 2NFA5 to 2DFA. Moreover, without any unproven assumptions, we show that each n-state unary 2NFA can be simulated by an equivalent 2UFA (an unambiguous 2NFA) with a polynomial number of states. (C) 2011 Elsevier Inc. All rights reserved.
logarithmic space space complexity state complexity unary regular languages finite automata