The Ideal View on Rackoff's Coverability Technique

Abstract : Rackoff's small witness property for the coverability problem is the standard means to prove tight upper bounds in vector addition systems (VAS) and many extensions. 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. The same reasoning readily generalises to several VAS extensions.
Type de document :
Communication dans un congrès
Mikołaj Bojańczyk; Sławomir Lasota; Igor Potapov. RP 2015 - 9th International Workshop on Reachability Problems, Sep 2015, Warsaw, Poland. Springer, 9328, pp.1--13, Lecture Notes in Computer Science. <10.1007/978-3-319-24537-9_8>
Liste complète des métadonnées

https://hal.inria.fr/hal-01176755
Contributeur : Sylvain Schmitz <>
Soumis le : mardi 2 février 2016 - 15:27:58
Dernière modification le : vendredi 17 février 2017 - 16:15:15

Fichier

article.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

Citation

Ranko Lazić, Sylvain Schmitz. The Ideal View on Rackoff's Coverability Technique. Mikołaj Bojańczyk; Sławomir Lasota; Igor Potapov. RP 2015 - 9th International Workshop on Reachability Problems, Sep 2015, Warsaw, Poland. Springer, 9328, pp.1--13, Lecture Notes in Computer Science. <10.1007/978-3-319-24537-9_8>. <hal-01176755v2>

Partager

Métriques

Consultations de
la notice

146

Téléchargements du document

86