Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Optimal Strategy Synthesis in Stochastic Müller Games
verfasst von : Krishnendu Chatterjee
Erschienen in: Foundations of Software Science and Computational Structures
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The theory of graph games with
ω
-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the
qualitative
problem asks for the set of states from which a player can win with probability 1 (
almost-sure winning
); and the
quantitative
problem asks for the maximal probability of winning (
optimal winning
) from each state. We consider
ω
-regular winning conditions formalized as Müller winning conditions. We present optimal memory bounds for
pure
almost-sure winning and optimal winning strategies in stochastic graph games with Müller winning conditions. We also present improved memory bounds for randomized almost-sure winning and optimal strategies.