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://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5651.html
%F Chatterjee:CSD-05-1391