Projects per year
Abstract
Energy games are a wellstudied class of 2player turnbased games on a finite graph where transitions are labeled with integer vectors which represent changes in a multidimensional resource (the energy). One player tries to keep the cumulative changes nonnegative in every component while the other tries to frustrate this. We consider generalized energy games played on infinite game graphs induced by pushdown automata (modelling recursion) or their subclass of onecounter automata. Our main result is that energy games are decidable in the case where the game graph is induced by a onecounter automaton and the energy is onedimensional. On the other hand, every further generalization is undecidable: Energy games on onecounter automata with a 2dimensional energy are undecidable, and energy games on pushdown automata are undecidable even if the energy is onedimensional. Furthermore, we show that energy games and simulation games are interreducible, and thus we additionally obtain several new (un)decidability results for the problem of checking simulation preorder between pushdown automata and vector addition systems.
Original language  English 

Title of host publication  CSLLICS '14 Proceedings of the Joint Meeting of the TwentyThird EACSL Annual Conference on Computer Science Logic (CSL) and the TwentyNinth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 
Publisher  ACM 
Number of pages  11 
ISBN (Print)  9781450328869 
DOIs  
Publication status  Published  3 May 2014 
Event  LICS  Vienna, Austria Duration: 14 Jul 2014 → 18 Jul 2014 
Conference
Conference  LICS 

Country/Territory  Austria 
City  Vienna 
Period  14/07/14 → 18/07/14 
Fingerprint
Dive into the research topics of 'InfiniteState Energy Games'. Together they form a unique fingerprint.Projects
 1 Finished
Profiles

Richard Mayr
 School of Informatics  Reader
 Laboratory for Foundations of Computer Science
 Foundations of Computation
Person: Academic: Research Active