| Identifikační kód | RIV/00216224:14330/13:00080250 |
|---|
| Název v anglickém jazyce | Z-reachability Problem for Games on 2-dimensional Vector Addition Systems with States is in P |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2013 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 1 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Jakub Chaloupka (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 5376327) |
|---|
| Popis výsledku v anglickém jazyce | 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 fork > 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. |
|---|
| Klíčová slova oddělená středníkem | vector addition system with states; infinite games; zero-reachability problem |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.3233/FI-2013-798 |
|---|