Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability
Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability
Probabilistic omega-automata are variants of nondeterministic automata for infinite words where all choices are resolved by probabilistic distributions. Acceptance of an infinite input word can be defined in different ways: by requiring that (i) the probability for the accepting runs is positive (probable semantics), or (ii) almost all runs are …