| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428031 | Information Processing Letters | 2008 | 7 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
