The effect of tossing coins in omega-automata

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

DOI Link

Christel Baier, Nathalie Bertrand, Marcus Größer
The effect of tossing coins in omega-automata
Proc. of the 20th International Conference on Concurrency Theory (CONCUR), volume 5710 of Lecture Notes in Computer Science, 15--29, 2009. Springer

Details
Bibtex

KurzfassungAbstract
In this paper we provide a summary of the fundamental properties of probabilistic automata over infinite words. Such probabilistic automata are a variant of standard automata with Büchi or other ω-regular acceptance conditions, such as Rabin, Streett, parity or Müller, where the nondeterministic choices are resolved probabilistically. Acceptance of an infinite input word can be defined in different ways: by requiring that (i) almost all runs are accepting, or (ii) the probability for the accepting runs is positive, or (iii) the probability measure of the accepting runs is beyond a certain threshold. Surprisingly, even the qualitative criteria (i) and (ii) yield a different picture concerning expressiveness, efficiency, and decision problems compared to the nondeterministic case.
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-642-04081-8_2.

@inproceedings{BBG2009,
  author    = {Christel Baier and Nathalie Bertrand and Marcus Gr{\"{o}}{\ss}er},
  title     = {The effect of tossing coins in omega-automata},
  booktitle = {Proc. of the 20th International Conference on Concurrency Theory
               (CONCUR)},
  series    = {Lecture Notes in Computer Science},
  volume    = {5710},
  publisher = {Springer},
  year      = {2009},
  pages     = {15--29},
  doi       = {10.1007/978-3-642-04081-8_2}
}