Vector Addition System Reversible Reachability Problem

DOI10.1007/978-3-642-23217-6_22MaRDI QIDQ3090839zbMATH OpenOpenAlexFDO

Authors Jérôme Leroux

Publication date 2 September 2011

Published in CONCUR 2011 – Concurrency Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: The reachability problem for vector addition systems is a central problem of net theory. This problem is known to be decidable but the complexity is still unknown. Whereas the problem is EXPSPACE-hard, no elementary upper bounds complexity are known. In this paper we consider the reversible reachability problem. This problem consists to decide if two configurations are reachable one from each other, or equivalently if they are in the same strongly connected component of the reachability graph. We show that this problem is EXPSPACE-complete. As an application of the introduced materials we characterize the reversibility domains of a vector addition system.

Recommendations

• Vector addition system reversible reachability problem
• scientific article; zbMATH DE number 3878366
• Demystifying Reachability in Vector Addition Systems
• scientific article; zbMATH DE number 4092784
• Vector addition system reachability problem: a short self-contained proof
• Vector addition system reachability problem, a short self-contained proof
• scientific article; zbMATH DE number 7559504
• Rewriting systems for reachability in vector addition systems with pairs
• The Reachability Problem for Vector Addition System with One Zero-Test
• The Reachability Problem for Two-Dimensional Vector Addition Systems with States

Cites work

• scientific article; zbMATH DE number 3582425 (Why is no real title available?)
• scientific article; zbMATH DE number 1232238 (Why is no real title available?)
• scientific article; zbMATH DE number 559221 (Why is no real title available?)
• A structure to decide reachability in Petri nets
• The covering and boundedness problems for vector addition systems
• Vector addition system reachability problem, a short self-contained proof

Cited in

(10)

• Existence of home states in Petri nets is decidable
• The reachability problem for branching vector addition systems requires doubly-exponential space
• When reachability meets Grzegorczyk
• Vector addition system reversible reachability problem
• Co-finiteness and co-emptiness of reachability sets in vector addition systems with states
• Reversing Unbounded Petri Nets
• Advances in parameterized verification of population protocols
• Demystifying Reachability in Vector Addition Systems
• Slice closures of indexed languages and word equations with counting constraints
• Verification of population protocols

This page was built for publication: Vector Addition System Reversible Reachability Problem

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