Citation
Krishnendu Chatterjee, Tom Henzinger, Nir Piterman. "Generalized Parity Games". FOSSACS 07, March, 2007.

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} * m) * (k* d)! /(d! ^k ), as compared to O(n ^{2 k d} * m) * (k* d)! when these games are solved as Rabin/Streett games. We also extend the subexponential algorithm for solving parity games recently introduced by Jurdzinski, Patterson, and Zwick to generalized parity games. The resulting complexity of solving generalized parity games is n ^O(sqrt{n}) * (k* 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}) * d!.

Electronic downloads

• main.ps · application/postscript · 445 kbytes
• Chatterjee_Henginger_Piterman_GeneralizedParityGames_FOSSACS07.pdf · application/pdf · 216 kbytes. (PDF version of main.ps, converted on 6/4/2008.)

• HTML

  Krishnendu Chatterjee, Tom Henzinger, Nir Piterman. <a
  href="http://chess.eecs.berkeley.edu/pubs/241.html"
  >Generalized Parity Games</a>, FOSSACS 07, March,
  2007.

• Plain text

  Krishnendu Chatterjee, Tom Henzinger, Nir Piterman.
  "Generalized Parity Games". FOSSACS 07, March,
  2007.

• BibTeX

  @inproceedings{ChatterjeeHenzingerPiterman07_GeneralizedParityGames,
      author = {Krishnendu Chatterjee and Tom Henzinger and Nir
                Piterman},
      title = {Generalized Parity Games},
      booktitle = {FOSSACS 07},
      month = {March},
      year = {2007},
      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
                <sup> 2 k d </sup> * m) * (k* d)! /(d!<sup> k
                </sup>), as compared to O(n <sup> 2 k d </sup> *
                m) * (k* d)! when these games are solved as
                Rabin/Streett games. We also extend the
                subexponential algorithm for solving parity games
                recently introduced by Jurdzinski, Patterson, and
                Zwick to generalized parity games. The resulting
                complexity of solving generalized parity games is
                n <sup>O(sqrt{n}) </sup> * (k* d)!/(d! <sup> k
                </sup>). As a corollary we obtain an improved
                algorithm for Rabin and Streett games with d
                pairs, with time complexity n^<sup> O(sqrt{n})
                </sup> * d!. },
      URL = {http://chess.eecs.berkeley.edu/pubs/241.html}
  }
  

Posted by Krishnendu Chatterjee, PhD on 13 May 2007.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.