Reachability Games on Extended Vector Addition Systems with States

BRÁZDIL, Tomáš, Petr JANČAR a Antonín KUČERA. Reachability Games on Extended Vector Addition Systems with States. Abramsky, Gavoille, Kirchner, Meyer auf der Heide, Spirakis (Eds.). In Proceedings of 37th International Colloquium on Automata, Languages and Programming (ICALP 2010). Berlin: Springer, 2010, s. 478-489. ISBN 978-3-642-14161-4. Dostupné z: https://dx.doi.org/10.1007/978-3-642-14162-1_40.

Základní údaje

Originální název

Reachability Games on Extended Vector Addition Systems with States

Autoři

BRÁZDIL, Tomáš (203 Česká republika, domácí), Petr JANČAR (203 Česká republika) a Antonín KUČERA (203 Česká republika, garant, domácí)
Abramsky, Gavoille, Kirchner, Meyer auf der Heide, Spirakis (Eds.).

Vydání

Berlin, Proceedings of 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), od s. 478-489, 12 s. 2010

Nakladatel

Springer

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/10:00065875

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-14161-4

ISSN

DOI

http://dx.doi.org/10.1007/978-3-642-14162-1_40

UT WoS

000286344200040

Klíčová slova anglicky

vector addition systems; infinite games; reachability

Příznaky

Mezinárodní význam

---

Anotace

V originále

We consider two-player turn-based games with zero-reachability and zero-safety objectives generated by extended vector addition systems with states. Although the problem of deciding the winner in such games in undecidable in general, we identify several decidable and even tractable subcases of this problem obtained by restricting the number of counters and/or the sets of target configurations.

Česky

V článku se zkoumají hry dvou hráčů na nekonečných grafech generovaných VASS systémy, kde cílem jednoho hráče je dosáhnout danou podmnožinu stavů a druhý hráč se tomu snaží zabránit. Tento problém je v plné obecnosti nerozhodnutelný, nicméně lze identifikovat některé zajímavé podpřípady, kdy se stavá rozhodnutelným.

---

Návaznosti

GAP202/10/1469, projekt VaV	Název: Formální metody pro analýzu a verifikaci komplexních systémů Investor: Grantová agentura ČR, Formální metody pro analýzu a verifikaci komplexních systémů
MSM0021622419, záměr	Název: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky