# Translating Workflow Nets to Process Trees: An Algorithmic Approach
## Preliminaries
### Process Trees  
Process trees allow us to model processes that comprise a control-flow hierarchy. A process tree is a mathematical tree, where the internal vertices are _operators_, and leaves are (non-observable) _activities_. Operators specify how their children, i.e., sub-trees, need to be combined from a control-flow perspective. Several operators can be defined; however, in this work, we focus on four basic operators, i.e., the \(\rightarrow\), \(\times\), \(\wedge\) and \(\circlearrowleft\)-operator. The _sequence_ operator (\(\rightarrow\)) specifies sequential behavior. First, its left-most child is executed, then its second left-most child, and so on until finally its right-most child. For example, the root operator in Figure 4 specifies that first activity \(a\) is executed, then its second sub-tree (\(\circlearrowleft\)) and finally its third sub-tree (\(\times\)). The _exclusive choice_ operator (\(\times\)), specifies an exclusive choice, i.e., one (and exactly one) of its sub-trees is executed. Concurrent/parallel behavior is represented by the _concurrency operator_ (\(\wedge\)), i.e., all children are executed simultaneously/in any order. Finally, we represent repeated behavior by the _loop operator_\(\circlearrowleft\). Whereas the \(\rightarrow\), \(\times\)-, and \(\wedge\)-operators have an arbitrary number of children, the \(\circlearrowleft\)-operator has two children. Its left child (the \"do-child\")is _always_ executed. Secondly, executing its right child (the \"re-do-child\") is optional. After executing the re-do-child, we again execute the do-child. We are allowed to repeat this, yet we always finish with the do-child. Note that, various definitions of the loop operator exist, i.e., with three/an arbitrary number of children (e.g., [1] Definition 3.13). All of these definitions can be rewritten into the binary loop operator, i.e., as considered in this paper.  
Note that, the process tree in Figure 4, describes the same language as the WF-net in Figure 3.  
The root of the tree, i.e., \(v_{0}\), is a sequence operator, specifying that first, its left-most child (\(v_{1.1}\)) is executed. Its middle child, i.e., \(v_{1.2}\), represents a loop operator. The left sub-tree of the loop operator (i.e., having vertex \(v_{2.1}\) as its root) is always executed. Vertex \(v_{2.2}\) represents the \"redo\" part of the loop operator. The last part of the tree is represented by \(v_{1.3}\), i.e., specifying a choice construct between executing activity \(g\) or \(h\).  
Definition 3 (Process Tree): Let \(\Sigma\) denote the universe of (activity) labels and let \(\tau\
ot\in\Sigma\). Let \(\bigoplus\) denote the universe of process tree operators. A process tree \(Q\), is defined (recursively) as any of:  
1. \(x\in\Sigma\cup\{\tau\}\); an (non-observable) activity,
2. \(\oplus(Q_{1},...,Q_{n})\), for \(\oplus\in\bigoplus\), \(n\geq\)1, where \(Q_{1},...,Q_{n}\) are process trees;  
We let \(\mathcal{Q}\) denote the universe of process trees.  
Given a process tree \(Q\in\mathcal{Q}\), its language is of the form \(\mathcal{L}_{\mathcal{Q}}(Q)\subseteq\Sigma^{*}\), which is recursively defined in terms of of the languages of the children of a process tree. For example, the language of the \(\rightarrow\)-operator, is formed by concatenating any element of the language of its first child, with any element of its second child, etc. We formally define the language of a process tree as follows.  
Definition 4 (Process Tree Language): Let \(Q\in\mathcal{Q}\) be a process tree. The language of \(Q\), i.e., \(\mathcal{L}_{\mathcal{Q}}(Q)\subseteq\Sigma^{*}\), is defined recursively as:  
Figure 4: Process tree [1], describing the same language as the WF-net in Figure 3 (reprint of Figure 1).  
operators within the net, together with a generic reduction function. Finally, in Section 3.4, we provide an algorithmic description that allows us to find process trees, including correctness proofs.