2010/02/12 by Tomǎš Brázdil, Tomas Brazdil, Petr Jančar +6 · 1 citation
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Formal Methods in Verification #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #cs.GT
paper · pdf · doi:10.48550/arxiv.1002.2557
26 pages
arxiv created 2010/02/12 · openalex publication_date 2010/02/12 · arxiv updated 2010/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 is 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.