Translating Workflow Nets to Process Trees:
An Algorithmic Approach

Workflow nets (WF-nets) [2] extend the more general notion of Petri nets [14]. A Petri net is a directed bipartite graph containing two types of vertices, i.e., places and transitions. Places are visualized as circles, transitions are visualized as boxes. Places only connect to transitions, and vise-versa. Consider 1(a), depicting an example Petri net (which is also a WF-net).

We let $N{=}(P,T,F,\ell)$ denote a (labelled) 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 symbol $\tau{\notin}\Sigma$, $\ell{\colon}T{\to}\Sigma{\cup}\{\tau\}$ is the net’s labelling function, e.g., in 1(a), $\ell(t_{1}){=}a$, $\ell(t_{2}){=b}$, etc. Given an element $x{\in}P{\cup}T$, ${\bullet}x=\left\{y\mid(y,x){\in}F\right\}$ denotes the pre-set of $x$, whereas $x{\bullet}{=}\left\{y|(x,y){\in}F\right\}$ denotes its post-set, e.g., in 1(a), ${\bullet}{t_{1}}{=}\left\{p_{i}\right\}$ and $p_{1}{\bullet}{=}\left\{t_{2},t_{3}\right\}$. We lift the $\bullet$-notation to the level of sets, i.e., given $X{\subseteq}P{\cup}T$, $\bullet{X}{=}\left\{y\mid\exists{x{\in}X}\left(y{\in}{\bullet}x\right)\right\}$ and ${X}{\bullet}{=}\left\{y\mid\exists{x{\in}X}\left(y{\in}x{\bullet}\right)\right\}$. Let $N{=}(P,T,F,\ell)$, let $P^{\prime}{\subseteq}P$, $T^{\prime}{\subseteq}T$ and $F^{\prime}{\subseteq}F$. The net $N^{\prime}{=}\left(P^{\prime},T^{\prime},F^{\prime},\ell|_{T^{\prime}}\right)$ is a subnet of $N$, written $N^{\prime}{\sqsubseteq}N$. 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 1(a) 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}{\rangle}$, if $\forall{p{\in}{\bullet}{t}}\left(M(p){>}0\right)$. An enabled transition can fire, leading to a new marking $M^{\prime}{=}\left(M{\setminus}{\bullet}t\right){\uplus}{t}{\bullet}$, written $(N,M){\xrightarrow{t}}(N,M^{\prime})$. A sequence of transition firings $\sigma{=}\langle t_{1},t_{2},...,t_{n}\rangle$ is a firing sequence of $(N,M)$, yielding marking $M^{\prime}$, written $(N,M){\xrightarrow[]{\sigma}\mathrel{\mkern-14.0mu}\rightarrow}(N,M^{\prime})$, iff $\exists M_{1},M_{2},...,M_{n-1}{\in}\mathcal{M}(P)$ s.t. $(N\mathchar 44\relax\penalty 0M){\xrightarrow{t_{1}}}(N\mathchar 44\relax\penalty 0M_{1}){\xrightarrow{t_{2}}}(N\mathchar 44\relax\penalty 0M_{2}){\cdots}(N\mathchar 44\relax\penalty 0M_{n-1}){\xrightarrow{t_{n}}}(N\mathchar 44\relax\penalty 0M^{\prime})$. We write $(N,M){\rightsquigarrow}(N,M^{\prime})$, in case $\exists{\sigma{\in}T^{*}}\left((N,M){\xrightarrow[]{\sigma}\mathrel{\mkern-14.0mu}\rightarrow}(N,M^{\prime})\right)$. $\mathcal{L}_{\mathcal{N}}(N\mathchar 44\relax\penalty 0M\mathchar 44\relax\penalty 0M^{\prime})=\left\{\sigma{\in}T^{*}\mid(N\mathchar 44\relax\penalty 0M){\xrightarrow[]{\sigma}\mathrel{\mkern-14.0mu}\rightarrow}(N\mathchar 44\relax\penalty 0M^{\prime})\right\}$ denotes all firing sequences starting from marking $M$, leading to marking $M^{\prime}$. The labelled-language of $N$, conditional to markings $M,M^{\prime}$, is defined as $\mathcal{L}_{\mathcal{N}}^{\nu}(N\mathchar 44\relax\penalty 0M\mathchar 44\relax\penalty 0M^{\prime}){=}\ell(\mathcal{L}_{\mathcal{N}}(N\mathchar 44\relax\penalty 0M\mathchar 44\relax\penalty 0M^{\prime}))_{\downarrow_{\Sigma}}$. $\mathcal{R}(N\mathchar 44\relax\penalty 0M)=\left\{M^{\prime}{\in}\mathcal{M}(P)\mid\exists{\sigma{\in}T^{*}}\left((N\mathchar 44\relax\penalty 0M)\xrightarrow[]{\sigma}\mathrel{\mkern-14.0mu}\rightarrow(N\mathchar 44\relax\penalty 0M^{\prime})\right)\right\}$ denotes the reachable markings.

