# Translating Workflow Nets to Process Trees: An Algorithmic Approach
## Preliminaries
### Pattern Reduction
The fragment formed by \(p_{1}\), \(p_{3}\), \(p_{5}\), \(t_{2}\), and \(t_{4}\), is a feasible sequence pattern. In Figure 7b, we depict the reduced counterpart of the net in Figure 7a, in which transitions \(t_{2}\) and \(t_{4}\), and the place connecting them, i.e., \(p_{3}\), are replaced by transition \(t_{2}^{\prime}\) with label \(\rightarrow(a,c)\). Observe that the language of the original net (Figure 7a) is \(\{\left\{t_{1},t_{2},t_{3},t_{4},t_{5}\right\},\left\langle t_{1},t_{3},t_{2}, t_{4},t_{5}\right\rangle,\left\langle t_{1},t_{2},t_{4},t_{3},t_{5}\right\rangle\}\), whereas the language of the corresponding reduced net (Figure 7b) is \(\{\left\langle t_{1},t_{2}^{\prime},t_{3},t_{5}\right\rangle,\left\langle t_{1},t_{3},t_{2}^{\prime},t_{5}\right\rangle\}\). Consequently, the corresponding labeled languages are \(\{\left\langle a,b,c\right\rangle,\left\langle b,a,c\right\rangle,\left\langle a,c,b\right\rangle\}\) and \(\{\left\langle\rightarrow(a,c),b\right\rangle,\left\langle b,\rightarrow(a,c) \right\rangle\}\), respectively. The labeled language of the reduced net, after evaluating the process tree fragments inside, yields \(\{\left\langle a,c,b\right\rangle,\left\langle b,a,c\right\rangle\}\), i.e., the trace \(\left\langle a,b,c\right\rangle\) is not in the corresponding language. However, if we first unfold the label of \(t_{2}^{\prime}\) in Figure 7b, i.e., yielding the model in Figure 7a (modulo renaming of transitions), the labeled languages of the two nets are indeed equal, i.e., they both describe \(\{\left\langle a,b,c\right\rangle,\left\langle b,a,c\right\rangle,\left\langle a,c,b\right\rangle\}\). Furthermore, observe that there exist feasible patterns that are locally language-preserving, yet, not globally language-preserving. For example, consider the WF-net in Figure 8. The place-bordered fragment formed by the subnet consisting of places \(p_{1}\) and \(p_{2}\) and transitions \(t_{2}\) and \(t_{3}\) (with the arcs connecting them), form a feasible pattern corresponding to \(\circlearrow(a,b)\) (with \(M_{i}{=}[p_{1}]\) and \(M_{f}{=}[p_{2}]\)). However, note that, after reduction, i.e., by inserting \(t_{2}^{\prime}\), we obtain a WF-net that no longer has the same language as the original model. This is because, before reduction, executing transition \(t_{5}\) allows us to enable transition \(t_{3}\). After reduction, however, this is no longer possible. Hence, whereas the observed feasible pattern is locally language preserving, i.e., when considering the elements it is composed of, it is not globally language-preserving. In the upcoming paragraphs, we characterize an instantiation of a global language preserving feasible pattern for each process tree operator considered in this paper. For each proposed pattern, we prove that it is both locally and globally language preserving. Figure 8: Example WF-net (and a corresponding reduction) in which we are able to detect feasible patterns (\(\circlearrowleft(a,b\right)\) and \(\circlearrowleft(c,d\right)\)) that are not globally language preserving. In the exemplary reduced net (Figure 8b), once we have executed \(t_{2}^{\prime}\), we are only able to execute the loop construct between \(t_{4}\) and \(t_{5}\). **(a)** The WF-net containing two local language equivalent feasible patterns. **(b)** The (PTree)WF-net after reduction of the loop pattern between \(t_{2}\) and \(t_{3}\).