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

<TITLE>Tight bounds on the simulation of unary probabilistic
                         automata by deterministic automata</TITLE>

<H2 ALIGN="CENTER">Tight bounds on the simulation of unary probabilistic
                         automata by deterministic automata</H2>

<H4 ALIGN="CENTER">Massimiliano Milani and Giovanni Pighizzini</H4>

<H6 ALIGN="CENTER">Dipartimento di  Scienze dell'Informazione<BR>
Universit&agrave; degli Studi di Milano<BR>
via Comelico 39 -- 20135  Milano, Italy</H6>

<H5 ALIGN="CENTER">Abstract</H5>

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$.