---
_id: '3883'
abstract:
- lang: eng
  text: 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!.
acknowledgement: This research was supported in part by the Swiss National Science
  Foundation, and by the NSF grants CCR-0225610 and CCR-0234690.
alternative_title:
- LNCS
author:
- first_name: Krishnendu
  full_name: Krishnendu Chatterjee
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Thomas A
  full_name: Thomas Henzinger
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Nir
  full_name: Piterman, Nir
  last_name: Piterman
citation:
  ama: 'Chatterjee K, Henzinger TA, Piterman N. Generalized parity games. In: Vol
    4423. Springer; 2007:153-167. doi:<a href="https://doi.org/10.1007/978-3-540-71389-0_12">10.1007/978-3-540-71389-0_12</a>'
  apa: 'Chatterjee, K., Henzinger, T. A., &#38; Piterman, N. (2007). Generalized parity
    games (Vol. 4423, pp. 153–167). Presented at the FoSSaCS: Foundations of Software
    Science and Computation Structures, Springer. <a href="https://doi.org/10.1007/978-3-540-71389-0_12">https://doi.org/10.1007/978-3-540-71389-0_12</a>'
  chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Nir Piterman. “Generalized
    Parity Games,” 4423:153–67. Springer, 2007. <a href="https://doi.org/10.1007/978-3-540-71389-0_12">https://doi.org/10.1007/978-3-540-71389-0_12</a>.
  ieee: 'K. Chatterjee, T. A. Henzinger, and N. Piterman, “Generalized parity games,”
    presented at the FoSSaCS: Foundations of Software Science and Computation Structures,
    2007, vol. 4423, pp. 153–167.'
  ista: 'Chatterjee K, Henzinger TA, Piterman N. 2007. Generalized parity games. FoSSaCS:
    Foundations of Software Science and Computation Structures, LNCS, vol. 4423, 153–167.'
  mla: Chatterjee, Krishnendu, et al. <i>Generalized Parity Games</i>. Vol. 4423,
    Springer, 2007, pp. 153–67, doi:<a href="https://doi.org/10.1007/978-3-540-71389-0_12">10.1007/978-3-540-71389-0_12</a>.
  short: K. Chatterjee, T.A. Henzinger, N. Piterman, in:, Springer, 2007, pp. 153–167.
conference:
  name: 'FoSSaCS: Foundations of Software Science and Computation Structures'
date_created: 2018-12-11T12:05:41Z
date_published: 2007-03-09T00:00:00Z
date_updated: 2021-01-12T07:52:56Z
day: '09'
doi: 10.1007/978-3-540-71389-0_12
extern: 1
fulldoi: https://doi.org/10.1007/978-3-540-71389-0_12
intvolume: '      4423'
month: '03'
page: 153 - 167
publication_status: published
publisher: Springer
publist_id: '2287'
quality_controlled: 0
status: public
title: Generalized parity games
type: conference
volume: 4423
year: '2007'
...