Decision Questions for Probabilistic Automata on Small Alphabets

Paul C. Bell, Pavel Semukhin

We study the emptiness and $\lambda$-reachability problems for unary and binary Probabilistic Finite Automata (PFA) and characterise the complexity of these problems in terms of the degr…