acm12

C. Baier, M. Grösser, N. Bertrand. Probabilistic w-automata. Journal of the ACM, 59(1), February 2012.

Abstract

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

Contact

Nathalie Bertrand http://www.irisa.fr/prive/nbertran/

BibTex Reference

@article{acm12,
   Author = {Baier, C. and Grösser, M. and Bertrand, N.},
   Title = {Probabilistic w-automata},
   Journal = {Journal of the ACM},
   Volume = {59},
   Number = {1},
   Month = {February},
   Year = {2012}
}

EndNote Reference [help]

Get EndNote Reference (.ref)