The Ideal View on Rackoff's Coverability Technique - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

The Ideal View on Rackoff's Coverability Technique

Résumé

Well-structured transition systems form a large class of infinite-state systems, for which safety verification is decidable thanks to a generic backward coverability algorithm. However, for several classes of systems, the generic upper bounds one can extract from the algorithm are far from optimal. In particular, in the case of vector addition systems (VAS) and several of their extensions, the known tight upper bounds were rather derived thanks to ad-hoc arguments based on Rackoff’s small witness property. We show how to derive the same bounds directly on the computations of the VAS instantiation of the generic backward coverability algorithm. This relies on a dual view of the algorithm using ideal decompositions of downwards-closed sets, which exhibits a key structural invariant in the VAS case. This reasoning offers a uniform setting for all well-structured transition systems, including branching ones, and we further apply it to several VAS extensions: we derive optimal upper bounds for coverability in branching and alternating VAS, matching the previously known results from the literature.
Fichier principal
Vignette du fichier
article.pdf (508.69 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01176755 , version 1 (15-07-2015)
hal-01176755 , version 2 (02-02-2016)
hal-01176755 , version 3 (21-06-2017)

Licence

Copyright (Tous droits réservés)

Identifiants

Citer

Ranko Lazić, Sylvain Schmitz. The Ideal View on Rackoff's Coverability Technique. RP 2015 - 9th International Workshop on Reachability Problems, Sep 2015, Warsaw, Poland. pp.1--13, ⟨10.1007/978-3-319-24537-9_8⟩. ⟨hal-01176755v3⟩
482 Consultations
518 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More