## 4 Materials and Methods
### Efficient Construction of Behavior Graphs
The graph \(bg\) follows the behavior graph semantics: for all pairs of events \(e\in\sigma\) and \(e^{\prime}\in\sigma\) such that \(id(e)=e_{id}\), \(\pi_{a}(e)=e_{a}\), \(\pi_{o}(e)=e_{o}\), \(id(e^{\prime})=e^{\prime}_{id}\), \(\pi_{a}(e^{\prime})=e^{\prime}_{a}\), \(\pi_{o}(e^{\prime})=e^{\prime}_{o}\), we have that the node \((e_{id},e_{a},e_{o})\) is connected to the node \((e^{\prime}_{id},e^{\prime}_{a^{\prime}},e^{\prime}_{o})\) if and only if \(\pi_{t_{\max}}(e)<\pi_{t_{\min}}(e^{\prime})\) and there exists no event \(e^{\prime\prime}\in\sigma\) such that \(\pi_{t_{\max}}(e)<\pi_{t_{\min}}(e^{\prime\prime})\leq\pi_{t_{\max}}(e^{\prime \prime})<\pi_{t_{\min}}(e^{\prime})\). Thus, \(bg=\beta(\sigma)\)._  
Proof. : Let us first define a suitable \(id\) function for the behavior graph using the list \(\mathbb{E}\) created in \(\textsc{TimestampList}(\sigma)\). For all events \(e^{*}\in\sigma\) and for \(i\in\mathbb{N}\) such that \(\mathbb{E}[i]=e^{*}\), we define \(id(e^{*})=i\). Since \(id\) is just an enumeration of the events in \(\sigma\), it is trivially bijective. \((\Leftarrow)\) Assume \(\pi_{t_{\max}}(e)<\pi_{t_{\min}}(e^{\prime})\). By construction, we have that \(\mathcal{L}=\langle\ldots,(e_{id},e_{a},e_{o},\textsc{MAX}^{\prime}),\ldots,(e ^{\prime}_{id},e^{\prime}_{a},e^{\prime}_{o},\textsc{MIN}^{\prime}),\ldots\rangle\). The checks in line 6 and line 10 only allow for edges to be linked from entries of type '\(\textsc{MAX}^{\prime}\) to entries of type '\(\textsc{MIN}^{\prime}\)' that only appear in a later position in the list \(\mathcal{L}\). Thus, the configuration \(\pi_{t_{\max}}(e)<\pi_{t_{\min}}(e^{\prime})\) is a strict prerequisite for \((e_{id},e_{a},e_{o})\) and \((e^{\prime}_{id},e^{\prime}_{a},e^{\prime}_{o})\) to be connected: \(((e_{id},e_{a},e_{o}),(e^{\prime}_{id},e^{\prime}_{a},e^{\prime}_{o}))\in E \Rightarrow\pi_{t_{\max}}(e)<\pi_{t_{\min}}(e^{\prime})\). \((\Rightarrow)\) Assume \(\pi_{t_{\max}}(e)<\pi_{t_{\min}}(e^{\prime})\), and that the algorithm is currently searching the successors for the entry \((e_{id},e_{a},e_{o},\textsc{MAX}^{\prime})\). Eventually, the inner loop will consider as a successor the entry \((e^{\prime}_{id},e^{\prime}_{a},e^{\prime}_{o},\textsc{MIN}^{\prime})\), and since it is of type '\(\textsc{MIN}^{\prime}\), \((e_{id},e_{a},e_{o})\) and \((e^{\prime}_{id},e^{\prime}_{a},e^{\prime}_{o})\) will necessarily be connected unless the algorithm executes the break at line 13. To execute it, the algorithm needs to find a list entry \((e^{\prime\prime}_{id},e^{\prime\prime}_{a},e^{\prime\prime}_{o},\textsc{MAX}^ {\prime})\) such that there already exist an arc between \((e_{id},e_{a},e_{o})\) and \((e^{\prime\prime}_{id},e^{\prime\prime}_{a},e^{\prime\prime}_{o})\), and this is only possible if \((e^{\prime\prime}_{id},e^{\prime\prime}_{a},e^{\prime\prime}_{o},\textsc{MIN}^ {\prime})\) has been encountered while searching for successors of \((e_{id},e_{a},e_{o})\). This implies that  
\[\mathcal{L} =\langle\ldots,(e_{id},e_{a},e_{o},\textsc{MAX}^{\prime}),\ldots,(e^{\prime\prime}_{id},e^{\prime\prime}_{a},e^{\prime\prime}_{o},\textsc{MIN}^ {\prime}),\ldots\] \[\ldots,(e^{\prime\prime}_{id},e^{\prime\prime}_{a},e^{\prime \prime}_{o},\textsc{MAX}^{\prime}),\ldots,(e^{\prime}_{id},e^{\prime}_{a},e^{ \prime}_{o},\textsc{MIN}^{\prime}),\ldots\rangle\]  
which by construction of \(\mathcal{L}\), is only possible if there exist some \(e^{\prime\prime}\in\sigma\) such that  
\[\pi_{t_{\max}}(e)<\pi_{t_{\min}}(e^{\prime\prime})\leq\pi_{t_{\max}}(e^{\prime \prime})<\pi_{t_{\min}}(e^{\prime})\]  
As mentioned earlier, the procedure of constructing a behavior graph has been structured in two different algorithms specifically to enable further optimization in processing uncertain process trace. This becomes evident once we consider the problem of converting in behavior graphs all the traces in an event \(\log\), as opposed as one single uncertain trace. First, it is important to notice that different uncertain traces can have the same list \(\mathcal{L}\).