On the Complexity of Counter Reachability Games

DOI10.1007/978-3-642-41036-9_18MaRDI QIDQ5168525zbMATH OpenOpenAlexFDO

Authors J. Reichert

Publication date 7 July 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.5004

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Games involving graphs (91A43)

Abstract: Counter reachability games are played by two players on a graph with labelled edges. Each move consists in picking an edge from the current location and adding its label to a counter vector. The objective is to reach a given counter value in a given location. We distinguish three semantics for counter reachability games, according to what happens when a counter value would become negative: the edge is either disabled, or enabled but the counter value becomes zero, or enabled. We consider the problem of deciding the winner in counter reachability games and show that, in most cases, it has the same complexity under all semantics. Surprisingly, under one semantics, the complexity in dimension one depends on whether the objective value is zero or any other integer.

Recommendations

• Reachability in succinct one-counter games
• Reachability games and parity games
• The complexity of recursion theoretic games
• On Reachability Games of Ordinal Length
• The complexity of reachability in randomized sabotage games
• On Complexity of Ehrenfeucht-Fraïssé Games
• On complexity of Ehrenfeucht-Fraïssé games

Cited in

(11)

• Reachability in succinct one-counter games
• On robot games of degree two
• Games for counting abstractions
• On the complexity of counter reachability games
• Reachability games on extended vector addition systems with states
• scientific article; zbMATH DE number 1948167 (Why is no real title available?)
• Reachability switching games
• Complexity of Unordered CNF Games
• The complexity of recursion theoretic games
• On higher-order reachability games vs may reachability
• Two-player boundedness counter games

This page was built for publication: On the Complexity of Counter Reachability Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5168525)