Reduction of stochastic parity to stochastic mean-payoff games

K. Chatterjee, T.A. Henzinger, Information Processing Letters 106 (2008) 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
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, 106(1), 1–7. 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 106, no. 1 (2008): 1–7. 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, 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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar