Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability

Christel Baier, Nathalie Bertrand, Marcus Größer

Probabilistic omega-automata are variants of nondeterministic automata for infinite words where all choices are resolved by probabilistic distributions. Acceptance of an infinite i…