Infinite-State Energy Games

Prelegent(ci)

Piotr Hofman

Afiliacja

Bayreuth Universität

Termin

5 lutego 2014 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joined work with Parosh Aziz Abdulla, Mohamed Faouzi Atig, Richard Mayr, K. Narayan Kumar and Patrick Totzke

Seminarium

Seminarium „Teoria automatów”

---

Energy games are a well-studied class of
2-player turn based games on a finite graph
where transitions are labelled with integer vectors which represent
changes in a multidimensional resource (the energy). One player tries to keep the cumulative changes non-negative 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 one-counter automata.

Our main result is that energy games are decidable in the case where the game graph is induced by a one-counter machine and the energy is one-dimensional.
On the other hand, every further generalization is undecidable:
Energy games on one-counter machines with a 2-dimensional energy are undecidable, and energy games on pushdown automata are undecidable even if the energy is one-dimensional.

---