--- _id: '3851' abstract: - lang: eng text: 'Energy parity games are infinite two-player turn-based games played on weighted graphs. The objective of the game combines a (qualitative) parity condition with the (quantitative) requirement that the sum of the weights (i.e., the level of energy in the game) must remain positive. Beside their own interest in the design and synthesis of resource-constrained omega-regular specifications, energy parity games provide one of the simplest model of games with combined qualitative and quantitative objective. Our main results are as follows: (a) exponential memory is sufficient and may be necessary for winning strategies in energy parity games; (b) the problem of deciding the winner in energy parity games can be solved in NP ∩ coNP; and (c) we give an algorithm to solve energy parity by reduction to energy games. We also show that the problem of deciding the winner in energy parity games is polynomially equivalent to the problem of deciding the winner in mean-payoff parity games, which can thus be solved in NP ∩ coNP. As a consequence we also obtain a conceptually simple algorithm to solve mean-payoff parity games.' alternative_title: - LNCS author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Laurent full_name: Doyen, Laurent last_name: Doyen citation: ama: 'Chatterjee K, Doyen L. Energy parity games. In: Vol 6199. Springer; 2010:599-610. doi:10.1007/978-3-642-14162-1_50' apa: 'Chatterjee, K., & Doyen, L. (2010). Energy parity games (Vol. 6199, pp. 599–610). Presented at the ICALP: Automata, Languages and Programming, 37th International Colloquium, Bordeaux, France: Springer. https://doi.org/10.1007/978-3-642-14162-1_50' chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Energy Parity Games,” 6199:599–610. Springer, 2010. https://doi.org/10.1007/978-3-642-14162-1_50. ieee: 'K. Chatterjee and L. Doyen, “Energy parity games,” presented at the ICALP: Automata, Languages and Programming, 37th International Colloquium, Bordeaux, France, 2010, vol. 6199, pp. 599–610.' ista: 'Chatterjee K, Doyen L. 2010. Energy parity games. ICALP: Automata, Languages and Programming, 37th International Colloquium, LNCS, vol. 6199, 599–610.' mla: Chatterjee, Krishnendu, and Laurent Doyen. Energy Parity Games. Vol. 6199, Springer, 2010, pp. 599–610, doi:10.1007/978-3-642-14162-1_50. short: K. Chatterjee, L. Doyen, in:, Springer, 2010, pp. 599–610. conference: end_date: 2010-07-10 location: Bordeaux, France name: ' ICALP: Automata, Languages and Programming, 37th International Colloquium' start_date: 2010-07-06 date_created: 2018-12-11T12:05:31Z date_published: 2010-09-10T00:00:00Z date_updated: 2023-02-23T11:06:35Z day: '10' department: - _id: KrCh doi: 10.1007/978-3-642-14162-1_50 external_id: arxiv: - '1001.5183' intvolume: ' 6199' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1001.5183 month: '09' oa: 1 oa_version: Preprint page: 599 - 610 publication_status: published publisher: Springer publist_id: '2330' quality_controlled: '1' related_material: record: - id: '2972' relation: later_version status: public scopus_import: 1 status: public title: Energy parity games type: conference user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87 volume: 6199 year: '2010' ...