Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games
verfasst von : Krishnendu Chatterjee, Thomas A. Henzinger
Erschienen in: STACS 2006
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
A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with
ω
-regular winning conditions specified as parity objectives. These games lie in NP ∩ coNP. We present a strategy improvement algorithm for stochastic parity games; this is the first non-brute-force algorithm for solving these games. From the strategy improvement algorithm we obtain a randomized subexponential-time algorithm to solve such games.