Reachability Games on Extended Vector Addition Systems with States

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	BRÁZDIL Tomáš JANČAR Petr KUČERA Antonín
Rok publikování	2010
Druh	Článek ve sborníku
Konference	Proceedings of 37th International Colloquium on Automata, Languages and Programming (ICALP 2010)
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Doi	http://dx.doi.org/10.1007/978-3-642-14162-1_40
Obor	Informatika
Klíčová slova	vector addition systems; infinite games; reachability
Popis	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.
Související projekty:	Institut Teoretické Informatiky Vysoce paralelní a distribuované výpočetní systémy Formální metody pro analýzu a verifikaci komplexních systémů