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

Logo poskytovatele
Logo poskytovatele

Varování

Publikace nespadá pod Fakultu sportovních studií, 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 http://dx.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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info