Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-04081-8_2 | CONCUR |
Keywords | Field | DocType |
different way,infinite word,tossing coins,certain threshold,infinite input word,different picture,probability measure,probabilistic automaton,nondeterministic choice,nondeterministic case,regular acceptance condition,decision problem,probabilistic automata | Quantum finite automata,Discrete mathematics,Decision problem,Combinatorics,Nondeterministic algorithm,Computer science,Automaton,Probability measure,Markov decision process,Probabilistic automaton,ω-automaton | Conference |
Volume | ISSN | Citations |
5710 | 0302-9743 | 1 |
PageRank | References | Authors |
0.35 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christel Baier | 1 | 3053 | 185.85 |
| Nathalie Bertrand | 2 | 250 | 17.84 |
| Marcus Größer | 3 | 334 | 18.23 |