Leveraging polyhedral reductions for solving Petri net reachability problems - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Article Dans Une Revue International Journal on Software Tools for Technology Transfer Année : 2023

Leveraging polyhedral reductions for solving Petri net reachability problems

Résumé

We propose a new method that takes advantage of structural reductions to accelerate the verification of reachability properties on Petri nets. Our approach relies on a state space abstraction, called polyhedral abstraction, which involves a combination between structural reductions and sets of linear arithmetic constraints between the marking of places. We propose a new data-structure, called a Token Flow Graph (TFG), that captures the particular structure of constraints occurring in polyhedral abstractions. We leverage TFGs to efficiently solve two reachability problems: first to check the reachability of a given marking; then to compute the concurrency relation of a net, that is all pairs of places that can be marked together in some reachable marking. Our algorithms are implemented in a tool, called Kong, that we evaluate on a large collection of models used during the 2020 edition of the Model Checking Contest. Our experiments show that the approach works well, even when a moderate amount of reductions applies.
Fichier principal
Vignette du fichier
paper.pdf (956.09 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03973463 , version 1 (04-02-2023)

Identifiants

Citer

Nicolas Amat, Silvano Dal Zilio, Didier Le Botlan. Leveraging polyhedral reductions for solving Petri net reachability problems. International Journal on Software Tools for Technology Transfer, 2023, 25, pp.95-114. ⟨10.1007/s10009-022-00694-8⟩. ⟨hal-03973463⟩
25 Consultations
11 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More