Citation
Krishnendu Chatterjee, Tom Henzinger. "Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games". STACS, February, 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. These games lie in NP and coNP. We present a strategy improvement algorithm for stochastic parity games; this is the first non-brute-force algorithm for solving these games. From the strategy improvement algorithm we obtain a randomized subexponential-time algorithm to solve such games.

Electronic downloads

• stacs06b.ps · application/postscript · 241 kbytes

• HTML

  Krishnendu Chatterjee, Tom Henzinger. <a
  href="http://chess.eecs.berkeley.edu/pubs/80.html"
  >Strategy Improvement and Randomized Subexponential
  Algorithms for Stochastic Parity Games</a>, STACS,
  February, 2006.

• Plain text

  Krishnendu Chatterjee, Tom Henzinger. "Strategy
  Improvement and Randomized Subexponential Algorithms for
  Stochastic Parity Games". STACS, February, 2006.

• BibTeX

  @inproceedings{ChatterjeeHenzinger06_StrategyImprovementRandomizedSubexponentialAlgorithms,
      author = {Krishnendu Chatterjee and Tom Henzinger},
      title = {Strategy Improvement and Randomized Subexponential
                Algorithms for Stochastic Parity Games},
      booktitle = {STACS},
      month = {February},
      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. These games lie in NP and coNP.
                We present a strategy improvement algorithm for
                stochastic parity games; this is the first
                non-brute-force algorithm for solving these games.
                From the strategy improvement algorithm we obtain
                a randomized subexponential-time algorithm to
                solve such games. },
      URL = {http://chess.eecs.berkeley.edu/pubs/80.html}
  }
  

Posted by Krishnendu Chatterjee, PhD on 9 May 2006.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.