# Translating Workflow Nets to Process Trees: An Algorithmic Approach
## 5 Related Work  
Process trees are often used in the domain of process mining. However, a complete overview of the field is outside of scope, i.e., we refer to [1] for a gentle introduction. Similarly, we refer to [21] for an in-depth overview of process discovery algorithms, and, we refer to [22] for an overview of the sub-field of conformance checking. The conceptual idea of transforming a given process model in a certain formalism \(F\) into an alternative process modeling formalism \(F^{\prime}\) is well-studied. Transformations of _graph-oriented_ modeling formalisms, e.g., Petri nets, and _block-oriented_ modeling formalisms, e.g., Process Trees, are often studied. In [10], the authors generalize work that transforms (both ways) graph-based process modeling formalisms into _Business Process Execution Language for Webservices (BPEL)_ (an XML-based format). The authors characterize several strategies for such translations. In this context, the work presented in this paper belongs to the _structure-identification_ category. Of particular interest is the work of [PERSON] and [PERSON] [23; 24], i.e., on translating of WF-nets to BPEL. In the work, XML fragments of BPEL are generated on the basis of a given WF-net. Since XML, by definition, is a tree-like data representation, BPEL and process trees are conceptually close. The algorithm replaces _components_, i.e., connected, complete subnets with a unique start and end element, i.e., such a start/end element can be either a place or a transition. The authors prove that \"folding\" a WF-net based on an identified component, under certain conditions, yields a sound WF-net. The folding operator for components as defined in [23] can be regarded as being very similar to the reduction (cf. Definition 9) presented in this paper. However, note that the proofs in [23] only hold for components, i.e., subnets with a single entry and exit. The algorithm described in [23] is similar to the algorithm presented in this paper, i.e., searching and replacing patterns until either a WF-net with a single transition is found, or no more pattern is found. However, within the algorithm, a specific ordering for the patterns and a maximization of the pattern-size is applied. Observe that, whereas the work in [23; 24] is conceptually close to the work presented here, there are several differences as well. Figure 14: Average time performance of the implementation. A quadratic relation, in computation time measured in micro-seconds (\(\mu\)-seconds), with respect to the size of the WF-net, is observable. For example, in this work, we use system nets to represent patterns, i.e., lifting the single source/sink requirement for pattern recognition. As such, the algorithm presented in this paper is able to detect process tree fragments in WF-nets, in which the algorithm reported on in [23; 24] would not find any fragments. Similarly, the algorithm presented in this paper does not impose any order on the reduction of the patterns identified, nor on their size. However, there is no clear motivation provided in [23] on the underlying reasons for imposing an order and maximization with respect to pattern detection. In [25; 26], the notion of the _Refined Process Structure Tree_ (RPST) and its computation is introduced. The RPST is a hierarchical grouping of the edges present in a process model (defined as a _workflow graph_). As such, the given process model can be decomposed, i.e., on the basis of the hierarchy described by the RPST. Similar to the work in [23; 24], the identified model-fragments need a single source and a single sink element. The works in [25; 26] exemplify computing the RPST of a given BPMN model (which complies with the definition of the workflow graphs mentioned earlier), yet indicate that the concepts can be generalized to WF-nets. However, as we show in Section 6.2, the fact that the RPST, by definition, ignores the semantics of the model provided as an input leads the algorithm to find tree structures in unsound Workflow nets.