Abstract
Many algorithms for computing minimal coverability sets for Petri nets prune futures. That is, if a new marking strictly covers an old one, then not just the old marking but also some subset of its subsequent markings is discarded from search. In this publication, a simpler algorithm that lacks future pruning is presented and proven correct. Then 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. If the minimal coverability set is constructed in depth-first or most tokens first order, and if so-called history merging is applied, then most of the advantage of future pruning is automatic. Some implementation aspects of minimal coverability set construction are also discussed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Finkel, A.: The Minimal Coverability Graph for Petri Nets. In: Rozenberg, G. (ed.) APN 1993. LNCS, vol. 674, pp. 210–243. Springer, Heidelberg (1993)
Finkel, A., Geeraerts, G., Raskin, J.-F., Van Begin, L.: A counter-example to the minimal coverability tree algorithm. Technical Report 535, Universite Libre de Bruxelles (2005)
Geeraerts, G., Raskin, J.-F., Van Begin, L.: On the efficient computation of the minimal coverability set of Petri nets. International Journal of Foundations of Computer Science 21(2), 135–165 (2010)
Karp, R.M., Miller, R.E.: Parallel program schemata. Journal of Computer and System Sciences 3(2), 147–195 (1969)
König, B., Koziura, V.: Incremental construction of coverability graphs. Information Processing Letters 103(5), 203–209 (2007)
Reynier, P.-A., Servais, F.: Minimal Coverability Set for Petri Nets: Karp and Miller Algorithm with Pruning. In: Kristensen, L.M., Petrucci, L. (eds.) PETRI NETS 2011. LNCS, vol. 6709, pp. 69–88. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Valmari, A., Hansen, H. (2012). Old and New Algorithms for Minimal Coverability Sets. In: Haddad, S., Pomello, L. (eds) Application and Theory of Petri Nets. PETRI NETS 2012. Lecture Notes in Computer Science, vol 7347. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31131-4_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-31131-4_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31130-7
Online ISBN: 978-3-642-31131-4
eBook Packages: Computer ScienceComputer Science (R0)