Reduction of stochastic parity to stochastic mean-payoff games

A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with w-regular winning conditions specified as parity objectives, and mean-payoff (or limit-average) objectives. These games lie in NP boolean AND coNP. We present a polynomial-time Turing reduction of stochastic parity games to stochastic mean-payoff games. (c) 2007 Published by Elsevier B.V.


Published in:
Information Processing Letters, 106, 1-7
Year:
2008
Keywords:
Laboratories:




 Record created 2010-11-30, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)