Tight bounds on the simulation of unary probabilistic
automata by deterministic automata
Massimiliano Milani and Giovanni Pighizzini
Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
Abstract
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$.