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

This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/Archive/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