# Translating Workflow Nets to Process Trees: An Algorithmic Approach
## Preliminaries
### PTree-Nets and Their Unfolding  
As indicated, we aim to find Petri net fragments in the WF-net representing behavior equivalent to a process tree. As illustrated in Section 3.1, the patterns found in the WF-net are replaced by transitions with a label carrying a corresponding process tree. In the upcoming section, we present four different fragment characterizations, corresponding to the basic process tree operators considered. However, in this section, we first briefly present PTree-nets, i.e., a trivial extension of Petri nets, in which labels are process trees.  
**Definition 6** (Process Tree-labeled Petri-net (PTree-net)).: _Let \(\mathcal{Q}\) denote the universe of process trees. Let \(P\) denote a set of places, let \(T\) denote a set of transitions, let \(F\subseteq(P\times T)\cup(T\times P)\) denote the arc relation and let \(\kappa\): \(T\rightarrow\mathcal{Q}\). Tuple \(N=(P,T,F,\kappa)\) is a Process Tree-labeled Petri net (PTree-net). \(\mathcal{N}_{\mathcal{Q}}\) denotes the universe of PTree-nets._  
Given \(N\in\mathcal{N}_{\mathcal{Q}}\), for any marking \(M,M^{\prime}\), we have \(\kappa\left(\mathcal{L}_{\mathcal{N}}\left(N,M,M^{\prime}\right)\right)\in \mathcal{Q}^{*}\) and \(\mathcal{L}_{\mathcal{Q}}\left(\kappa\left(\mathcal{L}_{\mathcal{N}}\left(N,M,M^{\prime}\right)\right)\right)\in\Sigma^{*}\), i.e., the definition of \(\mathcal{L}_{\mathcal{Q}}\) ignores \(\tau\
ot\in\Sigma\) (observe: \(\mathcal{L}_{\mathcal{N}}^{\
u}\left(N,M,M^{\prime}\right)=\kappa\left( \mathcal{L}_{\mathcal{N}}\left(N,M,M^{\prime}\right)\right)\)). Clearly, since PTree-nets extend the labelling function to \(\mathcal{Q}\), PTree-System-nets, and PTree-WF-nets are readily defined. We let \(\mathcal{SN}_{\mathcal{Q}}\) and \(\mathcal{W}_{\mathcal{Q}}\) represent their respective universes. Note that we use a different symbol to indicate whether a labeling function maps to \(\mathcal{Q}\) or \(\Sigma\cup\{\tau\}\), i.e., \(\kappa\): \(T\rightarrow\mathcal{Q}\), whereas \(\ell\): \(T\rightarrow\Sigma\cup\{\tau\}\).  
Since a PTree-net contains process trees as its labels, which can be translated into a Petri net fragment, we define a PTree-net _unfolding_, cf. Definition 7, which maps a PTree-net onto a corresponding conventional Petri net.  
**Definition 7** (PTree-net Unfolding).: _A PTree-net unfolding \(\Lambda\colon\mathcal{N}_{\mathcal{Q}}\rightarrow\mathcal{N}\) is a function where, given \(N=(P,T,F,\kappa)\in\mathcal{N}_{\mathcal{Q}}\), \(\Lambda(N)=(P^{\prime},T^{\prime},F^{\prime},\ell)\), with:_  
1. \(P^{\prime}=P\cup\bigcup\limits_{t\in T}\hat{P}_{t}\)_,_
2. \(T^{\prime}=\bigcup\limits_{t\in T}\hat{T}_{t}\)_,_
3. \(F^{\prime}=\bigcup\limits_{t\in T}\hat{F}_{t}\cup\bigcup\limits_{t\in T}\{(p, t)\mid p\in\bullet t\wedge t\in p_{i}\bullet\}\cup\bigcup\limits_{t\in T}\{(t,p)\mid p \in t\bullet\wedge t\in\bullet p_{o_{t}}\}\)_,_
4. \(\ell=\bigcup\limits_{t\in T}\hat{\ell}_{t}\)_. (Since functions are binary Cartesian products, we write set operations here)._  
Observe that, under the assumption that we use the instantiation of \(\lambda\) as shown in Figure 5, indeed, each transition in the unfolding of a PTree-net has a corresponding label in \(\Sigma\cup\{\tau\}\). Furthermore, note that unfolding the WF-net in Figure 5(a) yields the original model in Figure 3. The unfolding of the other WF-nets in Figure 6 yields a different WF-net. However, the language of all unfolded WF-nets remains equal to the language of the WF-net in Figure 3.