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(e(root 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 at the endmarkers only. Further results on simulating unary alternating finite automata are pointed out. Our results give answers to some questions left open in the literature.

Optimal simulations between unary automata / C. Mereghetti, G. Pighizzini (LECTURE NOTES IN COMPUTER SCIENCE). - In: STACS 98 / [a cura di] M. Morvan, C. Meinel, D. Krob. - Berlin : Springer, 1998. - ISBN 9783540642305. - pp. 139-149 (( 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
Primo
;
G. Pighizzini
Ultimo
1998

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(e(root 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 at the endmarkers only. Further results on simulating unary alternating finite automata are pointed out. Our results give answers to some questions left open in the literature.
finite automata
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
pubblicato.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 1.94 MB
Formato Adobe PDF
1.94 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento 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: http://hdl.handle.net/2434/178765
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact