The relationship between workflow graphs and free-choice workflow nets

C. Favre, D. Fahland, H. Völzer

Research output: Contribution to journalArticleAcademicpeer-review

24 Citations (Scopus)
5 Downloads (Pure)

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
Original languageEnglish
Pages (from-to)197-219
Number of pages23
JournalInformation Systems
Volume47
DOIs
Publication statusPublished - 2015

Fingerprint

Dive into the research topics of 'The relationship between workflow graphs and free-choice workflow nets'. Together they form a unique fingerprint.

Cite this