Nie jesteś zalogowany |
Infinite-State Energy Games
- Prelegent(ci)
- Piotr Hofman
- Afiliacja
- Bayreuth Universität
- Termin
- 5 lutego 2014 14:15
- Pokój
- p. 5870
- 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.
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.
