D 2010

Reachability Games on Extended Vector Addition Systems with States

BRÁZDIL, Tomáš, Petr JANČAR and Antonín KUČERA

Basic information

Original name

Reachability Games on Extended Vector Addition Systems with States

Authors

BRÁZDIL, Tomáš (203 Czech Republic, belonging to the institution), Petr JANČAR (203 Czech Republic) and Antonín KUČERA (203 Czech Republic, guarantor, belonging to the institution)
Abramsky, Gavoille, Kirchner, Meyer auf der Heide, Spirakis (Eds.).

Edition

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

Publisher

Springer

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

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

Publication form

printed version "print"

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/10:00065875

Organization unit

Faculty of Informatics

ISBN

978-3-642-14161-4

ISSN

DOI

UT WoS

000286344200040

Keywords in English

vector addition systems; infinite games; reachability

Tags

International impact
Změněno: 30/4/2014 05:23, RNDr. Pavel Šmerk, Ph.D.

Abstract

ORIG CZ

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.

In Czech

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.

Links

GAP202/10/1469, research and development project
Name: Formální metody pro analýzu a verifikaci komplexních systémů
Investor: Czech Science Foundation
MSM0021622419, plan (intention)
Name: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
1M0545, research and development project
Name: Institut Teoretické Informatiky
Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science