Please use this identifier to cite or link to this item: https://doi.org/10.3233/FI-2014-1002
Title: Old and new algorithms for minimal coverability sets
Authors: Valmari, A.
Hansen, H. 
Issue Date: 2014
Citation: Valmari, A., Hansen, H. (2014). Old and new algorithms for minimal coverability sets. Fundamenta Informaticae 131 (1) : 1-25. ScholarBank@NUS Repository. https://doi.org/10.3233/FI-2014-1002
Abstract: Many algorithms for computing minimal coverability sets for Petri nets prune futures. That is, if a newmarking strictly covers an old one, then not just the old marking but also some subset of its successor markings is discarded from search. In this publication, a simpler algorithm that lacks future pruning is presented and proven correct. Its performance is compared with future pruning. It is demonstrated, using examples, that neither approach is systematically better than the other. However, the simple algorithm has some attractive features. It never needs to re-construct pruned parts of the minimal coverability set. It automatically gives most of the advantage of future pruning, if the minimal coverability set is constructed in depth-first or most tokens first order, and if so-called history merging is applied. Some implementation aspects of minimal coverability set construction are also discussed. Some measurements are given to demonstrate the effect of construction order and other implementation aspects.
Source Title: Fundamenta Informaticae
URI: http://scholarbank.nus.edu.sg/handle/10635/128911
ISSN: 01692968
DOI: 10.3233/FI-2014-1002
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

5
checked on Aug 18, 2018

WEB OF SCIENCETM
Citations

5
checked on Jul 17, 2018

Page view(s)

11
checked on May 24, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.