Z-reachability Problem for Games on 2-dimensional Vector Addition Systems with States is in P

Investor logo
Investor logo

Warning

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

CHALOUPKA Jakub

Year of publication 2010
Type Article in Proceedings
Conference Reachability Problems
MU Faculty or unit

Faculty of Informatics

Citation
Web http://www.springerlink.com/content/w410q46u3g20qh84/
Doi http://dx.doi.org/10.1007/978-3-642-15349-5_7
Field Informatics
Keywords vector addition system with states; infinite games; zero-reachability problem
Description We consider a two-player infinite game with zero-reachability objectives played on a 2-dimensional vector addition system with states (VASS), the states of which are divided between the two players. Brázdil, Jančar, and Kučera (2010) have shown that for k > 0, deciding the winner in a game on k-dimensional VASS is in (k-1)-EXPTIME. In this paper, we show that, for k = 2, the problem is in P, and thus improve the EXPTIME upper bound.
Related projects:

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

More info