# Translating Workflow Nets to Process Trees: An Algorithmic Approach
## 1 Introduction  
_Process mining_[1] is concerned with distilling knowledge of the execution of processes by analyzing the event data generated during the execution of these processes, i.e., stored in modern-day information systems. In the field, different (semi-)automated techniques have been developed that allow one to distill knowledge of a process from event data, ranging from _automated process discovery algorithms_ to _conformance checking algorithms_. In automated process discovery, the main aim is to translate observed process behavior, i.e., as stored in the information system, into a process model that accurately describes the behavior of the process. In this context, the discovered process model should strike an adequate balance between accounting for unobserved, yet likely, process behavior (i.e., avoiding overfitting) and being precise (i.e., avoiding underfitting) at the same time. Conformance checking techniques allow us to compute to what degree the observed behavior is in line with a given reference process model (either designed by hand or discovered using an automated process discovery technique). Since processes are the cornerstone of process mining, so are the models that allow us to represent them (and reason about their behavior and quality). As such, various process modeling formalisms exist, e.g., BPMN [2], EPCs [3], etc., some of which are heavily used in practice. Recently, process trees were introduced [4]. A process tree is a hierarchical representation of a process corresponding to the mathematical notion of a rooted tree, i.e., a connected undirected acyclic graph with a designated root vertex. The internal vertices of a process tree represent how their childrenrelate to each other regarding their control-flow behavior (i.e., their sequential scheduling). The leaves of the tree represent the activities of the process. Consider Figure 1, in which we depict an example process tree. Its root vertex has label \(\rightarrow\), specifying that first its leftmost child, i.e., activity \(a\), needs to be executed, secondly its middle child, and, finally, its rightmost child. Its middle child has a \(\circlearrowleft\) label, specifying cyclic behavior, i.e., its leftmost child is _always executed_, whereas the execution of its rightmost child stipulates that we need to _repeat_ its leftmost child. The \(\times\)-label in a process tree represents an _exclusive choice_, e.g., vertex \(\
u_{1,3}\) specifies that we either executed activity \(g\) or \(h\), yet not both. Finally, the \(\wedge\)-label refers to concurrency, i.e, the children of a vertex with such a label are allowed to be executed simultaneously, i.e., at the same time. Furthermore, consider the two models depicted in Figure 2 (page 3), i.e., a _Workflow net (WF-net)_ and a process tree (note that the activity labels within the model are not depicted in a readable fashion, i.e., the main aim of the figure is to illustrate the structural differences between WF-nets and process trees). The models represent the same behavior, based on a real-life event log. Clearly, the hierarchy of the process tree allows one to more easily understand the main control-flow of the process. The previous examples show the relative simplicity at which one can reason on the behavior of a process tree. Furthermore, it is straightforward to translate process trees into other process modeling formalisms, e.g., WF-nets, BPMN models, etc. By definition, a process tree corresponds to a _sound WF-net_, i.e., a WF-net with desirable behavioral properties, e.g., the absence of deadlocks. The reverse, i.e., translating a given WF-net into a process tree (if possible), is less trivial. At the same time, obtaining such a translation is of great interest, e.g., it allows us to discover control-flow-aware hierarchical structures within a WF-net. Such structures can, for example, be used to hide certain parts of the model, i.e., leading to a more understandable view of the process model.