The Library
The ideal view on Rackoff's coverability technique
Tools
Tools
Tools
Lazic, Ranko and Schmitz, Sylvain (2015) The ideal view on Rackoff's coverability technique. In: 9th International Workshop on Reachability Problems, Warsaw, Poland, 21-23 Sep 2015. Published in: Reachability Problems : 9th International Workshop, RP 2015, Warsaw, Poland, September 21-23, 2015, Proceedings, 9328 pp. 76-88. ISSN 0302-9743. doi:10.1007/978-3-319-24537-9_8
|
PDF
WRAP_0070379-cs-061015-lncs.pdf - Accepted Version - Requires a PDF viewer. Download (497Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-319-24537-9_8
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.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||
| Divisions: | Faculty of Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Vector analysis, Algorithms | ||||||
| Series Name: | Lecture Notes in Computer Science | ||||||
| Journal or Publication Title: | Reachability Problems : 9th International Workshop, RP 2015, Warsaw, Poland, September 21-23, 2015, Proceedings | ||||||
| Publisher: | Springer | ||||||
| ISSN: | 0302-9743 | ||||||
| Official Date: | 1 October 2015 | ||||||
| Dates: |
|
||||||
| Volume: | 9328 | ||||||
| Page Range: | pp. 76-88 | ||||||
| DOI: | 10.1007/978-3-319-24537-9_8 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Funder: | Engineering and Physical Sciences Research Council (EPSRC), Leverhulme Trust (LT) | ||||||
| Grant number: | EP/M011801/1 (EPSRC), VP1-2014-041 (LT) | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 9th International Workshop on Reachability Problems | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Warsaw, Poland | ||||||
| Date(s) of Event: | 21-23 Sep 2015 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
