Krishnendu Chatterjee

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-153

November 19, 2006

http://www2.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},
    Year= {2006},
    Month= {Nov},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-153.html
%F Chatterjee:EECS-2006-153