Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/14846
Title: Minimal Coverability Set for Petri Nets: Karp and Miller Algorithm with Pruning
Authors: SERVAIS, Frederic 
Reynier, Pierre-Alain
Issue Date: 2013
Source: Fundamenta informaticae, 122 (1-2), p. 1-30
Abstract: This paper presents the Monotone-Pruning algorithm (MP) for computing the minimal coverability set of Petri nets. The original Karp and Miller algorithm (KM) unfolds the reachability graph of a Petri net and uses acceleration on branches to ensure termination. The MP algorithm improves the KM algorithm by adding pruning between branches of the tree. This idea was first introduced in the Minimal Coverability Tree algorithm (MCT), however it was recently shown to be incomplete. The MP algorithm can be viewed as the MCT algorithm with a slightly more aggressive pruning strategy which ensures completeness. Experimental results show that this algorithm is a strong improvement over the KM algorithm as it dramatically reduces the exploration tree.
Notes: Reprint Address: Reynier, PA (reprint author) - LIF, 163 Ave Luminy,Case 901, F-13288 Marseille 9, France. E-mail Addresses:pierre-alain.reynier@lif.univ-mrs.fr; frederic.servais@uhasselt.be
Keywords: Petri net; concurrency
Document URI: http://hdl.handle.net/1942/14846
Link to publication: http://www.mimuw.edu.pl/~fundam/FI/previous/abs122.html
ISSN: 0169-2968
e-ISSN: 1875-8681
DOI: 10.3233/FI-2013-781
ISI #: 000317266900002
Rights: COPYRIGHT © 2013 BY POLISH MATHEMATICAL SOCIETY
Category: A1
Type: Journal Contribution
Validations: ecoom 2014
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
hal.pdf352.91 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

7
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

7
checked on May 21, 2022

Page view(s)

56
checked on May 19, 2022

Download(s)

250
checked on May 19, 2022

Google ScholarTM

Check

Altmetric


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