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

References to SciGraph publications

  • 1993. The minimal coverability graph for Petri nets in ADVANCES IN PETRI NETS 1993
  • 1987. A generalization of the procedure of karp and miller to well structured transition systems in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2009. Forward Analysis for WSTS, Part II: Complete WSTS in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 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 N04d6fb151a534d1ab2c4afc4bc421fed
    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 N44ba7ce0762248878006ceb5a186dce7
    13 schema:genre chapter
    14 schema:inLanguage en
    15 schema:isAccessibleForFree true
    16 schema:isPartOf Nacbc9ab63bd24ec5b67687880cfc6b64
    17 schema:name Minimal Coverability Set for Petri Nets: Karp and Miller Algorithm with Pruning
    18 schema:pagination 69-88
    19 schema:productId N4e6222c27c5c489c99e6204d01164868
    20 N653991ccfa6d44578c9ff44db5406859
    21 Nab80e60321d641d9af6e474f2a5c30e8
    22 schema:publisher N72512b83ea9b405ea6a4fbe37a305441
    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 Na7f5f066baf341eb9258db5a9df270a8
    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 N04d6fb151a534d1ab2c4afc4bc421fed rdf:first sg:person.015601635406.76
    33 rdf:rest N796c0d992be446deb70f060d6b9664e3
    34 N44ba7ce0762248878006ceb5a186dce7 rdf:first N7ca6e8e7837c4e9e9b031b3bd80a647a
    35 rdf:rest N4af3baae52d440c781e5c7f6c10df979
    36 N4af3baae52d440c781e5c7f6c10df979 rdf:first Nacc4264d1cb3466ead5da350318026bd
    37 rdf:rest rdf:nil
    38 N4e6222c27c5c489c99e6204d01164868 schema:name readcube_id
    39 schema:value ecf543841b0f4f64da01e7ebf688d0b8192596191cbc1da8031d8420388fef83
    40 rdf:type schema:PropertyValue
    41 N653991ccfa6d44578c9ff44db5406859 schema:name doi
    42 schema:value 10.1007/978-3-642-21834-7_5
    43 rdf:type schema:PropertyValue
    44 N72512b83ea9b405ea6a4fbe37a305441 schema:location Berlin, Heidelberg
    45 schema:name Springer Berlin Heidelberg
    46 rdf:type schema:Organisation
    47 N796c0d992be446deb70f060d6b9664e3 rdf:first sg:person.010673052277.08
    48 rdf:rest rdf:nil
    49 N7ca6e8e7837c4e9e9b031b3bd80a647a schema:familyName Kristensen
    50 schema:givenName Lars M.
    51 rdf:type schema:Person
    52 Na7f5f066baf341eb9258db5a9df270a8 schema:name Springer Nature - SN SciGraph project
    53 rdf:type schema:Organization
    54 Nab80e60321d641d9af6e474f2a5c30e8 schema:name dimensions_id
    55 schema:value pub.1049742642
    56 rdf:type schema:PropertyValue
    57 Nacbc9ab63bd24ec5b67687880cfc6b64 schema:isbn 978-3-642-21833-0
    58 978-3-642-21834-7
    59 schema:name Applications and Theory of Petri Nets
    60 rdf:type schema:Book
    61 Nacc4264d1cb3466ead5da350318026bd schema:familyName Petrucci
    62 schema:givenName Laure
    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)


    ...