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 = {Krishnendu Chatterjee},
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}
}
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