Minimal Coverability Set for Petri Nets: Karp and Miller Algorithm with Pruning View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Pierre-Alain Reynier , Frédéric Servais

ABSTRACT

This paper presents the Monotone-Pruning algorithm (MP) for computing the minimal coverability set of Petri nets. The original Karp and Miller algorithm (K&M) unfolds the reachability graph of a Petri net and uses acceleration on branches to ensure termination. The MP algorithm improves the K&M algorithm by adding pruning between branches of the K&M 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 K&M algorithm. More... »

PAGES

69-88

Book

TITLE

Applications and Theory of Petri Nets

ISBN

978-3-642-21833-0
978-3-642-21834-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-21834-7_5

DOI

http://dx.doi.org/10.1007/978-3-642-21834-7_5

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1049742642


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Laboratoire d\u2019Informatique Fondamentale de Marseille", 
          "id": "https://www.grid.ac/institutes/grid.462848.4", 
          "name": [
            "LIF, Universit\u00e9 Aix-Marseille & CNRS, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Reynier", 
        "givenName": "Pierre-Alain", 
        "id": "sg:person.015601635406.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015601635406.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Universit\u00e9 Libre de Bruxelles", 
          "id": "https://www.grid.ac/institutes/grid.4989.c", 
          "name": [
            "Department of Computer & Decision Engineering (CoDE), ULB, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Servais", 
        "givenName": "Fr\u00e9d\u00e9ric", 
        "id": "sg:person.010673052277.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010673052277.08"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-02930-1_16", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004338576", 
          "https://doi.org/10.1007/978-3-642-02930-1_16"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-02930-1_16", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004338576", 
          "https://doi.org/10.1007/978-3-642-02930-1_16"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-56689-9_45", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005061806", 
          "https://doi.org/10.1007/3-540-56689-9_45"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-18088-5_43", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034273512", 
          "https://doi.org/10.1007/3-540-18088-5_43"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(69)80011-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052702842"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054110007180", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062897011"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "This paper presents the Monotone-Pruning algorithm (MP) for computing the minimal coverability set of Petri nets. The original Karp and Miller algorithm (K&M) unfolds the reachability graph of a Petri net and uses acceleration on branches to ensure termination. The MP algorithm improves the K&M algorithm by adding pruning between branches of the K&M 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 K&M algorithm.", 
    "editor": [
      {
        "familyName": "Kristensen", 
        "givenName": "Lars M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Petrucci", 
        "givenName": "Laure", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-21834-7_5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-21833-0", 
        "978-3-642-21834-7"
      ], 
      "name": "Applications and Theory of Petri Nets", 
      "type": "Book"
    }, 
    "name": "Minimal Coverability Set for Petri Nets: Karp and Miller Algorithm with Pruning", 
    "pagination": "69-88", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049742642"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-21834-7_5"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ecf543841b0f4f64da01e7ebf688d0b8192596191cbc1da8031d8420388fef83"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-21834-7_5", 
      "https://app.dimensions.ai/details/publication/pub.1049742642"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:58", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000369_0000000369/records_68971_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-21834-7_5"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21834-7_5'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21834-7_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21834-7_5'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21834-7_5'


 

This table displays all metadata directly associated to this object as RDF triples.

98 TRIPLES      23 PREDICATES      32 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-21834-7_5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd391e8d6292b4000854c1428a591fa5d
4 schema:citation sg:pub.10.1007/3-540-18088-5_43
5 sg:pub.10.1007/3-540-56689-9_45
6 sg:pub.10.1007/978-3-642-02930-1_16
7 https://doi.org/10.1016/s0022-0000(69)80011-5
8 https://doi.org/10.1142/s0129054110007180
9 schema:datePublished 2011
10 schema:datePublishedReg 2011-01-01
11 schema:description This paper presents the Monotone-Pruning algorithm (MP) for computing the minimal coverability set of Petri nets. The original Karp and Miller algorithm (K&M) unfolds the reachability graph of a Petri net and uses acceleration on branches to ensure termination. The MP algorithm improves the K&M algorithm by adding pruning between branches of the K&M 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 K&M algorithm.
12 schema:editor N207d1e8b70dd43c79f46dfe2ff677b2b
13 schema:genre chapter
14 schema:inLanguage en
15 schema:isAccessibleForFree true
16 schema:isPartOf N4ee7a0d395294f14b75a18c407596577
17 schema:name Minimal Coverability Set for Petri Nets: Karp and Miller Algorithm with Pruning
18 schema:pagination 69-88
19 schema:productId N4aec1bada6e542eaa1423d1224fa2776
20 N739ebdb4427c42fc95e342cc33d51a98
21 Nb0d764a5f48f420fb59fe0e4e1c73d80
22 schema:publisher Nc65affbd69054b3aa51b932e18e31638
23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049742642
24 https://doi.org/10.1007/978-3-642-21834-7_5
25 schema:sdDatePublished 2019-04-16T08:58
26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
27 schema:sdPublisher N640445da679243048c009a7fbff6307e
28 schema:url https://link.springer.com/10.1007%2F978-3-642-21834-7_5
29 sgo:license sg:explorer/license/
30 sgo:sdDataset chapters
31 rdf:type schema:Chapter
32 N207d1e8b70dd43c79f46dfe2ff677b2b rdf:first Nffcd36b3d5d54c74a85b287707aa3d5e
33 rdf:rest Nd7700c9cec364952a62f578ccaaebcbd
34 N4aec1bada6e542eaa1423d1224fa2776 schema:name doi
35 schema:value 10.1007/978-3-642-21834-7_5
36 rdf:type schema:PropertyValue
37 N4ee7a0d395294f14b75a18c407596577 schema:isbn 978-3-642-21833-0
38 978-3-642-21834-7
39 schema:name Applications and Theory of Petri Nets
40 rdf:type schema:Book
41 N640445da679243048c009a7fbff6307e schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 N739ebdb4427c42fc95e342cc33d51a98 schema:name readcube_id
44 schema:value ecf543841b0f4f64da01e7ebf688d0b8192596191cbc1da8031d8420388fef83
45 rdf:type schema:PropertyValue
46 Nb0d764a5f48f420fb59fe0e4e1c73d80 schema:name dimensions_id
47 schema:value pub.1049742642
48 rdf:type schema:PropertyValue
49 Nbd6dcefa7a1b492da3c6bcba92b620dc rdf:first sg:person.010673052277.08
50 rdf:rest rdf:nil
51 Nc52b201cd4164580b96d48a6045a0e74 schema:familyName Petrucci
52 schema:givenName Laure
53 rdf:type schema:Person
54 Nc65affbd69054b3aa51b932e18e31638 schema:location Berlin, Heidelberg
55 schema:name Springer Berlin Heidelberg
56 rdf:type schema:Organisation
57 Nd391e8d6292b4000854c1428a591fa5d rdf:first sg:person.015601635406.76
58 rdf:rest Nbd6dcefa7a1b492da3c6bcba92b620dc
59 Nd7700c9cec364952a62f578ccaaebcbd rdf:first Nc52b201cd4164580b96d48a6045a0e74
60 rdf:rest rdf:nil
61 Nffcd36b3d5d54c74a85b287707aa3d5e schema:familyName Kristensen
62 schema:givenName Lars M.
63 rdf:type schema:Person
64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
65 schema:name Information and Computing Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
68 schema:name Computation Theory and Mathematics
69 rdf:type schema:DefinedTerm
70 sg:person.010673052277.08 schema:affiliation https://www.grid.ac/institutes/grid.4989.c
71 schema:familyName Servais
72 schema:givenName Frédéric
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010673052277.08
74 rdf:type schema:Person
75 sg:person.015601635406.76 schema:affiliation https://www.grid.ac/institutes/grid.462848.4
76 schema:familyName Reynier
77 schema:givenName Pierre-Alain
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015601635406.76
79 rdf:type schema:Person
80 sg:pub.10.1007/3-540-18088-5_43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034273512
81 https://doi.org/10.1007/3-540-18088-5_43
82 rdf:type schema:CreativeWork
83 sg:pub.10.1007/3-540-56689-9_45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005061806
84 https://doi.org/10.1007/3-540-56689-9_45
85 rdf:type schema:CreativeWork
86 sg:pub.10.1007/978-3-642-02930-1_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004338576
87 https://doi.org/10.1007/978-3-642-02930-1_16
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1016/s0022-0000(69)80011-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052702842
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1142/s0129054110007180 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062897011
92 rdf:type schema:CreativeWork
93 https://www.grid.ac/institutes/grid.462848.4 schema:alternateName Laboratoire d’Informatique Fondamentale de Marseille
94 schema:name LIF, Université Aix-Marseille & CNRS, France
95 rdf:type schema:Organization
96 https://www.grid.ac/institutes/grid.4989.c schema:alternateName Université Libre de Bruxelles
97 schema:name Department of Computer & Decision Engineering (CoDE), ULB, Belgium
98 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...