Abstract of Paper

Probabilistic and Nondeterministic Unary Automata
by Gregor Gramlich

Abstract:

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.