We show that, on inputs of length exceeding 5n(2), any n-state unary 2nfa (two-way nondeterministic finite automaton) can be simulated by a (2n+2)-state quasi sweeping 2nfa. Such a result, besides providing a "normal form" for 2nfa's, enables us to get a subexponential simulation of unary 2nfa's by 2dfa's (two-way deterministic finite automata). In fact, we prove that any n-state unary 2nfa can be simulated by a 2dfa with O(n (log n+4)) states.
Converting two-way nondeterministic unary automata into simpler automata / V. Geffert, C. Mereghetti, G. Pighizzini - In: Mathematical Foundations of Computer Science 2001 / [a cura di] J. Sgall, A. Pultr, P. Kolman. - [s.l] : Springer, 2001. - ISBN 9783540424963. - pp. 398-407 (( Intervento presentato al 26. convegno International Symposium on Mathematical Foundations of Computer Science tenutosi a Marianske Lazne nel 2001.
Converting two-way nondeterministic unary automata into simpler automata
C. MereghettiSecondo
;G. PighizziniUltimo
2001
Abstract
We show that, on inputs of length exceeding 5n(2), any n-state unary 2nfa (two-way nondeterministic finite automaton) can be simulated by a (2n+2)-state quasi sweeping 2nfa. Such a result, besides providing a "normal form" for 2nfa's, enables us to get a subexponential simulation of unary 2nfa's by 2dfa's (two-way deterministic finite automata). In fact, we prove that any n-state unary 2nfa can be simulated by a 2dfa with O(n (log n+4)) states.
| File | Dimensione | Formato | |
|---|---|---|---|
|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
172.83 kB
Formato
Adobe PDF
|
172.83 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
