Reachability in succinct one-counter games

We consider two-player games with reachability objectives played on transition systems of succinct one-counter machines, that is, machines where the counter is incremented or decremented by a value given in binary. We show that the reachability and counter reachability problems are equivalent, in contrast to non-succinct games and that all problems are EXPSPACE-complete.

Authors

• Paul Hunter

Keywords

No keywords are indexed for this paper.