Reachability Games on Extended Vector Addition Systems with States

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BRÁZDIL Tomáš JANČAR Petr KUČERA Antonín

Year of publication 2010
Type Article in Proceedings
Conference Proceedings of 37th International Colloquium on Automata, Languages and Programming (ICALP 2010)
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-642-14162-1_40
Field Informatics
Keywords vector addition systems; infinite games; reachability
Description We consider two-player turn-based games with zero-reachability and zero-safety objectives generated by extended vector addition systems with states. Although the problem of deciding the winner in such games in undecidable in general, we identify several decidable and even tractable subcases of this problem obtained by restricting the number of counters and/or the sets of target configurations.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.