Undecidability results for probabilistic automata
Nathanaël Fijalkow · ACM SIGLOG News · 2017
The model of probabilistic automata was introduced by Rabin in 1963. Ever since, undecidability results were obtained for this model, showing that although simple, it is very expressive. This paper provides streamlined constructions implying the most important negative results, including the celebrated inapproximability result of Condon and Lipton.