*banner
 

Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games
Krishnendu Chatterjee, Tom Henzinger

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

Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess