Strategy improvement and randomized subexponential algorithms for stochastic parity games - Chatterjee, Krishnendu; Henzinger, Thomas A; STACS: Theoretical Aspects of Computer Science (Springer, 2006)
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.
published
yes
Keywords: conference paper