Generalized parity games

K. Chatterjee, T.A. Henzinger, N. Piterman, in:, Springer, 2007, pp. 153–167.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Series Title
LNCS
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!.
Publishing Year
Date Published
2007-03-09
Acknowledgement
This research was supported in part by the Swiss National Science Foundation, and by the NSF grants CCR-0225610 and CCR-0234690.
Volume
4423
Page
153 - 167
Conference
FoSSaCS: Foundations of Software Science and Computation Structures
IST-REx-ID

Cite this

Chatterjee K, Henzinger TA, Piterman N. Generalized parity games. In: Vol 4423. Springer; 2007:153-167. doi:10.1007/978-3-540-71389-0_12
Chatterjee, K., Henzinger, T. A., & Piterman, N. (2007). Generalized parity games (Vol. 4423, pp. 153–167). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Springer. https://doi.org/10.1007/978-3-540-71389-0_12
Chatterjee, Krishnendu, Thomas A Henzinger, and Nir Piterman. “Generalized Parity Games,” 4423:153–67. Springer, 2007. https://doi.org/10.1007/978-3-540-71389-0_12.
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.
Chatterjee K, Henzinger TA, Piterman N. 2007. Generalized parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 4423. 153–167.
Chatterjee, Krishnendu, et al. Generalized Parity Games. Vol. 4423, Springer, 2007, pp. 153–67, doi:10.1007/978-3-540-71389-0_12.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar