# Translating Workflow Nets to Process Trees: An Algorithmic Approach
## Preliminaries
### Workflow Nets  
Workflow nets (WF-nets) [15] extend the more general notion of Petri nets [16]. A Petri net is a _directed bipartite graph_ containing two types of vertices, i.e., places and transitions. We visualize places as circles, whereas we visualize transitions as boxes. Places only connect to transitions and vice versa. Consider Figure 3, depicting an example Petri net (which is also a WF-net). We let \(N{=}(P,T,F,\ell)\) denote a labeled Petri net, where, \(P\) denotes a set of places, \(T\) denotes a set of transitions and \(F{\subseteq}(P{\times}T)\cup(T{\times}P)\) represents the arcs. Furthermore, given a set of labels \(\Sigma\) and the symbol \(\tau{\
otin}\Sigma\), \(\ell\): \(T{\rightarrow}\Sigma{\cup}\{\tau\}\) is the net's labelling function, e.g., in Figure 3, \(\ell(t_{1}){=}a\), \(\ell(t_{2}){=}b\), etc. Given an element \(x{\in}P{\cup}T\), \(\bullet x=\{y\mid(y,x){\in}F\}\) denotes the _pre-set_ of \(x\), whereas \(x\bullet=\{y|(x,y){\in}F\}\) denotes its _post-set_, e.g., in Figure 3, \(\bullet t_{1}{=}\{p_{i}\}\) and \(p_{1}\bullet=\{t_{2},t_{3}\}\). We lift the \(\bullet\)-notation to the level of sets, i.e., given \(X{\subseteq}P{\cup}T\), \(\bullet X{=}\{y\mid\exists x{\in}X(y{\in}\bullet x)\}\) and \(X\bullet=\{y\mid\exists x{\in}X(y{\in}\bullet\bullet)\}\). Let \(N{=}(P,T,F,\ell)\) be a Petri net and let \(P^{\prime}{\subseteq}P\), \(T^{\prime}{\subseteq}T\) and \(F^{\prime}=F{\cap}((P^{\prime}{\times}T^{\prime})\cup(T^{\prime}{\times}P^{ \prime}))\). The Petri net \(N^{\prime}{=}(P^{\prime},T^{\prime},F^{\prime},\ell|_{T^{\prime}})\) is a _subnet_ of \(N\), written \(N^{\prime}{\sqsubseteq}N\). In the context of this paper, we refer to a subnet \(N^{\prime}{\sqsubseteq}N\) as a _fragment_ if it is _weakly connected_. Furthermore, a fragment \(N^{\prime}{\sqsubseteq}N\) is _place-bordered_ iff the only vertices of \(N^{\prime}\) (i.e., members of \(P^{\prime}{\cup}T^{\prime}\)) that are connected to vertices that do not belong to \(N^{\prime}\) (i.e., members of \(P{\cup}T{\setminus}(P^{\prime}{\cup}T^{\prime})\)) are places, i.e., \(\{x{\in}P^{\prime}{\cup}T^{\prime}\mid(x,y){\in}F{\setminus}F^{\prime}{ \vee}(y,x){\in}F{\setminus}F^{\prime}\}{\subseteq}P^{\prime}\). Furthermore, we refer to \(P^{\prime}_{i}{=}\{x{\in}P^{\prime}|(y,x){\in}F{\setminus}F^{\prime}\}\) and \(P^{\prime}_{o}{=}\{x{\in}P^{\prime}|(x,y){\in}F{\setminus}F^{\prime}\}\) to the _input_ and _output places_ of the place-bordered fragment. For example, in Figure 3, the subnet formed by places \(p_{1}\), \(p_{2}\), \(p_{3}\), \(p_{4}\), \(p_{5}\), transitions \(t_{2}\), \(t_{3}\), \(t_{4}\), \(t_{5}\) and the arcs \((p_{1},t_{2})\), \((p_{1},t_{3}),\ldots,(t_{5},p_{5})\) is a place-bordered fragment. Observe that, if we remove place \(p_{5}\) (and the corresponding arc \((t_{5},p_{5})\)), the subnet is still a fragment, yet, no longer place-bordered. If we also remove \(t_{5}\) and the arcs \((p_{3},t_{5})\) and \((p_{4},t_{5})\), the subnet is not a fragment as it is no longer weakly connected. We let \(\mathcal{N}\) denote the universe of Petri nets. The _state_ of a Petri net is expressed by means of a _marking_, i.e., a multiset of places. A marking is visualized by drawing the corresponding number of dots in the place(s) of the marking, e.g., the marking in Figure 3 is \([p_{i}]\) (one black dot is drawn inside place \(p_{i}\)). Given a Petri net \(N=(P,T,F,\ell)\) and marking \(M{\in}\mathcal{M}(P)\), \((N,M)\) denotes a _marked net_. Given a marked net \((N,M)\), a transition \(t{\in}T\) is _enabled_, written \((N,M)[t]\), if \(\forall p{\in}\bullet{\
otin}\,(M(p){>}0)\). If a transition is _not enabled_ in marking \(M\), we write \((N,M)[\![t]\!]\). An enabled transition can _fire_, leading to a new marking \(M^{\prime}{=}\,(M{-}\bullet{\
otin}\,)\uplus\bullet\bullet\), written \((N,M)\xrightarrow{t}(N,M^{\prime})\).