Linear Time Algorithm for Weak Parity Games

Krishnendu Chatterjee

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-153
November 19, 2006

http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-153.pdf

We consider games played on graphs with the winning conditions for the players specified as weak-parity conditions. In weak-parity conditions the winner of a play is decided by looking into the set of states appearing in the play, rather than the set of states appearing infinitely often in the play. A naive analysis of the classical algorithm for weak-parity games yields a quadratic time algorithm. We present a linear time algorithm for solving weak-parity games.


BibTeX citation:

@techreport{Chatterjee:EECS-2006-153,
    Author = {Chatterjee, Krishnendu},
    Title = {Linear Time Algorithm for Weak Parity Games},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {Nov},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-153.html},
    Number = {UCB/EECS-2006-153},
    Abstract = {We consider games played on graphs with the winning conditions for the players specified as weak-parity conditions. In weak-parity conditions the winner of a play is decided by looking into the set of states appearing in the play, rather than the set of states appearing infinitely often in the play. A naive analysis of the classical algorithm for weak-parity games yields a quadratic time algorithm. We present a linear time algorithm for solving weak-parity games.}
}

EndNote citation:

%0 Report
%A Chatterjee, Krishnendu
%T Linear Time Algorithm for Weak Parity Games
%I EECS Department, University of California, Berkeley
%D 2006
%8 November 19
%@ UCB/EECS-2006-153
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-153.html
%F Chatterjee:EECS-2006-153