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

https://hal.inria.fr/hal-01176755
Contributor : Sylvain Schmitz <>
Submitted on : Wednesday, July 15, 2015 - 6:18:14 PM
Last modification on : Thursday, July 2, 2020 - 5:26:02 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 6:01:49 AM

File

lncs.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-01176755v1⟩

Share

Metrics

Record views

149

Files downloads

121