Publication details
Z
-reachability Problem for Games on 2-dimensional Vector Addition Systems with States is in P
| Basic information | |
|---|---|
| Original title: | Z-reachability Problem for Games on 2-dimensional Vector Addition Systems with States is in P |
| Author: | Jakub Chaloupka |
| Further information | |
|---|---|
| Citation: | CHALOUPKA, Jakub. Z-reachability Problem for Games on 2-dimensional Vector Addition Systems with States is in P. In Reachability Problems. Berlin : Springer Berlin / Heidelberg, 2010. ISBN 978-3-642-15348-8, pp. 104-119. 2010, Brno. |
| Original language: | English |
| Field: | Informatika |
| Type: | Article in Proceedings |
| Keywords: | vector addition system with states; infinite games; zero-reachability problem |
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:
- Highly Parallel and Distributed Computing Systems
- Verification and Analysis of Large-Scale Computer Systems
- Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů
- Rozsáhlé výpočetní systémy: modely, aplikace a verifikace
