The effect of tossing coins in omega-automata
From International Center for Computational Logic
The effect of tossing coins in omega-automata
Christel BaierChristel Baier, Nathalie BertrandNathalie Bertrand, Marcus GrößerMarcus Größer
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
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
- 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
@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}
}