Reduction of Stochastic Parity to Stochastic Mean-Payoff Games

Krishnendu Chatterjee and Thomas A. Henzinger

A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with omega-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.

Information Processing Letters 106:1-7, 2008.

Download inofficial, sometimes updated PostScript / PDF document. © 2008 Elsevier.