## 4 Materials and Methods
### Preliminaries
\((\prec,\mathcal{E}^{S}_{U})\) is an order defined on the universe of strongly uncertain events \(\mathcal{E}^{S}_{U}\) as:_  
\[e\prec e^{\prime}\Leftrightarrow\pi_{t_{\max}}(e)<\pi_{t_{\min}}(e^{\prime})\]  
**Definition 13** (Order-realizations of simple uncertain traces). : _Let \(\sigma\in\mathcal{T}_{U}\) be a simple uncertain trace. An order-realization \(\sigma_{O}=\langle e_{1},e_{2},\ldots,e_{|\sigma|}\rangle\in\mathcal{S}_{\sigma}\) is a permutation of the events in \(\sigma\) such that for all \(1\leq i<j\leq|\sigma|\) we have that \(e_{j}\
ot<e_{i}\), i.e., \(\sigma_{O}\) is a correct evaluation order for \(\sigma\) over \((\prec,\mathcal{E}^{S}_{U})\), and the (total) order in which events are sorted in \(\sigma_{O}\) is a linear extension of the strict partial order \((\prec,\mathcal{E}^{S}_{U})\). We denote with \(\mathcal{R}_{O}(\sigma)\) the set of all such order-realizations of the trace \(\sigma\)._  
A necessary step to allow for analysis of simple uncertain traces is to obtain their _behavior graph_. A behavior graph is a directed acyclic graph that synthesizes the information regarding the uncertainty on timestamps contained in the trace. **Definition 14** (Behavior graph). : _Let \(\sigma\in\mathcal{T}_{U}\) be a simple uncertain trace. Let the identification function \(id\colon\sigma\to\{1,2,\ldots,|\sigma|\}\) be a bijection between the events in \(\sigma\) and the first \(|\sigma|\) natural numbers. A behavior graph \(\beta\colon\mathcal{T}_{U}\to\mathcal{U}_{G}\) is the transitive reduction of a directed graph \(\rho(G)\), where \(G=(V,E)\in\mathcal{U}_{G}\) is defined as:_  
* \(V=\{(id(e),\pi_{a}(e),\pi_{o}(e))\mid e\in\sigma\}\)__
* \(E=\{(v,w)\mid v,w\in V\wedge\pi_{t_{\max}}(v)<\pi_{t_{\min}}(w)\}\)__  
_The set of topological sortings of a behavior graph \(\beta(\sigma)\) corresponds to the set of all the order-realizations of the trace \(\sigma\):_  
A technical note: this definition for the nodes of the behavior graph is slightly different from the one in [2], to simplify the notation in algorithms. The two definitions are functionally identical. Figures 6 and 7 show the transitive reduction operation on the running example. The semantics of a behavior graph can efficaciously communicate time and order information concerning the time relationships among events in the corresponding uncertain trace in a compact manner. For a behavior graph \(\beta(\sigma)=(V,E)\) and two events \(e_{1}\in\sigma\), \(e_{2}\in\sigma\), \((e_{1},e_{2})\in E\) holds if and only if \(e_{1}\) is immediately followed by \(e_{2}\) for some possible values of the timestamps of the events in the  
Figure 6: The behavior graph of the trace in Table 1 before applying the transitive reduction. All the nodes in the graph are pairwise connected based on precedence relationships; pairs of nodes for which the order is unknown are not connected. Figure 7: The same behavior graph after the transitive reduction. The arc between \(e_{1}\) and \(e_{4}\) is removed, since they are reachable through \(e_{2}\). This graph has a minimal number of arcs while conserving the same reachability relationship between nodes. trace. A consequence of this fact is that if a pair of events in the graph are unreachable, they might have occurred in any order. Definition 14 is meaningful and clear from a theoretical point of view. It rigorously defines a behavior graph and the semantics of its parts. Although helpful to understand the function of behavior graphs, obtaining them from process traces following this definition--that is, using the transitive reduction--is inefficient and slow. This hinders the analysis of logs with a large number of events, and with longer traces. It is nonetheless possible to build behavior graphs from process traces in a faster and more efficient way.