# Translating Workflow Nets to Process Trees: An Algorithmic Approach
## 6 Discussion
### Relation to Refined Process Structure Tree  
One of the works that is conceptually very close to the work presented in this paper, is the work on the Refined Process Structure Tree (RPST) [25; 26]. An RPST describes a hierarchy of sub-workflows of a _workflow graph_, such that each sub-workflow represents a connected subgraph with a single entry and single exit of control. In this context, a workflow graph is simply a two-terminal graph (TTG), i.e., a directed graph without self-loops with a unique source \((s)\) and sink node \((t\
eq s)\), s.t. each node in the TTG is on a path from \(s\) to \(t\). Note that a WF-net, i.e., from a graph-theoretical perspective, is a workflow graph. However, various other process modeling formalisms, e.g., BPMN, are also considered a workflow graph. Hence, an RPST can be computed on a much wider variety of process modeling formalisms, i.e., compared to the approach presented in this paper. Formally, given a workflow graph \(G_{W}{=}(V,E,w)\) (a multi-graph in which \(w\) assigns each edge in \(E\) to an ordered pair of nodes) an RPST is a hierarchy of _fragments_. A fragment is a subset \(E^{\prime}{\subseteq}E\) of arcs, s.t., the subgraph formed by \(E^{\prime}\) (including their incident vertices) is connected. Furthermore, the fragment should only contain one unique _entry vertex_ and one unique _exit vertex_. A vertex is an entry vertex iff none of its incoming arcs are part of \(E^{\prime}\) or all of its outgoing arcs are part of \(E^{\prime}\). A vertex is an exit vertex iff none of its outgoing arcs are part of \(E^{\prime}\) or all of its incoming arcs are part of \(E^{\prime}\). The RPST of a workflow graph is the set of canonical fragments, i.e., those fragments that completely contain other fragments or are completely contained by other fragments, i.e., any overlap between fragments is not allowed. In [26], the authors showed that computation of an RPST is equivalent to computing the tree of triconnected components on a _normalized_ variant of \(G_{W}\) (normalization is performed by splitting vertices with multiple different incoming and outgoing edges into two nodes). Clearly, each individual edge of a workflow graph is a fragment. Similarly, the complete set of arcs \(E\) defines a fragment. As an example, consider Figure 17, in which we present a simple example WF-net (Figure 17a) and its corresponding RPST decomposition (Figure 17b,c). Figure 16: Example application of the self-loop pattern reduction. (**a**) Simple WF-net, having self loop transitions \(t_{2}\) and \(t_{3}\). (**b**) Self-loop reduction where \(T^{\prime}{=}\{t_{2}\}\). (**c**) Self-loop reduction where \(T^{\prime}{=}\{t_{2},t_{3}\}\). The edges \((p_{i},t_{1})\) and \((t_{1},p_{1})\), visualized as \(e_{1}\) and \(e_{2}\) are part of the root fragment, i.e., \(F_{0}\), which is the complete edge set of the WF-net/workflow graph. The choice construct, i.e., connecting place \(p_{1}\) and \(p_{o}\) to transitions \(t_{2}\) and \(t_{3}\), respectively, comprises fragment \(F_{1}\), which is further subdivided into fragments \(F_{2}\) and \(F_{3}\). Note that the process tree corresponding to \(W_{2}\) is \(\rightarrow(a,\times(b,c))\), i.e., consisting of 5 vertices. Hence, to translate the RPST to the corresponding process tree, we need to \"collapse\" \(F_{2}\) and \(F_{3}\) into \(b\) and \(c\), respectively. Similarly, \(F_{1}\) needs to be transformed to \(\times\) and, \(F_{0}\) needs to be transformed to \(\rightarrow\). Finally, \(e_{1}\) and \(e_{2}\) need to be merged into \(a\). The previous example illustrates that there is no general direct correspondence between the RPST of a WF-net and a corresponding process tree that describes the same language. Furthermore, it shows that translation of the RPST to a process tree is a non-trivial operation.