Given a Petri net $N{=}\left(P,T,F,\ell\right)$, and designated initial and final marking $M_{i}\mathchar 44\relax\penalty 0M_{f}{\in}\mathcal{M}(P)$, triple $SN{=}(N,M_{i},M_{f})$ denotes a system net. As system net $SN{=}(N,M_{i},M_{f})$ is formed by $N$, we write $SN$ as a replacement for $N$, e.g., $(SN,M)$ denotes a marked system net. Clearly, $\mathcal{R}(SN,M)$, $\mathcal{L}_{\mathcal{N}}(SN,M,M^{\prime})$, etc., are readily defined. $\mathcal{SN}$ denotes the universe of system nets.

A WF-net is a special type of Petri net, i.e., it has one unique start and one unique end place. Furthermore, every place/transition in the net is on a path from the start to the end place.

Of particular interest are sound WF-nets, i.e., WF-nets that are, by definition, guaranteed to be free of deadlocks and livelocks. We formalize the notion of soundness in 2.

Observe that, the Petri net depicted in 1(a), is a sound WF-net.

Process trees allow us to model processes, that comprise a control-flow hierarchy. A process tree is a mathematical tree, where the internal vertices are operators and leaves are (non-observable) activities. Operators specify how their children, i.e., sub-trees, need to be combined, from a control-flow perspective.

Several operators (elements of $\bigoplus$) can be defined, however, in this work, we focus on four basic operators, i.e., the $\to$, $\times$, $\wedge$ and $\circlearrowleft$-operator. The sequence operator ($\to$) specifies sequential behavior. First its left-most child is executed, then its second left-most child, …, and finally its right-most child. For example, the root operator in 1(b), specifies that first activity $a$ is executed, then its second sub-tree ($\circlearrowleft$) and then its third sub-tree ($\times$). The exclusive choice operator $(\times)$, specifies an exclusive choice, i.e., one (and exactly one) of its sub-trees is executed. Concurrent/parallel behavior is represented by the concurrency operator ($\wedge$), i.e., all children are executed simultaneously/in any order. Repeated behavior is represented by the loop operator $\circlearrowleft$. The $\to$, $\times$ and $\wedge$-operator have an arbitrary number of children. The $\circlearrowleft$-operator has two children. Its left child (the “do-child”) is always executed. Secondly, executing its right child (the “re-do-child”) is optional. After executing the re-do-child, we again execute the do-child. We are allowed to repeat this, yet, we always finish with the do-child.

Given a process tree $Q{\in}\mathcal{Q}$, its language is of the form $\mathcal{L}_{\mathcal{Q}}(Q){\subseteq}\Sigma^{*}$.

The process tree operators considered ($\to$, $\times$, $\wedge$ and $\circlearrowleft$), are easily translated to sound WF-nets, cf. Fig. 2. Hence, we define a generic process tree to WF-net translation function, s.t., the language of the two is the same.

Given an arbitrary process tree $Q{\in}\mathcal{Q}$, there are several ways to translate it to a (sound) WF-net $W$, s.t., $\mathcal{L}_{\mathcal{N}}^{\nu}(W){=}\mathcal{L}_{\mathcal{Q}}(Q)$, i.e., instantiating $\lambda$ and $\hat{\lambda}$. As an example, consider the translation functions, depicted in Fig. 2.

Note that, each transformation function in Fig. 2, is sound by construction. Hence, we deduce that their recursive composition is also a sound [1, Theorem 3.3].

The core idea of the approach, concerns searching for fragments in the given WF-net, that represent behavior that is expressible as a process tree. The patterns we look for, bear great similarity with the translation patterns defined in Fig. 2, i.e., they can be considered as a generalized reverse of those patterns. When we find a pattern, we replace it with a smaller net fragment that represents the process tree that was just found. We continue to search for patterns in the reduced net, until we are not able to find any more patterns. As we prove in Section 3.4, in case the final WF-net contains just one transition, in fact, its label carries a process tree with the same labelled-language as the original WF-net.

Consider Fig. 3, in which we sketch the basic idea of the algorithm, applied on the example WF-net $W_{1}$ (1(a)).

First, the algorithm detects two choice constructs, i.e., one between the transitions labelled $b$ and $c$, and, one between the transitions labelled $g$ and $h$. The algorithm replaces the fragments by means of two new transitions, carrying labels $\times(b,c)$ and $\times(g,h)$ respectively (3(a)). Subsequently, a parallel construct is detected, i.e., between the transitions labelled $\times(b,c)$ and $d$. Again, the pattern is replaced (3(b)). A sequential pattern is detected and replaced (3(c)), after which a loop construct is detected (3(d)). The resulting process tree, i.e., carried by the remaining transition in 3(e), $\to(a,\circlearrowleft(\to(\wedge(\times(b,c),d),e),f),\times(g,h))$, is equal to 1(b).

The core idea of the proposed algorithm presented, is finding Petri net fragments in the WF-net, that represent 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.

Given $\tilde{N}{\in}\mathcal{N}_{\mathcal{Q}}$, we have $\tilde{\ell}\left(\mathcal{L}_{\mathcal{N}}\left(\tilde{N},M,M^{\prime}\right)\right){\in}\mathcal{Q}^{*}$, and, $\mathcal{L}_{\mathcal{Q}}\left(\tilde{\ell}\left(\mathcal{L}_{\mathcal{N}}\left(\tilde{N},M,M^{\prime}\right)\right)\right){\in}\Sigma^{*}$, i.e., the definition of $\mathcal{L}_{\mathcal{Q}}$ ignores $\tau{\notin}{\Sigma}$.¹¹1 Observe: $\mathcal{L}_{\mathcal{N}}^{\nu}\left(\tilde{N},M,M^{\prime}\right){=}\tilde{\ell}\left(\mathcal{L}_{\mathcal{N}}\left(\tilde{N},M,M^{\prime}\right)\right)_{\downarrow_{\Sigma}}{=}\mathcal{L}_{\mathcal{Q}}\left(\tilde{\ell}\left(\mathcal{L}_{\mathcal{N}}\left(\tilde{N},M,M^{\prime}\right)\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.

Since a PTree-net contains process trees as labels, which can be translated into a Petri net fragment, we define a PTree-net unfolding, cf. 7, which maps a PTree-net onto a corresponding conventional Petri net.

Note that, the WF-net in 1(a), is the unfolding of all PTree-WF-nets in Fig. 3.

In this section, we describe four patterns, used to identify and replace process tree behavior. Furthermore, we propose a corresponding overarching reduction function, which shows how to reduce a PTree-WF-net containing any of these patterns. However, first, we present the general notion of a feasible pattern.

In the upcoming paragraphs, we characterize an instantiation of a feasible $\oplus$-pattern, for each operator considered.