We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer $d$, there exists a unary $d$-cyclic language such that any pfa for it requires $d$ states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's smaller than nfa's which, in turn, are smaller than deterministic automata.

Probabilistic vs. nondeterministic unary automata / M.P. Bianchi, C. Mereghetti, B. Palano, G. Pighizzini - In: Non-Classical Models for Auomata and Applications / [a cura di] H. Bordihn, R. Freund, M. Holzer, M. Kutrib, F. Otto. - Vienna : Austrian Computer Society, 2010. - ISBN 9783854032564. - pp. 33-44 (( Intervento presentato al 2. convegno Non-Classical Models for Auomata and Applications tenutosi a Jena nel 2010.

Probabilistic vs. nondeterministic unary automata

M.P. Bianchi;C. Mereghetti;B. Palano;G. Pighizzini
2010

Abstract

We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer $d$, there exists a unary $d$-cyclic language such that any pfa for it requires $d$ states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's smaller than nfa's which, in turn, are smaller than deterministic automata.
Probabilistic automata; nondeterministic automata; descriptional complexity; unary automata; unary languages
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
ncma10.pdf

non disponibili

177.29 kB 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/147845
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact