Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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