## 4 Materials and Methods
### Efficient Construction of Behavior Graphs
Definition 14 describes such a baseline method for the creation of the behavior graph consisting of two main parts: the construction of the starting graph and the computation of its transitive reduction. Let us consider an uncertain process trace \(\sigma\in\mathcal{T}_{U}\) with \(|\sigma|=n\) events, and the graph \(G=(V,E)\) generated in Definition 14 before the transitive reduction. The starting graph is created by inspecting the time relationship between every pair of events; this corresponds to checking if an edge exists between each pair of vertices in \(G\), which needs \(\mathcal{O}(n^{2})\) time. The transitive reduction of graphs can be obtained through many methods. A simple and efficient method to compute the transitive reduction on sparse graphs is to test reachability through a search(either breadth-first or depth-first) from each edge. This method costs \(\mathcal{O}(V\cdot E)\) time (here, for simplicity, we resort to a widely adopted abuse of notation in asymptotic complexity analysis: we indicate a set instead of its cardinality, e.g., we use \(\mathcal{O}(V)\) in place of \(\mathcal{O}(|V|)\)). However, in the initial graph each event \(e\in V\) has an inbound arc from each event certainly preceding \(e\) and an outbound arc to each event certainly following \(e\). Fewer events with overlapping intervals as timestamps of uncertain events imply fewer arcs in \(G\); the initial graph \(G\) of a trace with no uncertainty has \(|E|=\frac{n(n-1)}{2}=\mathcal{O}(V^{2})\) edges. Thus, except for rare, very uncertain cases, the graph \(G\) is dense. [PERSON] et al. [12] presented a technique to compute the transitive reduction in \(\mathcal{O}(n^{3})\) time, more appropriate in the case of dense graphs, and proved that the transitive reduction has the same computational complexity of the matrix multiplication problem. The problem of matrix multiplication was generally regarded as having an optimal time complexity of \(\mathcal{O}(n^{3})\), until [PERSON] presented an algorithm [13] able to multiply matrices in \(\mathcal{O}(n^{2.807355})\) time. Subsequent improvements have followed, by [PERSON] and [PERSON] [14], [PERSON] [15] and [PERSON] [16]. The asymptotically fastest algorithm known to date has been illustrated by [PERSON] [17] and has an execution time of \(\mathcal{O}(n^{2.3728639})\). However, these faster algorithms are very seldomly used in practice, due to the existence of large constant factors in their computation time that are hidden by the asymptotic notation. Moreover, they have vast memory requirements. The Strassen algorithm is helpful in real-life applications only when applied on very large matrices [18], and the Coppersmith-Winograd algorithm and subsequent improvements are more efficient only with inputs so large that they are effectively classified as galactic algorithms [19]. Bearing in mind these considerations, for the vast majority of event logs, the most efficient way to implement the creation of the behavior graph via transitive reduction runs in \(\mathcal{O}(n^{2})+\mathcal{O}(n^{3})=\mathcal{O}(n^{3})\) time in the worst-case scenario. It is straightforward to find upper bounds for the complexity of Algorithms 1 and 2. Line 3 of TimestampList require \(\mathcal{O}(n\log n)\) to be executed. Lines 5-8 require \(\mathcal{O}(n)\) time. Line 9 requires \(\mathcal{O}(2n\log(2n))=\mathcal{O}(n\log n)\) time to be run. Lines 11-14 require \(2n=\mathcal{O}(n)\) time to be run. Lines 1-4 and 10 have a constant cost \(\mathcal{O}(1)\). Thus, TimestampList has a total asymptotic cost of \(\mathcal{O}(1)+2\cdot\mathcal{O}(n\log n)+2\cdot\mathcal{O}(n)=\mathcal{O}(n \log n)\) in the worst-case scenario. Let us now examine BehaviorGraph. Lines 1-3 and line 11 run in \(\mathcal{O}(1)\) time. Lines 11-30 consist of two nested loops over the list \(\mathcal{L}\), and we have \(|\mathcal{L}|=2n\), resulting in an asymptotic cost of \(\mathcal{O}((2n)^{2})=\mathcal{O}(n^{2})\).