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

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Problém Z-dosažitelnosti ve hrách na dvoudimenzionálních vektorových aditivních systémech se stavy je v P
Autoři	CHALOUPKA Jakub
Rok publikování	2010
Druh	Článek ve sborníku
Konference	Reachability Problems
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	http://www.springerlink.com/content/w410q46u3g20qh84/
Doi	https://doi.org/10.1007/978-3-642-15349-5_7
Obor	Informatika
Klíčová slova	vector addition system with states; infinite games; zero-reachability problem
Popis	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.
Související projekty:	Vysoce paralelní a distribuované výpočetní systémy Verifikace a analýza velmi velkých počítačových systémů 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