Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01176755
Contributor : Sylvain Schmitz <>
Submitted on : Tuesday, February 2, 2016 - 3:27:58 PM
Last modification on : Thursday, July 2, 2020 - 5:26:02 PM

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. RP 2015 - 9th International Workshop on Reachability Problems, Sep 2015, Warsaw, Poland. pp.1--13, ⟨10.1007/978-3-319-24537-9_8⟩. ⟨hal-01176755v2⟩

Share

Metrics

Record views

172

Files downloads

110