---
res:
  bibo_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 priorities, n states, and m edges is O(n(2kd) (.) m) (.) (k(.)d)!/ d!(k),
    as compared to O(n(2kd .) 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, Paterson, and Zwick to generalized parity games. The
    resulting complexity of solving generalized parity games is n(O(root n)) (.) (k(.)d)!/d!(k).
    As a corollary we obtain an improved ald!k gorithm for Rabin and Streett games
    with d pairs, with time complexity n(O(root n)) (.) d!.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Krishnendu Chatterjee
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Thomas A
      foaf_name: Thomas Henzinger
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
    orcid: 0000−0002−2985−7724
  - foaf_Person:
      foaf_givenName: Nir
      foaf_name: Piterman, Nir
      foaf_surname: Piterman
  bibo_doi: 10.1007/978-3-540-71389-0_12
  bibo_volume: 4423
  dct_date: 2007^xs_gYear
  dct_publisher: Springer@
  dct_title: Generalized parity games@
...