# Translating Workflow Nets to Process Trees: An Algorithmic Approach
## Preliminaries
### Basic Notation  
Given set \(X\), \(\mathcal{P}(X){=}\left\{X^{\prime}\subseteq X\right\}\) denotes its powerset. Given a function \(f\colon X{\to}Y\) and \(X^{\prime}{\subseteq}X\), we extend function application to sets, i.e., \(f(X^{\prime}){=}\{y|\exists x\in X^{\prime}(f(x){=}y)\}\). Furthermore, \(f|_{X^{\prime}}\colon X^{\prime}{\to}Y\) restricts \(f\) to \(X^{\prime}\). A multiset over set \(X\), i.e., \(m\colon X{\to}\mathbb{N}\cup\{0\}\), contains multiple instances of an element. We write a multiset as \(m{=}[x_{1}^{i},x_{2}^{j},...,x_{n}^{k}]\), where \(m(x_{1}){=}i\), \(m(x_{2}){=}j\), \(...\), \(m(x_{n}){=}k\), for \(i,j,...\), \(k{>}1\) (in case, \(m(x_{i}){=}1\), we omit its superscript; in case \(m(x_{i}){=}0\), we omit \(x_{i}\)). The set of all multisets over \(X\) is written as \(\mathcal{M}(X)\). Given \(m{\in}\mathcal{M}(X)\), we write \(x{\in}_{+}m\) if \(m(x){>}0\), and, \(x{\
otin}_{+}m\) if \(m(x){=}0\), and, \(\overline{m}{=}\{x|x{\in}_{+}m\}\). For example, the multiset \([x^{2},y]\) consists of two instances of \(x\), one instance of \(y\), and zero instances of \(z\). The sum of two multisets \(m_{1},m_{2}\) is written as \(m_{1}{\uplus}m_{2}\), e.g., \([x^{2},y]{\uplus}[x^{3},y,z]{=}[x^{5},y^{2},z]\), and their difference is written as \(m_{1}{-}m_{2}\), e.g., \([x^{2},y]{-}[x,y,z]{=}[x]\). A set is considered a multiset in which each element appears only once. Hence, we also apply the operations defined for multisets on sets, and, on combinations of sets and multisets, e.g., \(\{x,y,z\}{\uplus}[x^{2}]{=}[x^{3},y,z]\). A sequence is an ordered collection of elements, e.g., a sequence \(\sigma\) of length \(n\) over base set \(X\) is a function \(\sigma\colon\{1,...,n\}{\to}X\). We write \(|\sigma|\) to denote the length of \(\sigma\), e.g., \(|\sigma|{=}n\). We write \(\sigma{=}\langle\sigma(1),\sigma(2),...,\sigma(|\sigma|)\rangle\), where \(\sigma(i)\) denotes the element at position \(i\), (1\({\leq}i{\leq}|\sigma|\)). \(\epsilon\) denotes the empty sequence, i.e., \(|\epsilon|{=}0\). We extend the notion of element inclusion to sequences, e.g., \(x{\in}\langle x,y,z\rangle\). \(X^{*}\) denotes the set of all sequences over members of set \(X\). Concatenation of sequences \(\sigma,\sigma^{\prime}{\in}X^{*}\) is written as \(\sigma{\cdot}\sigma^{\prime}\). We let \(\sigma{\coloneqq}\sigma^{\prime}\) denote the set of all possible order-preserving merges, i.e., the _shuffle operator_, of \(\sigma\) and \(\sigma^{\prime}\), e.g., given \(\sigma_{1}{=}\langle b,p\rangle\), \(\sigma_{2}{=}\langle m\rangle\), then \(\sigma_{1}{\coloneqq}\sigma_{2}{=}\left\{\langle b,p,m\rangle,\langle b,m,p \rangle,\langle m,b,p\rangle\right\}\). It is easy to see that \(\sigma{=}\sigma^{\prime}{=}\sigma^{\prime}{\coloneqq}\sigma\) (the operator is commutative). We extend the shuffle operator to sets (and overload notation), i.e., given \(S,S^{\prime}{\in}X^{*}\), \(S{\uplus}S^{\prime}{=}\{\sigma{\in}\sigma_{1}{\coloneqq}\sigma_{2}\mid\sigma_{ 1}{\in}S_{1}{\wedge}\sigma_{2}{\in}S_{2}\}\). Note that \((\sigma{\coloneqq}\sigma^{\prime}){\coloneqq}\{\sigma^{\prime\prime}\}=\{ \sigma{\coloneqq}(\sigma^{\prime}{\coloneqq}\sigma^{\prime\prime})\) (associative); hence, we write the application of the shuffle operation on \(n\) sequences as \(\sigma_{1}{\coloneqq}\sigma_{2}{\coloneqq}\cdots{\coloneqq}\sigma_{n}\). Similarly, we write \(S_{1}{\coloneqq}S_{2}{\coloneqq}\cdots{\coloneqq}S_{n}\) for sets of sequences \(S_{1},S_{2},...S_{n}{\in}X^{*}\). Given a function \(f\colon X{\to}Y\) and a sequence \(\sigma{\in}X^{*}\), we overload notation for function application, i.e., \(f(\sigma){=}\langle f(\sigma(1),f(\sigma(2)),...,f(\sigma|\sigma|)\rangle\). We extend the notion of sequence application to sets of sequences, i.e., given \(f\colon X\to Y\) and \(X^{\prime}{\subseteq}X^{*}\), \(f(X^{\prime}){=}\{\sigma{\in}Y^{*}\mid\exists\sigma^{\prime}{\in}X^{\prime} (f(\sigma^{\prime}){=}\sigma)\}\).