Petri net models for algebraic theories of concurrency View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1987

AUTHORS

Rob van Glabbeek , Frits Vaandrager

ABSTRACT

In this paper we discuss the issue of interleaving semantics versus True concurrency in an algebraic setting. We present various equivalence notions on Petri nets which can be used in the construction of algebraic models:(a) the occurrence net equivalence of Nielsen, Plotkin & Winskel; (b) bisimulation equivalence, which leads to a model which is isomorphic to the graph model of Baeten, Bergstra & Klop; (c) the concurrent bisimulation equivalence, which is also described by Nielsen & Thiagarajan, and Goltz; (d) partial order equivalences which are inspired by work of Pratt, and Boudol & Castellani. A central role in the paper will be played by the notion of real-time consistency. We show that, besides occurrence net equivalence, none of the equivalences mentioned above (including the partial order equivalences!) is real-time consistent. Therefore we introduce the notion of ST-bisimulation equivalence, which is real-time consistent. Moreover a complete proof system will be presented for those finite ST-bisimulation processes in which no action can occur concurrently with itself. More... »

PAGES

224-242

References to SciGraph publications

  • 1984. On the relationship of CCS and petri nets in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2005-10-22. Event structure semantics for CCS and related languages in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1984. A new definition of morphism on Petri nets in STACS 84
  • 1986. Some equivalence notions for concurrent systems. An overview in ADVANCES IN PETRI NETS 1985
  • 1985. Modelling scheduling problems with timed petri nets in ADVANCES IN PETRI NETS 1984
  • 1987. On the semantics of concurrency: Partial orders and transition systems in TAPSOFT '87
  • 1985. Semantics of concurrent systems: A modular fixed-point trace approach in ADVANCES IN PETRI NETS 1984
  • 1986. Petri nets: Basic notions, structure, behaviour in CURRENT TRENDS IN CONCURRENCY
  • 1986-02. Modeling concurrency with partial orders in INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING
  • 1984. Degrees of non-determinism and concurrency: A Petri net view in FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • Book

    TITLE

    PARLE Parallel Architectures and Languages Europe

    ISBN

    978-3-540-17945-0
    978-3-540-47181-3

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-17945-3_13

    DOI

    http://dx.doi.org/10.1007/3-540-17945-3_13

    DIMENSIONS

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


    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": "Centrum Wiskunde and Informatica", 
              "id": "https://www.grid.ac/institutes/grid.6054.7", 
              "name": [
                "Centre for Mathematics and Computer Science, P.O. Box 4079, 1009 AB\u00a0Amsterdam, The Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "van Glabbeek", 
            "givenName": "Rob", 
            "id": "sg:person.010555433417.04", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555433417.04"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Centrum Wiskunde and Informatica", 
              "id": "https://www.grid.ac/institutes/grid.6054.7", 
              "name": [
                "Centre for Mathematics and Computer Science, P.O. Box 4079, 1009 AB\u00a0Amsterdam, The Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Vaandrager", 
            "givenName": "Frits", 
            "id": "sg:person.0765460367.38", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0765460367.38"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bfb0016222", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001018251", 
              "https://doi.org/10.1007/bfb0016222"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0012800", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006383355", 
              "https://doi.org/10.1007/bfb0012800"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0012800", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006383355", 
              "https://doi.org/10.1007/bfb0012800"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-13345-3_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022331272", 
              "https://doi.org/10.1007/3-540-13345-3_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(85)90088-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022391759"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(85)90088-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022391759"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-12920-0_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023917668", 
              "https://doi.org/10.1007/3-540-12920-0_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-17660-8_52", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028712016", 
              "https://doi.org/10.1007/3-540-17660-8_52"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-15204-0_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033761956", 
              "https://doi.org/10.1007/3-540-15204-0_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-15204-0_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034306316", 
              "https://doi.org/10.1007/3-540-15204-0_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01379149", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035171005", 
              "https://doi.org/10.1007/bf01379149"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01379149", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035171005", 
              "https://doi.org/10.1007/bf01379149"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(81)90112-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035972534"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0027048", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039262993", 
              "https://doi.org/10.1007/bfb0027048"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-13883-8_66", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047492704", 
              "https://doi.org/10.1007/3-540-13883-8_66"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.7146/dpb.v6i78.7691", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1073611461"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1987", 
        "datePublishedReg": "1987-01-01", 
        "description": "In this paper we discuss the issue of interleaving semantics versus True concurrency in an algebraic setting. We present various equivalence notions on Petri nets which can be used in the construction of algebraic models:(a) the occurrence net equivalence of Nielsen, Plotkin & Winskel; (b) bisimulation equivalence, which leads to a model which is isomorphic to the graph model of Baeten, Bergstra & Klop; (c) the concurrent bisimulation equivalence, which is also described by Nielsen & Thiagarajan, and Goltz; (d) partial order equivalences which are inspired by work of Pratt, and Boudol & Castellani. A central role in the paper will be played by the notion of real-time consistency. We show that, besides occurrence net equivalence, none of the equivalences mentioned above (including the partial order equivalences!) is real-time consistent. Therefore we introduce the notion of ST-bisimulation equivalence, which is real-time consistent. Moreover a complete proof system will be presented for those finite ST-bisimulation processes in which no action can occur concurrently with itself.", 
        "editor": [
          {
            "familyName": "Bakker", 
            "givenName": "J. W.", 
            "type": "Person"
          }, 
          {
            "familyName": "Nijman", 
            "givenName": "A. J.", 
            "type": "Person"
          }, 
          {
            "familyName": "Treleaven", 
            "givenName": "P. C.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-17945-3_13", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-17945-0", 
            "978-3-540-47181-3"
          ], 
          "name": "PARLE Parallel Architectures and Languages Europe", 
          "type": "Book"
        }, 
        "name": "Petri net models for algebraic theories of concurrency", 
        "pagination": "224-242", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-17945-3_13"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "23792f3d05c1ffe8e3f6853de43cfe8ed4837be4787133d11fc69d5428f637a8"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1007447453"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-17945-3_13", 
          "https://app.dimensions.ai/details/publication/pub.1007447453"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T19:07", 
        "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/0000000001_0000000264/records_8684_00000247.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-17945-3_13"
      }
    ]
     

    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/3-540-17945-3_13'

    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/3-540-17945-3_13'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-17945-3_13'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-17945-3_13'


     

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

    131 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-17945-3_13 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N4b7e5d8f8e5a43f298bd3a9b5190a628
    4 schema:citation sg:pub.10.1007/3-540-12920-0_13
    5 sg:pub.10.1007/3-540-13345-3_18
    6 sg:pub.10.1007/3-540-13883-8_66
    7 sg:pub.10.1007/3-540-15204-0_20
    8 sg:pub.10.1007/3-540-15204-0_5
    9 sg:pub.10.1007/3-540-17660-8_52
    10 sg:pub.10.1007/bf01379149
    11 sg:pub.10.1007/bfb0012800
    12 sg:pub.10.1007/bfb0016222
    13 sg:pub.10.1007/bfb0027048
    14 https://doi.org/10.1016/0304-3975(81)90112-2
    15 https://doi.org/10.1016/0304-3975(85)90088-x
    16 https://doi.org/10.7146/dpb.v6i78.7691
    17 schema:datePublished 1987
    18 schema:datePublishedReg 1987-01-01
    19 schema:description In this paper we discuss the issue of interleaving semantics versus True concurrency in an algebraic setting. We present various equivalence notions on Petri nets which can be used in the construction of algebraic models:(a) the occurrence net equivalence of Nielsen, Plotkin & Winskel; (b) bisimulation equivalence, which leads to a model which is isomorphic to the graph model of Baeten, Bergstra & Klop; (c) the concurrent bisimulation equivalence, which is also described by Nielsen & Thiagarajan, and Goltz; (d) partial order equivalences which are inspired by work of Pratt, and Boudol & Castellani. A central role in the paper will be played by the notion of real-time consistency. We show that, besides occurrence net equivalence, none of the equivalences mentioned above (including the partial order equivalences!) is real-time consistent. Therefore we introduce the notion of ST-bisimulation equivalence, which is real-time consistent. Moreover a complete proof system will be presented for those finite ST-bisimulation processes in which no action can occur concurrently with itself.
    20 schema:editor N8b83bfc94c5747bea6286d0009da2787
    21 schema:genre chapter
    22 schema:inLanguage en
    23 schema:isAccessibleForFree false
    24 schema:isPartOf N59c48ba94ab64a59afcc4787f0c1a3b8
    25 schema:name Petri net models for algebraic theories of concurrency
    26 schema:pagination 224-242
    27 schema:productId N5cef2c121519413081d22503837b89f3
    28 Ne452928802bb49979f168965f6a8b9ce
    29 Nee64c25a19834367a6a03029be345f7e
    30 schema:publisher N74da07b261aa46a98707eec5753aa8bb
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007447453
    32 https://doi.org/10.1007/3-540-17945-3_13
    33 schema:sdDatePublished 2019-04-15T19:07
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher N32a014bf165f463387a49d89eb736674
    36 schema:url http://link.springer.com/10.1007/3-540-17945-3_13
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset chapters
    39 rdf:type schema:Chapter
    40 N23dbf076f61448be9e3291ecfbfea856 rdf:first Na94812a6d9b14843867df2a51e8307ee
    41 rdf:rest N4779ec436bf949d0b40f30fdcbf5e156
    42 N32a014bf165f463387a49d89eb736674 schema:name Springer Nature - SN SciGraph project
    43 rdf:type schema:Organization
    44 N4779ec436bf949d0b40f30fdcbf5e156 rdf:first Nb190bcd66320497684ba3e9049fbdb50
    45 rdf:rest rdf:nil
    46 N4b7e5d8f8e5a43f298bd3a9b5190a628 rdf:first sg:person.010555433417.04
    47 rdf:rest N77a305749ccc46d8b3defa01cca134da
    48 N59c48ba94ab64a59afcc4787f0c1a3b8 schema:isbn 978-3-540-17945-0
    49 978-3-540-47181-3
    50 schema:name PARLE Parallel Architectures and Languages Europe
    51 rdf:type schema:Book
    52 N5cef2c121519413081d22503837b89f3 schema:name readcube_id
    53 schema:value 23792f3d05c1ffe8e3f6853de43cfe8ed4837be4787133d11fc69d5428f637a8
    54 rdf:type schema:PropertyValue
    55 N74da07b261aa46a98707eec5753aa8bb schema:location Berlin, Heidelberg
    56 schema:name Springer Berlin Heidelberg
    57 rdf:type schema:Organisation
    58 N77a305749ccc46d8b3defa01cca134da rdf:first sg:person.0765460367.38
    59 rdf:rest rdf:nil
    60 N89da59dd29b945138563068d6afac138 schema:familyName Bakker
    61 schema:givenName J. W.
    62 rdf:type schema:Person
    63 N8b83bfc94c5747bea6286d0009da2787 rdf:first N89da59dd29b945138563068d6afac138
    64 rdf:rest N23dbf076f61448be9e3291ecfbfea856
    65 Na94812a6d9b14843867df2a51e8307ee schema:familyName Nijman
    66 schema:givenName A. J.
    67 rdf:type schema:Person
    68 Nb190bcd66320497684ba3e9049fbdb50 schema:familyName Treleaven
    69 schema:givenName P. C.
    70 rdf:type schema:Person
    71 Ne452928802bb49979f168965f6a8b9ce schema:name dimensions_id
    72 schema:value pub.1007447453
    73 rdf:type schema:PropertyValue
    74 Nee64c25a19834367a6a03029be345f7e schema:name doi
    75 schema:value 10.1007/3-540-17945-3_13
    76 rdf:type schema:PropertyValue
    77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Information and Computing Sciences
    79 rdf:type schema:DefinedTerm
    80 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Computation Theory and Mathematics
    82 rdf:type schema:DefinedTerm
    83 sg:person.010555433417.04 schema:affiliation https://www.grid.ac/institutes/grid.6054.7
    84 schema:familyName van Glabbeek
    85 schema:givenName Rob
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555433417.04
    87 rdf:type schema:Person
    88 sg:person.0765460367.38 schema:affiliation https://www.grid.ac/institutes/grid.6054.7
    89 schema:familyName Vaandrager
    90 schema:givenName Frits
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0765460367.38
    92 rdf:type schema:Person
    93 sg:pub.10.1007/3-540-12920-0_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023917668
    94 https://doi.org/10.1007/3-540-12920-0_13
    95 rdf:type schema:CreativeWork
    96 sg:pub.10.1007/3-540-13345-3_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022331272
    97 https://doi.org/10.1007/3-540-13345-3_18
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1007/3-540-13883-8_66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047492704
    100 https://doi.org/10.1007/3-540-13883-8_66
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/3-540-15204-0_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034306316
    103 https://doi.org/10.1007/3-540-15204-0_20
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/3-540-15204-0_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033761956
    106 https://doi.org/10.1007/3-540-15204-0_5
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/3-540-17660-8_52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028712016
    109 https://doi.org/10.1007/3-540-17660-8_52
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/bf01379149 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035171005
    112 https://doi.org/10.1007/bf01379149
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/bfb0012800 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006383355
    115 https://doi.org/10.1007/bfb0012800
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/bfb0016222 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001018251
    118 https://doi.org/10.1007/bfb0016222
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/bfb0027048 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039262993
    121 https://doi.org/10.1007/bfb0027048
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1016/0304-3975(81)90112-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035972534
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1016/0304-3975(85)90088-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1022391759
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.7146/dpb.v6i78.7691 schema:sameAs https://app.dimensions.ai/details/publication/pub.1073611461
    128 rdf:type schema:CreativeWork
    129 https://www.grid.ac/institutes/grid.6054.7 schema:alternateName Centrum Wiskunde and Informatica
    130 schema:name Centre for Mathematics and Computer Science, P.O. Box 4079, 1009 AB Amsterdam, The Netherlands
    131 rdf:type schema:Organization
     




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


    ...