Probabilistic ω-Automata.

Probabilistic &mega;-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 &mega;-automata, such as Büchi, Rabin or Streett conditions. The accepted language of a probabilistic &mega;-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 &mega;-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 λ ϵ]0, 1[ that specifies a lower probability bound for the acceptance probability. We provide a comparison of probabilistic &mega;-automata under these three semantics and nondeterministic &mega;-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. Categories and Subject Descriptors: D.2.4 [Software Engineering]: Software/Program Verification -- Model checking; F 1.1 [Computation by Abstract Devices]: Models of Computations -- Automata (e.g., finite, pushdown, resource-bounded); F.3.1 [Logics and Meanings of Programs]: Specifying and Verifying and Reasoning about Programs; F.4.3 [Mathematical Logics and Formal Languages]: Formal Languages; G.3 [Probability and Statistics]: Markov Processes General Terms: Languages, Verification, Theory [ABSTRACT FROM AUTHOR]