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, 12 s. ISBN 978-3-642-14161-4. doi:10.1007/978-3-642-14162-1_40.
Další formáty:   BibTeX LaTeX RIS
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
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 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 0302-9743
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
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 30. 4. 2014 05:23.
Anotace
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.
Anotace č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 VaVNázev: Formální metody pro analýzu a verifikaci komplexních systémů
Investor: Grantová agentura ČR, Standardní projekty
MSM0021622419, záměrNázev: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
1M0545, projekt VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumná centra (Národní program výzkumu)
VytisknoutZobrazeno: 21. 10. 2019 09:53