Affiliations: Dipartimento di Scienze dell'Informazione – Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy. maria.bianchi@unimi.it, {mereghetti, palano}@dsi.unimi.it | Dipartimento di Informatica e Comunicazione – Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy. pighizzini@dico.unimi.it
Note: [] Address for correspondence: Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy
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 accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa's which, in turn, are smaller than deterministic automata.
Keywords: probabilistic automata, nondeterministic automata, descriptional complexity, unary languages
