Reduction of stochastic parity to stochastic mean-payoff games
Chatterjee K, Henzinger TA. 2008. Reduction of stochastic parity to stochastic mean-payoff games. Information Processing Letters. 106(1), 1–7.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
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, and mean-payoff (or limit-average) objectives. These games lie in NP ∩ coNP. We present a polynomial-time Turing reduction of stochastic parity games to stochastic mean-payoff games.
Publishing Year
Date Published
2008-03-31
Journal Title
Information Processing Letters
Publisher
Elsevier
Volume
106
Issue
1
Page
1 - 7
IST-REx-ID
Cite this
Chatterjee K, Henzinger TA. Reduction of stochastic parity to stochastic mean-payoff games. Information Processing Letters. 2008;106(1):1-7. doi:10.1016/j.ipl.2007.08.035
Chatterjee, K., & Henzinger, T. A. (2008). Reduction of stochastic parity to stochastic mean-payoff games. Information Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2007.08.035
Chatterjee, Krishnendu, and Thomas A Henzinger. “Reduction of Stochastic Parity to Stochastic Mean-Payoff Games.” Information Processing Letters. Elsevier, 2008. https://doi.org/10.1016/j.ipl.2007.08.035.
K. Chatterjee and T. A. Henzinger, “Reduction of stochastic parity to stochastic mean-payoff games,” Information Processing Letters, vol. 106, no. 1. Elsevier, pp. 1–7, 2008.
Chatterjee K, Henzinger TA. 2008. Reduction of stochastic parity to stochastic mean-payoff games. Information Processing Letters. 106(1), 1–7.
Chatterjee, Krishnendu, and Thomas A. Henzinger. “Reduction of Stochastic Parity to Stochastic Mean-Payoff Games.” Information Processing Letters, vol. 106, no. 1, Elsevier, 2008, pp. 1–7, doi:10.1016/j.ipl.2007.08.035.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar