|
|||||
|
|
Reduction of stochastic parity to stochastic mean-payoff games |
|
| Authors: | Krishnendu Chatterjee Thomas A Henzinger |
| Affiliation: | a EECS, UC Berkeley, USA b EPFL, Switzerland |
| 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. |
| Keywords: | Formal verification and model checking Stochastic games Parity objectives Mean-payoff objectives Formal methods |
| 本文献已被 ScienceDirect 等数据库收录！ | |