We show that, on inputs of length exceeding 5n2, any n-state unary two-way nondeterministic finite automaton (2nfa) 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 two-way deterministic finite automata (2dfa's). In fact, we prove that any n-state unary 2nfa can be simulated by a sweeping 2dfa with O(n⌈log2(n+1)+3⌉) states.
Converting two-way nondeterministic unary automata into simpler automata / V. Geffert, C. Mereghetti, G. Pighizzini. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 295:1-3(2003), pp. 189-203. ((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
2003
Abstract
We show that, on inputs of length exceeding 5n2, any n-state unary two-way nondeterministic finite automaton (2nfa) 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 two-way deterministic finite automata (2dfa's). In fact, we prove that any n-state unary 2nfa can be simulated by a sweeping 2dfa with O(n⌈log2(n+1)+3⌉) states.
| File | Dimensione | Formato | |
|---|---|---|---|
|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
174.69 kB
Formato
Adobe PDF
|
174.69 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.
