Probabilistic acceptors for languages over infinite words

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

DOI Link

Christel Baier, Nathalie Bertrand, Marcus Größer
Probabilistic acceptors for languages over infinite words
Proc. of the 35th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), volume 5404 of Lecture Notes in Computer Science, 19--33, 2009. Springer

Details
Bibtex

KurzfassungAbstract
Probabilistic ω-automata are variants of nondeterministic automata for infinite words where all choices are resolved by probabilistic distributions. Acceptance of an infinite input word requires that the probability for the accepting runs is positive. In this paper, we provide a summary of the fundamental properties of probabilistic ω-automata concerning expressiveness, efficiency, compositionality and decision problems.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-95891-8_3.

@inproceedings{BBG2009,
  author    = {Christel Baier and Nathalie Bertrand and Marcus Gr{\"{o}}{\ss}er},
  title     = {Probabilistic acceptors for languages over infinite words},
  booktitle = {Proc. of the 35th International Conference on Current Trends in
               Theory and Practice of Computer Science (SOFSEM)},
  series    = {Lecture Notes in Computer Science},
  volume    = {5404},
  publisher = {Springer},
  year      = {2009},
  pages     = {19--33},
  doi       = {10.1007/978-3-540-95891-8_3}
}