Improving the linearly based characterization of P/T nets View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1991

AUTHORS

J. M. Colom , M. Silva

ABSTRACT

The state equation is a linear description of the reachable markings and firing count vectors of a P/T net. It has the disadvantage that its solution space, in general, includes additional integer unreachable or/and unfirable vectors. As a result, the analysis of properties using this linear characterization, usually leads to necessary or sufficient conditions for satisfying it, but not both. The appearance of these spurious solutions is due to the fact that the state equation does not take into account the order in which transitions fire. The first consists of checking that every marking which is a solution of the state equation has a sequence of predecessor markings, and that the transition firing rule holds in that sequence. The second is based on the addition of implicit places to the net [SILV 85] which are linearly non-redundant in the state equation. Some of these places are associated to initially marked traps, and the elimination of unreachable markings they perform is based on a well-known fact: initially marked traps remain always marked. The reasoning on structural deadlocks leads to the complementary fact: initially unmarked deadlocks remains always unmarked. In this case the linear restrictions are based on the annullation of marking variables belonging to places in the deadlock. Last but not least, another important point is the characterization by means of one single Linear Programming Problem (LPP) of those implicit places which are structurally implicit. The interesting fact here is that the theoretical complexity to solve a LPP is polynomial and the practical complexity is linear [SAKA 84]. More... »

PAGES

113-145

