Ideal Decompositions for Vector Addition Systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Ideal Decompositions for Vector Addition Systems

Résumé

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.
Fichier non déposé

Dates et versions

hal-01275991 , version 1 (18-02-2016)

Identifiants

Citer

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⟩
347 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More