Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [39 references]  Display  Hide  Download
Contributor : Sylvain Schmitz Connect in order to contact the contributor
Submitted on : Wednesday, June 21, 2017 - 8:41:15 PM
Last modification on : Wednesday, September 29, 2021 - 3:44:01 AM
Long-term archiving on: : Saturday, December 16, 2017 - 2:30:16 AM


Files produced by the author(s)





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⟩



Record views


Files downloads