Energy parity games

K. Chatterjee, L. Doyen, Theoretical Computer Science 458 (2012) 49–60.

Download
OA 351.27 KB

Journal Article | Published | English
Author
Department
Abstract
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 objectives. 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 logspace-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.
Publishing Year
Date Published
2012-11-02
Journal Title
Theoretical Computer Science
Volume
458
Page
49 - 60
IST-REx-ID

Cite this

Chatterjee K, Doyen L. Energy parity games. Theoretical Computer Science. 2012;458:49-60. doi:10.1016/j.tcs.2012.07.038
Chatterjee, K., & Doyen, L. (2012). Energy parity games. Theoretical Computer Science, 458, 49–60. https://doi.org/10.1016/j.tcs.2012.07.038
Chatterjee, Krishnendu, and Laurent Doyen. “Energy Parity Games.” Theoretical Computer Science 458 (2012): 49–60. https://doi.org/10.1016/j.tcs.2012.07.038.
K. Chatterjee and L. Doyen, “Energy parity games,” Theoretical Computer Science, vol. 458, pp. 49–60, 2012.
Chatterjee K, Doyen L. 2012. Energy parity games. Theoretical Computer Science. 458, 49–60.
Chatterjee, Krishnendu, and Laurent Doyen. “Energy Parity Games.” Theoretical Computer Science, vol. 458, Elsevier, 2012, pp. 49–60, doi:10.1016/j.tcs.2012.07.038.
All files available under the following license(s):
Creative Commons License:
CC-BY-NC-NDCreative Commons Attribution-NonCommercial-NoDerivs (CC BY-NC-ND 4.0)
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2019-02-06T11:56:22Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar