# Algorithms for Stochastic Parity Games

### Krishnendu Chatterjee and Thomas A. Henzinger

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-05-1391

May 2005

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1391.pdf

A stochastic graph game is played by two players on a game graph with probabilistic transitions. We present a strategy improvement algorithm for stochastic graph games with omega-regular conditions specified as parity objectives. From the strategy improvement algorithm we obtain a randomized sub-exponential time algorithm to solve stochastic parity games.

BibTeX citation:

@techreport{Chatterjee:CSD-05-1391, Author = {Chatterjee, Krishnendu and Henzinger, Thomas A.}, Title = {Algorithms for Stochastic Parity Games}, Institution = {EECS Department, University of California, Berkeley}, Year = {2005}, Month = {May}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2005/5651.html}, Number = {UCB/CSD-05-1391}, Abstract = {A stochastic graph game is played by two players on a game graph with probabilistic transitions. We present a strategy improvement algorithm for stochastic graph games with omega-regular conditions specified as parity objectives. From the strategy improvement algorithm we obtain a randomized sub-exponential time algorithm to solve stochastic parity games.} }

EndNote citation:

%0 Report %A Chatterjee, Krishnendu %A Henzinger, Thomas A. %T Algorithms for Stochastic Parity Games %I EECS Department, University of California, Berkeley %D 2005 %@ UCB/CSD-05-1391 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2005/5651.html %F Chatterjee:CSD-05-1391