The Ideal View on Rackoff's Coverability Technique

Abstract : 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.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/hal-01176755
Contributor : Sylvain Schmitz <>
Submitted on : Wednesday, June 21, 2017 - 8:41:15 PM
Last modification on : Thursday, January 11, 2018 - 6:20:14 AM
Document(s) archivé(s) le : Saturday, December 16, 2017 - 2:30:16 AM

File

article.pdf
Files produced by the author(s)

Licence


Copyright

Identifiers

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-01176755v3〉

Share

Metrics

Record views

215

Files downloads

112