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

CHALOUPKA, Jakub. Z-reachability Problem for Games on 2-dimensional Vector Addition Systems with States is in P. Fundamenta Informaticae. Polsko: IOS Press, Nizozemí, 2013, roč. 123, č. 1, s. 15-42. ISSN 0169-2968. Dostupné z: https://dx.doi.org/10.3233/FI-2013-798.

Základní údaje

Originální název

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

Autoři

CHALOUPKA, Jakub (203 Česká republika, garant, domácí)

Vydání

Fundamenta Informaticae, Polsko, IOS Press, Nizozemí, 2013, 0169-2968

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.479

Kód RIV

RIV/00216224:14330/13:00080250

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.3233/FI-2013-798

UT WoS

000317267500003

Klíčová slova anglicky

vector addition system with states; infinite games; zero-reachability problem

---

Anotace

V originále

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. Brazdil, Jancar, and Kucera (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.