Krishnendu Chatterjee and Thomas A. Henzinger and Nir Piterman

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-144

November 8, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-144.pdf

We consider games where the winning conditions are disjunctions (or dually, conjunctions) of parity conditions; we call them generalized parity games. These winning conditions, while $\omega$-regular, arise naturally when considering fair simulation between parity automata, secure equilibria for parity conditions, and determinization of Rabin automata. We show that these games retain the computational complexity of Rabin and Streett conditions; i.e., they are NP-complete and co-NP-complete, respectively. The (co-)NP-hardness is proved for the special case of a conjunction/disjunction of two parity conditions, which is the case that arises in fair simulation and secure equilibria. However, considering these games as Rabin or Streett games is not optimal. We give an exposition of Zielonka's algorithm when specialized to this kind of games. The complexity of solving these games for $k$ parity objectives with $d$ parities, $n$ states, and $m$ edges is $O(n^{2 k d} \cdot m) \cdot \frac{(k\cdot d)!}{d!^k}$, as compared to $O(n^{2 k d} \cdot m) \cdot (k\cdot d)!$ when these games are solved as Rabin/Streett games. We also extend the subexponential algorithm for solving parity games recently introduced by Jurdzi{\'n}ski, Patterson, and Zwick to generalized parity games. The resulting complexity of solving generalized parity games is $n^{O(\sqrt{n})} \cdot \frac{(k\cdot d)!}{d!^k}$. As a corollary we obtain an improved algorithm for Rabin and Streett games with $d$ pairs, with time complexity $n^{O(\sqrt{n})} \cdot d!$.

---

BibTeX citation:

@techreport{Chatterjee:EECS-2006-144,
    Author= {Chatterjee, Krishnendu and Henzinger, Thomas A. and Piterman, Nir},
    Title= {Generalized Parity Games},
    Year= {2006},
    Month= {Nov},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-144.html},
    Number= {UCB/EECS-2006-144},
    Abstract= {We consider games where the winning conditions are disjunctions (or dually, conjunctions) of parity conditions; we call them generalized parity games. These winning conditions, while $\omega$-regular, arise naturally when considering fair simulation between parity automata, secure equilibria for parity conditions, and determinization of Rabin automata. We show that these games retain the computational complexity of Rabin and Streett conditions; i.e., they are NP-complete and co-NP-complete, respectively. The (co-)NP-hardness is proved for the special case of a conjunction/disjunction of two parity conditions, which is the case that arises in fair simulation and secure equilibria. However, considering these games as Rabin or Streett games is not optimal. We give an exposition of Zielonka's algorithm when specialized to this kind of games. The complexity of solving these games for $k$ parity objectives with $d$ parities, $n$ states, and $m$ edges is $O(n^{2 k d} \cdot m) \cdot \frac{(k\cdot d)!}{d!^k}$, as compared to $O(n^{2 k d} \cdot m) \cdot (k\cdot d)!$ when these games are solved as Rabin/Streett games. We also extend the subexponential algorithm for solving parity games recently introduced by Jurdzi{\'n}ski, Patterson, and Zwick to generalized parity games. The resulting complexity of solving generalized parity games is $n^{O(\sqrt{n})}  \cdot \frac{(k\cdot d)!}{d!^k}$. As a corollary we obtain an improved algorithm for Rabin and Streett games with $d$ pairs, with time complexity $n^{O(\sqrt{n})} \cdot d!$.},
}

EndNote citation:

%0 Report
%A Chatterjee, Krishnendu 
%A Henzinger, Thomas A. 
%A Piterman, Nir 
%T Generalized Parity Games
%I EECS Department, University of California, Berkeley
%D 2006
%8 November 8
%@ UCB/EECS-2006-144
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-144.html
%F Chatterjee:EECS-2006-144