An Alternative Way to Analyze Workflow Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002-05-29

AUTHORS

W. M. P. van der Aalst , A. Hirnschall , H. M. W. Verbeek

ABSTRACT

At the CAiSE conference in Heidelberg in 1999, Wasim Sadiq and Maria Orlowska presented an algorithm to verify workflow graphs [19]. The algorithm uses a set of reduction rules to detect structural conflicts. This paper shows that the set of reduction rules presented in [19] is not complete and proposes an alternative algorithm. The algorithm translates workflow graphs into so-called WF-nets. WF-nets are a class of Petri nets tailored towards workflow analysis. As a result, Petri-net theory and tools can be used to verify workflow graphs. In particular, our workflow verification tool Woflan [21] can be used to detect design errors. It is shown that the absence of structural conflicts, i.e., deadlocks and lack of synchronization, conforms to soundness of the corresponding WF-net [2]. In contrast to the algorithm presented in [19], the algorithm presented in this paper is complete. Moreover, the complexity of this alternative algorithm is given. More... »

PAGES

535-552

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-47961-9_37

DOI

http://dx.doi.org/10.1007/3-540-47961-9_37

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Faculty of Technology and Management Department of Information and Technology, Eindhoven University of Technology, P.O. ox 513, NL-5600 MB, Eindhoven, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.6852.9", 
          "name": [
            "Faculty of Technology and Management Department of Information and Technology, Eindhoven University of Technology, P.O. ox 513, NL-5600 MB, Eindhoven, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "van der Aalst", 
        "givenName": "W. M. P.", 
        "id": "sg:person.014757056433.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014757056433.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Technology and Management Department of Information and Technology, Eindhoven University of Technology, P.O. ox 513, NL-5600 MB, Eindhoven, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.6852.9", 
          "name": [
            "Faculty of Technology and Management Department of Information and Technology, Eindhoven University of Technology, P.O. ox 513, NL-5600 MB, Eindhoven, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hirnschall", 
        "givenName": "A.", 
        "id": "sg:person.014510736401.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014510736401.51"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Technology and Management Department of Information and Technology, Eindhoven University of Technology, P.O. ox 513, NL-5600 MB, Eindhoven, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.6852.9", 
          "name": [
            "Faculty of Technology and Management Department of Information and Technology, Eindhoven University of Technology, P.O. ox 513, NL-5600 MB, Eindhoven, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Verbeek", 
        "givenName": "H. M. W.", 
        "id": "sg:person.016630174535.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016630174535.10"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-05-29", 
    "datePublishedReg": "2002-05-29", 
    "description": "At the CAiSE conference in Heidelberg in 1999, Wasim Sadiq and Maria Orlowska presented an algorithm to verify workflow graphs [19]. The algorithm uses a set of reduction rules to detect structural conflicts. This paper shows that the set of reduction rules presented in [19] is not complete and proposes an alternative algorithm. The algorithm translates workflow graphs into so-called WF-nets. WF-nets are a class of Petri nets tailored towards workflow analysis. As a result, Petri-net theory and tools can be used to verify workflow graphs. In particular, our workflow verification tool Woflan [21] can be used to detect design errors. It is shown that the absence of structural conflicts, i.e., deadlocks and lack of synchronization, conforms to soundness of the corresponding WF-net [2]. In contrast to the algorithm presented in [19], the algorithm presented in this paper is complete. Moreover, the complexity of this alternative algorithm is given.", 
    "editor": [
      {
        "familyName": "King", 
        "givenName": "Rudibert", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-47961-9_37", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-43738-3", 
        "978-3-540-47961-1"
      ], 
      "name": "Active Flow and Combustion Control 2018", 
      "type": "Book"
    }, 
    "keywords": [
      "graph", 
      "reduction rules", 
      "alternative algorithms", 
      "Petri net theory", 
      "Orlowska", 
      "algorithm", 
      "workflow graph", 
      "set", 
      "rules", 
      "class", 
      "Petri nets", 
      "theory", 
      "error", 
      "lack of synchronization", 
      "synchronization", 
      "complexity", 
      "structural conflicts", 
      "WF-nets", 
      "nets", 
      "analysis", 
      "results", 
      "tool", 
      "design errors", 
      "deadlock", 
      "soundness", 
      "alternative way", 
      "way", 
      "conference", 
      "Heidelberg", 
      "Sadiq", 
      "conflict", 
      "workflow analysis", 
      "absence", 
      "lack", 
      "contrast", 
      "paper"
    ], 
    "name": "An Alternative Way to Analyze Workflow Graphs", 
    "pagination": "535-552", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016171618"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-47961-9_37"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-47961-9_37", 
      "https://app.dimensions.ai/details/publication/pub.1016171618"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T07:01", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_96.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-47961-9_37"
  }
]
 

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-47961-9_37'

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-47961-9_37'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-47961-9_37'

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-47961-9_37'


 

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

109 TRIPLES      22 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-47961-9_37 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N5212d2a4f82844a38d5123a73e81810a
4 schema:datePublished 2002-05-29
5 schema:datePublishedReg 2002-05-29
6 schema:description At the CAiSE conference in Heidelberg in 1999, Wasim Sadiq and Maria Orlowska presented an algorithm to verify workflow graphs [19]. The algorithm uses a set of reduction rules to detect structural conflicts. This paper shows that the set of reduction rules presented in [19] is not complete and proposes an alternative algorithm. The algorithm translates workflow graphs into so-called WF-nets. WF-nets are a class of Petri nets tailored towards workflow analysis. As a result, Petri-net theory and tools can be used to verify workflow graphs. In particular, our workflow verification tool Woflan [21] can be used to detect design errors. It is shown that the absence of structural conflicts, i.e., deadlocks and lack of synchronization, conforms to soundness of the corresponding WF-net [2]. In contrast to the algorithm presented in [19], the algorithm presented in this paper is complete. Moreover, the complexity of this alternative algorithm is given.
7 schema:editor N145d5f6705aa4164b5f621f62c82c24a
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Na6bbaf37e62f41fb8e7d42034fb57f3f
11 schema:keywords Heidelberg
12 Orlowska
13 Petri net theory
14 Petri nets
15 Sadiq
16 WF-nets
17 absence
18 algorithm
19 alternative algorithms
20 alternative way
21 analysis
22 class
23 complexity
24 conference
25 conflict
26 contrast
27 deadlock
28 design errors
29 error
30 graph
31 lack
32 lack of synchronization
33 nets
34 paper
35 reduction rules
36 results
37 rules
38 set
39 soundness
40 structural conflicts
41 synchronization
42 theory
43 tool
44 way
45 workflow analysis
46 workflow graph
47 schema:name An Alternative Way to Analyze Workflow Graphs
48 schema:pagination 535-552
49 schema:productId N1306dd671d32483693f6868ae85f6cf4
50 N3cf2886285ad4b7f931a4432c0907148
51 schema:publisher Nffa1eca2dc4d4416baed4db944b6395d
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016171618
53 https://doi.org/10.1007/3-540-47961-9_37
54 schema:sdDatePublished 2022-10-01T07:01
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher N3c600c31a65046e1b0a89c330d0c843c
57 schema:url https://doi.org/10.1007/3-540-47961-9_37
58 sgo:license sg:explorer/license/
59 sgo:sdDataset chapters
60 rdf:type schema:Chapter
61 N1306dd671d32483693f6868ae85f6cf4 schema:name dimensions_id
62 schema:value pub.1016171618
63 rdf:type schema:PropertyValue
64 N145d5f6705aa4164b5f621f62c82c24a rdf:first Na7f95b7132da42c1a700d0aa9ffb8554
65 rdf:rest rdf:nil
66 N3c600c31a65046e1b0a89c330d0c843c schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N3cf2886285ad4b7f931a4432c0907148 schema:name doi
69 schema:value 10.1007/3-540-47961-9_37
70 rdf:type schema:PropertyValue
71 N4f9686b5f0574f588421baef135ad70b rdf:first sg:person.016630174535.10
72 rdf:rest rdf:nil
73 N5212d2a4f82844a38d5123a73e81810a rdf:first sg:person.014757056433.19
74 rdf:rest Nda4e494913ca434b8a10d30b54b1d559
75 Na6bbaf37e62f41fb8e7d42034fb57f3f schema:isbn 978-3-540-43738-3
76 978-3-540-47961-1
77 schema:name Active Flow and Combustion Control 2018
78 rdf:type schema:Book
79 Na7f95b7132da42c1a700d0aa9ffb8554 schema:familyName King
80 schema:givenName Rudibert
81 rdf:type schema:Person
82 Nda4e494913ca434b8a10d30b54b1d559 rdf:first sg:person.014510736401.51
83 rdf:rest N4f9686b5f0574f588421baef135ad70b
84 Nffa1eca2dc4d4416baed4db944b6395d schema:name Springer Nature
85 rdf:type schema:Organisation
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
90 schema:name Information Systems
91 rdf:type schema:DefinedTerm
92 sg:person.014510736401.51 schema:affiliation grid-institutes:grid.6852.9
93 schema:familyName Hirnschall
94 schema:givenName A.
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014510736401.51
96 rdf:type schema:Person
97 sg:person.014757056433.19 schema:affiliation grid-institutes:grid.6852.9
98 schema:familyName van der Aalst
99 schema:givenName W. M. P.
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014757056433.19
101 rdf:type schema:Person
102 sg:person.016630174535.10 schema:affiliation grid-institutes:grid.6852.9
103 schema:familyName Verbeek
104 schema:givenName H. M. W.
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016630174535.10
106 rdf:type schema:Person
107 grid-institutes:grid.6852.9 schema:alternateName Faculty of Technology and Management Department of Information and Technology, Eindhoven University of Technology, P.O. ox 513, NL-5600 MB, Eindhoven, The Netherlands
108 schema:name Faculty of Technology and Management Department of Information and Technology, Eindhoven University of Technology, P.O. ox 513, NL-5600 MB, Eindhoven, The Netherlands
109 rdf:type schema:Organization
 




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


...