Tight bounds on the simulation of unary probabilistic automata by deterministic automata

In 1963, Rabin proved that any $n$--state probabilistic automaton, accepting a language with a $\delta$--isolated cut--point, can be simulated by a deterministic automaton with no more than $(1+1/\delta)^{n-1}$ states. In this paper, we improve this result in the unary case, namely in the case of automata and languages defined over a one letter input alphabet. We show that any unary $n$--state probabilistic automaton with an isolated cut--point can be simulated by a deterministic automaton with $O(\szalay{n})$ states in the cyclic part. Furthermore, we show that this result is tight. We also study the number of states of the initial path of the minimum deterministic automaton which simulates the given $n$--state probabilistic automaton. We show that this number cannot be bounded by any function of the only parameter $n$.