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.