The Complexity of Bidirected Reachability in Valence Systems
Moses Ganardi, Rupak Majumdar, Georg Zetzsche · 2022
Reachability problems in infinite-state systems are often subject to extremely high complexity. This motivates the investigation of efficient overapproximations, where we add transitions to obtain a system in which reachability can be decided more efficiently. We consider bidirected infinite-state systems, where for every transition there is a transition with opposite effect.