Probabilistic automata over infinite words: expressiveness, efficiency, and decidability

Christel BaierChristel Baier, Nathalie BertrandNathalie Bertrand, Marcus GrößerMarcus Größer

DOI Link

Christel Baier, Nathalie Bertrand, Marcus Größer
Probabilistic automata over infinite words: expressiveness, efficiency, and decidability
Proc. of the 11th International Workshop on Descriptional Complexity of Formal Systems, volume 3 of Electronic Proceedings in Theoretical Computer Science, 3--16, 2009

Details
Bibtex

KurzfassungAbstract
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 accepting (almost-sure semantics), or (iii) the probability measure of the accepting runs is greater than a certain threshold (threshold semantics). The underlying notion of an accepting run can be defined as for standard omega-automata by means of a Buechi condition or other acceptance conditions, e.g., Rabin or Streett conditions. In this paper, we put the main focus on the probable semantics and provide a summary of the fundamental properties of probabilistic omega-automata concerning expressiveness, efficiency, and decision problems.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{BBG2009,
  author    = {Christel Baier and Nathalie Bertrand and Marcus Gr{\"{o}}{\ss}er},
  title     = {Probabilistic automata over infinite words: expressiveness,
               efficiency, and decidability},
  booktitle = {Proc. of the 11th International Workshop on Descriptional
               Complexity of Formal Systems},
  series    = {Electronic Proceedings in Theoretical Computer Science},
  volume    = {3},
  year      = {2009},
  pages     = {3--16},
  doi       = {10.4204/EPTCS.3.1}
}