Strategy improvement and randomized subexponential algorithms for stochastic parity games
Chatterjee K, Henzinger TA. 2006. Strategy improvement and randomized subexponential algorithms for stochastic parity games. STACS: Theoretical Aspects of Computer Science, LNCS, vol. 3884, 512–523.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
Series Title
LNCS
Abstract
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.
Publishing Year
Date Published
2006-02-14
Publisher
Springer
Volume
3884
Page
512 - 523
Conference
STACS: Theoretical Aspects of Computer Science
IST-REx-ID
Cite this
Chatterjee K, Henzinger TA. Strategy improvement and randomized subexponential algorithms for stochastic parity games. In: Vol 3884. Springer; 2006:512-523. doi:10.1007/11672142_42
Chatterjee, K., & Henzinger, T. A. (2006). Strategy improvement and randomized subexponential algorithms for stochastic parity games (Vol. 3884, pp. 512–523). Presented at the STACS: Theoretical Aspects of Computer Science, Springer. https://doi.org/10.1007/11672142_42
Chatterjee, Krishnendu, and Thomas A Henzinger. “Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games,” 3884:512–23. Springer, 2006. https://doi.org/10.1007/11672142_42.
K. Chatterjee and T. A. Henzinger, “Strategy improvement and randomized subexponential algorithms for stochastic parity games,” presented at the STACS: Theoretical Aspects of Computer Science, 2006, vol. 3884, pp. 512–523.
Chatterjee K, Henzinger TA. 2006. Strategy improvement and randomized subexponential algorithms for stochastic parity games. STACS: Theoretical Aspects of Computer Science, LNCS, vol. 3884, 512–523.
Chatterjee, Krishnendu, and Thomas A. Henzinger. Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games. Vol. 3884, Springer, 2006, pp. 512–23, doi:10.1007/11672142_42.
Google Scholar