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

Speaker(s)

Piotr Hofman

Affiliation

Bayreuth Universität

Date

Feb. 5, 2014, 2:15 p.m.

Room

room 5870

Title in Polish

Infinite-State Energy Games

Seminar

Seminar Automata Theory

---

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.

---