# 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