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.
Record created on 2010-11-30, modified on 2016-08-09