The decidability frontier for probabilistic automata on infinite words - Chatterjee, Krishnendu; Henzinger, Thomas A; Tracol, Mathieu; COMponent-Based Embedded Systems design Techniques; Rigorous Systems Engineering; Microsoft Research Faculty Fellowship; Design for Embedded Systems (ArXiv, 2011)
We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, Büchi, coBüchi, 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.
submitted
Keywords: preprint