Reduction of Stochastic Parity to Stochastic Mean-payoff Games
Krishnendu Chatterjee, Tom Henzinger

Citation
Krishnendu Chatterjee, Tom Henzinger. "Reduction of Stochastic Parity to Stochastic Mean-payoff Games". Technical report, University of California, Berkeley, UCB/EECS-2006-140, November, 2006.

Abstract
A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with omega-regular winning conditions specified as parity objectives, and mean-payoff (or long-run average) objectives. These games lie in NP and coNP. We present a polynomial time Turing reduction of stochastic parity games to stochastic mean-payoff games.

Electronic downloads

(No downloads are available for this publication.)

Citation formats

• HTML

  Krishnendu Chatterjee, Tom Henzinger. <a
  href="http://chess.eecs.berkeley.edu/pubs/321.html"
  ><i>Reduction of Stochastic Parity to Stochastic
  Mean-payoff Games</i></a>, Technical report, 
  University of California, Berkeley, UCB/EECS-2006-140,
  November, 2006.

• Plain text

  Krishnendu Chatterjee, Tom Henzinger. "Reduction of
  Stochastic Parity to Stochastic Mean-payoff Games".
  Technical report,  University of California, Berkeley,
  UCB/EECS-2006-140, November, 2006.

• BibTeX

  @techreport{ChatterjeeHenzinger06_ReductionOfStochasticParityToStochasticMeanpayoffGames,
      author = {Krishnendu Chatterjee and Tom Henzinger},
      title = {Reduction of Stochastic Parity to Stochastic
                Mean-payoff Games},
      institution = {University of California, Berkeley},
      number = {UCB/EECS-2006-140},
      month = {November},
      year = {2006},
      abstract = {A stochastic graph game is played by two players
                on a game graph with probabilistic transitions. We
                consider stochastic graph games with omega-regular
                winning conditions specified as parity objectives,
                and mean-payoff (or long-run average) objectives.
                These games lie in NP and coNP. We present a
                polynomial time Turing reduction of stochastic
                parity games to stochastic mean-payoff games.},
      URL = {http://chess.eecs.berkeley.edu/pubs/321.html}
  }
  

Posted by Christopher Brooks on 7 Jun 2007.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.