%0 Journal Article 
%F acm12
%A Baier, C.
%A Grösser, M.
%A Bertrand, N.
%T Probabilistic w-automata
%J Journal of the ACM
%V 59
%N 1
%X Probabilistic w-automata are variants of nondeterministic automata over infinite words where all choices are resolved by probabilistic distributions. Acceptance of a run for an infinite input word can be defined using traditional acceptance criteria for w-automata, such as Büchi, Rabin or Streett conditions. The accepted language of a probabilistic w-automata is then defined by imposing a constraint on the probability measure of the accepting runs. In this paper, we study a series of fundamental properties of probabilistic w-automata with three different language-semantics: (1) the probable semantics that requires positive acceptance probability, (2) the almost-sure semantics that requires acceptance with probability 1, and (3) the threshold semantics that relies on an additional parameter lambda in ]0,1[ that specifies a lower probability bound for the acceptance probability. We provide a comparison of probabilistic w-automata under these three semantics and nondeterministic w-automata concerning expressiveness and efficiency. Furthermore, we address closure properties under the Boolean operators union, intersection and complementation and algorithmic aspects, such as checking emptiness or language containment
%U http://dx.doi.org/10.1145/2108242.2108243
%8 February
%D 2012