Skip to Main content Skip to Navigation
New interface
Conference papers

Ideal Decompositions for Vector Addition Systems

Abstract : Vector addition systems, or equivalently Petri nets, are one of the most popular formal models for the representation and the analysis of parallel processes. Many problems for vector addition systems are known to be decidable thanks to the theory of well-structured transition systems. Indeed, vector addition systems with configurations equipped with the classical point-wise ordering are well-structured transition systems. Based on this observation, problems like coverability or termination can be proven decidable. However, the theory of well-structured transition systems does not explain the decidability of the reachability problem. In this presentation, we show that runs of vector addition systems can also be equipped with a well quasi-order. This observation provides a unified understanding of the data structures involved in solving many problems for vector addition systems, including the central reachability problem.
Document type :
Conference papers
Complete list of metadata
Contributor : Sylvain Schmitz Connect in order to contact the contributor
Submitted on : Thursday, February 18, 2016 - 3:55:28 PM
Last modification on : Saturday, June 25, 2022 - 7:44:16 PM



Jérôme Leroux, Sylvain Schmitz. Ideal Decompositions for Vector Addition Systems. STACS 2016 - 33rd Symposium on Theoretical Aspects of Computer Science, 2016, Orléans, France. pp.1--13, ⟨10.4230/LIPIcs.STACS.2016.1⟩. ⟨hal-01275991⟩



Record views