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 N4ae9fd2f316b421995cd642546bb2353
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 N5590ed6596b04f4ea211771e6f0aec7f
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Ne3b1424488c045a9bed20c2ca011bd07
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 N222c4aab177f45cdad8fad4c33854b24
50 N66a5ec00d234419fbac5fc8700703eb8
51 schema:publisher N599673ea938a4ab69b345aabb991a821
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 N8939e1d6a98a4c70b15845f2720f0a49
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 N222c4aab177f45cdad8fad4c33854b24 schema:name doi
62 schema:value 10.1007/3-540-47961-9_37
63 rdf:type schema:PropertyValue
64 N4ae9fd2f316b421995cd642546bb2353 rdf:first sg:person.014757056433.19
65 rdf:rest Ncaceb5315a4e44d7a6b934c857d7683e
66 N5590ed6596b04f4ea211771e6f0aec7f rdf:first Ncf974b2166cd477390dd6bd6dbdda282
67 rdf:rest rdf:nil
68 N599673ea938a4ab69b345aabb991a821 schema:name Springer Nature
69 rdf:type schema:Organisation
70 N66a5ec00d234419fbac5fc8700703eb8 schema:name dimensions_id
71 schema:value pub.1016171618
72 rdf:type schema:PropertyValue
73 N8939e1d6a98a4c70b15845f2720f0a49 schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 N91ea892a6c684f6d8f57c00431ac2e5d rdf:first sg:person.016630174535.10
76 rdf:rest rdf:nil
77 Ncaceb5315a4e44d7a6b934c857d7683e rdf:first sg:person.014510736401.51
78 rdf:rest N91ea892a6c684f6d8f57c00431ac2e5d
79 Ncf974b2166cd477390dd6bd6dbdda282 schema:familyName King
80 schema:givenName Rudibert
81 rdf:type schema:Person
82 Ne3b1424488c045a9bed20c2ca011bd07 schema:isbn 978-3-540-43738-3
83 978-3-540-47961-1
84 schema:name Active Flow and Combustion Control 2018
85 rdf:type schema:Book
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)


...