Probabilistic Automata on Infinite Words: Decidability and Undecidability Results

摘要

We consider probabilistic automata on infinite words with acceptance denned by safety, reachability, Biichi, coBiichi, and limit-average conditions. We consider quantitative and qualitative decision problems. We present extensions and adaptations of proofs for probabilistic finite automata and present an almost complete characterization of the decidability and undecidability frontier of the quantitative and qualitative decision problems for probabilistic automata on infinite words.