Energy games with perfect and imperfect information

Raffaella Gentilini

Università di Perugia

Games played on graphs are a powerful tool to reason on crucial issues arising in Logic, Formal Methods and Automata theory. In this talk we consider two player games with energy objectives, a quantitative objective targeting the design and synthesis of complex interactive systems under resource-constrained specifications. Beside their own interest in the context of resource-aware verification, energy games are one of the rare and intriguing combinatorial problems that lie in the complexity class NP and coNP, but are not known to be in P. We first provide an overview over the state-of- the-art algorithmics for energy games under the classic assumption of perfect information, where the players have complete knowledge on the history of the play. We then turn our attention to imperfect information energy games, suitable to capture the partial knowledge due to e.g. the presence of private variables or sensor with a poor accuracy.