Abstract of Paper

Probabilistic and Nondeterministic Unary Automata
by Gregor Gramlich


We investigate unary regular languages and compare deterministic finite
automata (DFA's), nondeterministic finite automata (NFA's) and
probabilistic finite automata (PFA's) with respect to their size.

Given a unary PFA with $n$ states and an $\epsilon$-isolated cutpoint, we
show that the minimal equivalent DFA has at most $n^(1 / (2\epsilon))$
states in its cycle. This result is almost optimal, since for any
$\alpha<1$ a family of PFA's can be constructed such that every equivalent
DFA has at least $n^(\alpha / (2\epsilon))$ states. Thus we show that for
the model of probabilistic automata with a constant error bound, there
is only a polynomial blowup for cyclic languages.

Given a unary NFA with n states, we show that efficiently approximating
the size of a minimal equivalent NFA within the factor $\sqrt(n) / \ln(n)$
is impossible unless P=NP. This result even holds under the promise that
the accepted language is cyclic.
On the other hand we show that we can approximate a minimal NFA within
the factor $\ln(n)$, if we are given a cyclic unary n-state DFA.