Loading...
research article
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.
Type
research article
Web of Science ID
WOS:000254375800001
Authors
Publication date
2008
Published in
Volume
106
Start page
1
End page
7
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
November 30, 2010
Use this identifier to reference this record