pith. sign in

arxiv: 1002.2557 · v1 · submitted 2010-02-12 · 💻 cs.GT

Reachability Games on Extended Vector Addition Systems with States

Tomas Brazdil , Petr Jancar , Antonin Kucera This is my paper
classification 💻 cs.GT
keywords gamesadditionextendedproblemstatessystemsvectoralthough
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Energy mean-payoff games

    cs.GT 2019-07 unverdicted novelty 6.0

    Energy mean-payoff games have protagonist strategies that may require infinite memory (antagonist needs none), with polynomial-time decidability in the one-player case and co-NP membership plus explicit constructions ...