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. Pighizzini
Ultimo
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.
Finite automata; Logarithmic space; Space complexity; State complexity; Unary regular languages
Settore INF/01 - Informatica
ago-2010
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/146904
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact