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.File | Dimensione | Formato | |
---|---|---|---|
ncma10.pdf
non disponibili |
177.29 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.