References to SciGraph publications

  • 1988. On the computation of structural synchronic invariants in P/T nets in ADVANCES IN PETRI NETS 1988
  • 1987. Transformations and Decompositions of Nets in PETRI NETS: CENTRAL MODELS AND THEIR PROPERTIES
  • Book

    TITLE

    Advances in Petri Nets 1990

    ISBN

    978-3-540-53863-9
    978-3-540-46369-6

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-53863-1_23

    DOI

    http://dx.doi.org/10.1007/3-540-53863-1_23

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Zaragoza", 
              "id": "https://www.grid.ac/institutes/grid.11205.37", 
              "name": [
                "Dpto. Ingenier\u00eda El\u00e9ctrica e Inform\u00e1tica, Universidad de Zaragoza, Mar\u00eda de Luna, 3 (Actur), 50015\u00a0ZARAGOZA, Spain"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Colom", 
            "givenName": "J. M.", 
            "id": "sg:person.016005103353.68", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016005103353.68"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Zaragoza", 
              "id": "https://www.grid.ac/institutes/grid.11205.37", 
              "name": [
                "Dpto. Ingenier\u00eda El\u00e9ctrica e Inform\u00e1tica, Universidad de Zaragoza, Mar\u00eda de Luna, 3 (Actur), 50015\u00a0ZARAGOZA, Spain"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Silva", 
            "givenName": "M.", 
            "id": "sg:person.013406576107.14", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013406576107.14"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-50580-6_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016242507", 
              "https://doi.org/10.1007/3-540-50580-6_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-47919-2_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033954355", 
              "https://doi.org/10.1007/978-3-540-47919-2_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(92)90299-u", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048479415"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1991", 
        "datePublishedReg": "1991-01-01", 
        "description": "The state equation is a linear description of the reachable markings and firing count vectors of a P/T net. It has the disadvantage that its solution space, in general, includes additional integer unreachable or/and unfirable vectors. As a result, the analysis of properties using this linear characterization, usually leads to necessary or sufficient conditions for satisfying it, but not both. The appearance of these spurious solutions is due to the fact that the state equation does not take into account the order in which transitions fire. The first consists of checking that every marking which is a solution of the state equation has a sequence of predecessor markings, and that the transition firing rule holds in that sequence. The second is based on the addition of implicit places to the net [SILV 85] which are linearly non-redundant in the state equation. Some of these places are associated to initially marked traps, and the elimination of unreachable markings they perform is based on a well-known fact: initially marked traps remain always marked. The reasoning on structural deadlocks leads to the complementary fact: initially unmarked deadlocks remains always unmarked. In this case the linear restrictions are based on the annullation of marking variables belonging to places in the deadlock. Last but not least, another important point is the characterization by means of one single Linear Programming Problem (LPP) of those implicit places which are structurally implicit. The interesting fact here is that the theoretical complexity to solve a LPP is polynomial and the practical complexity is linear [SAKA 84].", 
        "editor": [
          {
            "familyName": "Rozenberg", 
            "givenName": "Grzegorz", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-53863-1_23", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-53863-9", 
            "978-3-540-46369-6"
          ], 
          "name": "Advances in Petri Nets 1990", 
          "type": "Book"
        }, 
        "name": "Improving the linearly based characterization of P/T nets", 
        "pagination": "113-145", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-53863-1_23"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "6fe313b31d4be8938c30a161cc65216a5de595637bd079fc1bda747f42b86b2c"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1023484432"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-53863-1_23", 
          "https://app.dimensions.ai/details/publication/pub.1023484432"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T17:00", 
        "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_8678_00000040.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-53863-1_23"
      }
    ]
     

    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-53863-1_23'

    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-53863-1_23'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-53863-1_23'

    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-53863-1_23'


     

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

    83 TRIPLES      23 PREDICATES      30 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-53863-1_23 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Ncf1723e7a41147fb82b2dcf1a983d316
    4 schema:citation sg:pub.10.1007/3-540-50580-6_39
    5 sg:pub.10.1007/978-3-540-47919-2_13
    6 https://doi.org/10.1016/0304-3975(92)90299-u
    7 schema:datePublished 1991
    8 schema:datePublishedReg 1991-01-01
    9 schema:description The state equation is a linear description of the reachable markings and firing count vectors of a P/T net. It has the disadvantage that its solution space, in general, includes additional integer unreachable or/and unfirable vectors. As a result, the analysis of properties using this linear characterization, usually leads to necessary or sufficient conditions for satisfying it, but not both. The appearance of these spurious solutions is due to the fact that the state equation does not take into account the order in which transitions fire. The first consists of checking that every marking which is a solution of the state equation has a sequence of predecessor markings, and that the transition firing rule holds in that sequence. The second is based on the addition of implicit places to the net [SILV 85] which are linearly non-redundant in the state equation. Some of these places are associated to initially marked traps, and the elimination of unreachable markings they perform is based on a well-known fact: initially marked traps remain always marked. The reasoning on structural deadlocks leads to the complementary fact: initially unmarked deadlocks remains always unmarked. In this case the linear restrictions are based on the annullation of marking variables belonging to places in the deadlock. Last but not least, another important point is the characterization by means of one single Linear Programming Problem (LPP) of those implicit places which are structurally implicit. The interesting fact here is that the theoretical complexity to solve a LPP is polynomial and the practical complexity is linear [SAKA 84].
    10 schema:editor Nae8c2626ef0d489faae87316e946394f
    11 schema:genre chapter
    12 schema:inLanguage en
    13 schema:isAccessibleForFree false
    14 schema:isPartOf N1d1413860fb0489db61ecadf73a00172
    15 schema:name Improving the linearly based characterization of P/T nets
    16 schema:pagination 113-145
    17 schema:productId N21623df625dc46819a0b9b23ed39ddd6
    18 N6d2019457ef54c5fbbf98d199f049205
    19 Nf11ce3a5da6d4d679d080448e23edd29
    20 schema:publisher N1ff5649aafd044ea81eefc89f557ce1f
    21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023484432
    22 https://doi.org/10.1007/3-540-53863-1_23
    23 schema:sdDatePublished 2019-04-15T17:00
    24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    25 schema:sdPublisher Nfdc7e945609b44e59a5222900b1db999
    26 schema:url http://link.springer.com/10.1007/3-540-53863-1_23
    27 sgo:license sg:explorer/license/
    28 sgo:sdDataset chapters
    29 rdf:type schema:Chapter
    30 N1d1413860fb0489db61ecadf73a00172 schema:isbn 978-3-540-46369-6
    31 978-3-540-53863-9
    32 schema:name Advances in Petri Nets 1990
    33 rdf:type schema:Book
    34 N1ff5649aafd044ea81eefc89f557ce1f schema:location Berlin, Heidelberg
    35 schema:name Springer Berlin Heidelberg
    36 rdf:type schema:Organisation
    37 N21623df625dc46819a0b9b23ed39ddd6 schema:name doi
    38 schema:value 10.1007/3-540-53863-1_23
    39 rdf:type schema:PropertyValue
    40 N6d2019457ef54c5fbbf98d199f049205 schema:name dimensions_id
    41 schema:value pub.1023484432
    42 rdf:type schema:PropertyValue
    43 Nae8c2626ef0d489faae87316e946394f rdf:first Neefb6f7eb25c4aa995ae859a2ec6da80
    44 rdf:rest rdf:nil
    45 Nb8e938072da9446a8e8af3e1e2f307e9 rdf:first sg:person.013406576107.14
    46 rdf:rest rdf:nil
    47 Ncf1723e7a41147fb82b2dcf1a983d316 rdf:first sg:person.016005103353.68
    48 rdf:rest Nb8e938072da9446a8e8af3e1e2f307e9
    49 Neefb6f7eb25c4aa995ae859a2ec6da80 schema:familyName Rozenberg
    50 schema:givenName Grzegorz
    51 rdf:type schema:Person
    52 Nf11ce3a5da6d4d679d080448e23edd29 schema:name readcube_id
    53 schema:value 6fe313b31d4be8938c30a161cc65216a5de595637bd079fc1bda747f42b86b2c
    54 rdf:type schema:PropertyValue
    55 Nfdc7e945609b44e59a5222900b1db999 schema:name Springer Nature - SN SciGraph project
    56 rdf:type schema:Organization
    57 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    58 schema:name Mathematical Sciences
    59 rdf:type schema:DefinedTerm
    60 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    61 schema:name Pure Mathematics
    62 rdf:type schema:DefinedTerm
    63 sg:person.013406576107.14 schema:affiliation https://www.grid.ac/institutes/grid.11205.37
    64 schema:familyName Silva
    65 schema:givenName M.
    66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013406576107.14
    67 rdf:type schema:Person
    68 sg:person.016005103353.68 schema:affiliation https://www.grid.ac/institutes/grid.11205.37
    69 schema:familyName Colom
    70 schema:givenName J. M.
    71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016005103353.68
    72 rdf:type schema:Person
    73 sg:pub.10.1007/3-540-50580-6_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016242507
    74 https://doi.org/10.1007/3-540-50580-6_39
    75 rdf:type schema:CreativeWork
    76 sg:pub.10.1007/978-3-540-47919-2_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033954355
    77 https://doi.org/10.1007/978-3-540-47919-2_13
    78 rdf:type schema:CreativeWork
    79 https://doi.org/10.1016/0304-3975(92)90299-u schema:sameAs https://app.dimensions.ai/details/publication/pub.1048479415
    80 rdf:type schema:CreativeWork
    81 https://www.grid.ac/institutes/grid.11205.37 schema:alternateName University of Zaragoza
    82 schema:name Dpto. Ingeniería Eléctrica e Informática, Universidad de Zaragoza, María de Luna, 3 (Actur), 50015 ZARAGOZA, Spain
    83 rdf:type schema:Organization
     




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


    ...