We show that each n-state unary 2nfa (a two-way nondeterministic finite automaton) can be simulated by an equivalent 2ufa (an unambiguous 2nfa) with a polynomial number of states. Moreover, if L = NL (the classical logarithmic space classes), then each unary 2nfa can be converted into an equivalent 2dfa (a deterministic two-way automaton), still keeping polynomial the number of states. 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 2NFAs to 2DFAs.
Two-way unary automata versus logarithmic space / V. Geffert, G. Pighizzini (LECTURE NOTES IN COMPUTER SCIENCE). - In: Developments in language theory : 14. international conference, DLT 2010, London, ON, Canada, August 17-20, 2010 : proceedings / [a cura di] Y. Gao, H. Lu, S. Seki, S. Yu. - Berlin : Springer, 2010 Aug. - ISBN 9783642144547. - pp. 197-208 (( Intervento presentato al 14. convegno International conference on developments in language theory tenutosi a London (Ontario, Canada) nel 2010 [10.1007/978-3-642-14455-4_19].
Two-way unary automata versus logarithmic space
G. PighizziniUltimo
2010
Abstract
We show that each n-state unary 2nfa (a two-way nondeterministic finite automaton) can be simulated by an equivalent 2ufa (an unambiguous 2nfa) with a polynomial number of states. Moreover, if L = NL (the classical logarithmic space classes), then each unary 2nfa can be converted into an equivalent 2dfa (a deterministic two-way automaton), still keeping polynomial the number of states. 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 2NFAs to 2DFAs.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.