Reduction of stochastic parity to stochastic mean-payoff games Journal Article


Author(s): Chatterjee, Krishnendu; Henzinger, Thomas A
Article Title: Reduction of stochastic parity to stochastic mean-payoff games
Affiliation
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 methods; formal verification and model checking; stochastic games; parity objectives; mean-payoff objectives
Journal Title: Information Processing Letters
Volume: 106
Issue 1
ISSN: 0020-0190
Publisher: Elsevier  
Date Published: 2008-03-31
Start Page: 1
End Page: 7
URL:
DOI: 10.1016/j.ipl.2007.08.035
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work