We consider the problem of computing the costs---{ in terms of states---of optimal simulations between different kinds of finite automata recognizing unary languages. Our main result is a tight simulation of unary n-state two-way nondeterministic automata by $O({{\rm e}^{\sqrt{{n}\ln{n}}}})$-state one-way deterministic automata. In addition, we show that, given a unary n-state two-way nondeterministic automaton, one can construct an equivalent O(n^2)-state two-way nondeterministic automaton performing both input head reversals and nondeterministic choices only at the ends of the input tape. Further results on simulating unary one-way alternating finite automata are also discussed.
Optimal simulations between unary automata / C. Mereghetti, G. Pighizzini. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 30:6(2000), pp. 1976-1992. ((Intervento presentato al 15. convegno Annual Symposium on Theoretical Aspects of Computer Science tenutosi a Paris nel 1998.
Optimal simulations between unary automata
C. Mereghetti
;G. PighizziniUltimo
2000
Abstract
We consider the problem of computing the costs---{ in terms of states---of optimal simulations between different kinds of finite automata recognizing unary languages. Our main result is a tight simulation of unary n-state two-way nondeterministic automata by $O({{\rm e}^{\sqrt{{n}\ln{n}}}})$-state one-way deterministic automata. In addition, we show that, given a unary n-state two-way nondeterministic automaton, one can construct an equivalent O(n^2)-state two-way nondeterministic automaton performing both input head reversals and nondeterministic choices only at the ends of the input tape. Further results on simulating unary one-way alternating finite automata are also discussed.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
298.03 kB
Formato
Adobe PDF
|
298.03 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.