The Decidability Frontier for Probabilistic Automata on Infinite Words
  We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, B\"uchi, coB\"uchi, and limit-average conditions. We consider quantitative and qualitative decision problems. We present extensions and adaptations of proofs for probabilistic finite automata and present a complete characterization of the decidability and undecidability frontier of the quantitative and qualitative decision problems for probabilistic automata on infinite words. 
Krishnendu Chatterjee, Thomas A. Henzinger, Mathieu Tracol
cs.LO cs.FL