Translating Workflow Nets to Process Trees : An Algorithmic Approach

QUT ePrints (Queensland University of Technology)

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, if 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 rediscoverability.

Authors 2

1. Sebastiaan J. van Zelst corresponding Aachen Chair of Process and Data Science

   RWTH Aachen University · Fraunhofer-Gesellschaft · Fraunhofer Institute for Applied Information Technology

   Affiliation as printed

   Chair of Process and Data Science, RWTH Aachen University, 52074 Aachen, Germany

   Institute for Applied Information Technology (FIT), Fraunhofer Gesellschaft, 53754 Sankt Augustin, Germany

2. Sander J. J. Leemans

   Queensland University of Technology

   Affiliation as printed

   School of Information Systems, Queensland University of Technology, Brisbane City QLD 4000, Australia