The relationship between workflow graphs and free-choice workflow nets

Article

Favre, C., Fahland, D. & Völzer, H. (2015). The relationship between workflow graphs and free-choice workflow nets. Information Systems, 47, 197-219. In Scopus Cited 12 times.

Read more: DOI      Medialink/Full text

Abstract

 

Workflow graphs represent the main control-flow constructs of industrial process modeling languages such as BPMN, EPC and UML Activity diagrams, whereas free-choice workflow nets is a well understood class of Petri nets that possesses many efficient analysis techniques. In this paper, we provide new results on the translation between workflow graphs and free-choice workflow nets.

We distinguish workflow graphs with and without inclusive Or-logic. For workflow graphs without inclusive logic, we show that workflow graphs and free-choice workflow nets are essentially the same thing. More precisely, each workflow graph and each free-choice workflow net can be brought into an equivalent normal form such that the normal forms are, in some sense, isomorphic. This result gives rise to a translation from arbitrary free-choice workflow nets to workflow graphs.

For workflow graphs with inclusive logic, we provide various techniques to replace inclusive Or-joins by subgraphs without inclusive logic, thus giving rise to translations from workflow graphs to free-choice nets. Additionally, we characterize the applicability of these replacements. Finally, we also display a simple workflow graph with an inclusive Or-join, which, in some sense, cannot be replaced. This shows a limitation of translating inclusive logic into free-choice nets and illustrates also a difficulty of translating inclusive logic into general Petri nets.

Keywords: Workflow graphs; Petri nets; Free choice; Inclusive OR-join