Translating Workflow Nets to Process Trees: An Algorithmic Approach

Preprints.org

Abstract

Since their introduction, process trees have been frequently used as a process modeling formalism in many process mining algorithms. A process tree is a (mathematical) tree-based model of a process, in which internal vertices represent behavioral control-flow relations and leaves represent process activities. Translation of a process tree into a sound Workflow net is trivial; however, the reverse is not the case. Simultaneously, an algorithm that translates a WF-net into a process tree is of great interest, e.g., the explicit knowledge of the control-flow hierarchy in a WF-net allows one to reason on its behavior more easily. Hence, in this paper, we present such an algorithm, i.e., it detects whether a WF-net corresponds to a process tree, and, if so, constructs it. We prove that, when the algorithm finds a process tree, the language of the process tree is equal to the language of the original WF-net. The experiments conducted show that the algorithm’s corresponding implementation has a quadratic time complexity in the size of the WF-net. Furthermore, the experiments show strong evidence of process tree re-discoverability.

Authors 2

1. Sebastiaan J. van Zelst corresponding Aachen

   RWTH Aachen University · Fraunhofer Institute for Applied Information Technology

   Affiliation as printed

   Fraunhofer Institute for Applied Information Technology (FIT) , Germany;

   RWTH Aachen University , Aachen , Germany;

   Fraunhofer Institute for Applied Information Technology (FIT), Germany;

   RWTH Aachen University, Aachen, Germany;

2. Sander J. J. Leemans

   Queensland University of Technology

   Affiliation as printed

   Queensland University of Technology , Brisbane , Australia;

   Queensland University of Technology, Brisbane, Australia;