Ontology type: schema:Chapter Open Access: True
2011
AUTHORSPierre-Alain Reynier , Frédéric Servais
ABSTRACTThis 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... »
PAGES69-88
Applications and Theory of Petri Nets
ISBN
978-3-642-21833-0
978-3-642-21834-7
http://scigraph.springernature.com/pub.10.1007/978-3-642-21834-7_5
DOIhttp://dx.doi.org/10.1007/978-3-642-21834-7_5
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1049742642
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
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