---
_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'
...