## 4 Materials and Methods
### Efficient Construction of Behavior Graphs
Similarly to directly-follows relationships in more classical process mining, which can ignore the amount of time in absolute terms elapsed between two consecutive events, specific values of timestamps in an uncertain trace are not necessarily meaningful with respect to the connection in the behavior graph; their order, conversely, is crucial. This fact enables further optimization at the \(\log\) level. The construction of the list \(\mathcal{L}\) in \(\textsc{TimestampList}(\sigma)\) is engineered in a way that allows for computing the behavior graph without direct lookup to the events in the trace. This implies that it is possible to extract a multiset of lists \(\mathcal{L}\) from the event \(\log\), and to compute the conversion to behavior graph only for the set of lists induced by this multiset. This allows the saving of computation time in converting an entire event \(\log\) to behavior graphs; furthermore, it enables a more compact representation of the \(\log\) in memory, since we only need to store a smaller number of graphs to represent the whole \(\log\). The procedure to efficiently convert an event \(\log\) into graphs is detailed in Algorithm 3. ```
1:\(\leftarrow\)

**Definition 15** (Uncertain variants). : _Let \(L\subseteq\mathcal{T}_{U}\) be a simple uncertain event log. The variants of \(L\) denoted by \(\mathcal{V}_{L}\), are the multisets of behavior graphs for the uncertain traces in \(L\), and are computed with ProcessUncertainLog\((L)\)._

The computational advantage in representing a log through a multiset of behavior graphs is evident in the procedure described in Algorithm 2. We see that all data necessary to the creation of a behavior graph is contained in the list \(\mathcal{L}\), fact that justifies the log representation method illustrated in Algorithm 3. ```
Input : An uncertain log \(L\). Output : A multiset of behavior graphs \(BG\). \(\mathit{ML}\leftarrow[\,]\) \(\mathcal{V}_{L}\leftarrow[\,]\) for\(\sigma\in L\)do \(\mid\mathit{ML}\leftarrow\mathit{ML}\uplus[\textsc{TimestampList}(\sigma)]\) end for for\(\mathcal{L}\in\mathit{ML}\)do \(\mid\mathcal{V}_{L}\leftarrow\mathcal{V}_{L}\uplus[\textsc{BehaviorGraph}( \mathcal{L})^{\textsc{ML}(\mathcal{L})}]\) end return\(BG\)
```

**Algorithm 3**ProcessUncertainLog

**Lemma 1**. : _Two uncertain traces \(\sigma_{1}\in L\) and \(\sigma_{2}\in L\) belong to the same variant, and share the same behavior graph, if and only if they result in the same timestamp list \(\mathcal{L}\): \(\textsc{TimestampList}(\sigma_{1})=\textsc{TimestampList}(\sigma_{2})\)._

Another central concept in process mining is the so-called _control-flow perspective_ of event data. In certain process traces, where timestamps have a total order, events have a single activity label and no event is indeterminate, the control-flow information is represented by a sequence of activity labels sorted by timestamp. Although there are many analysis approaches that also account for other perspectives (e.g., the performance perspective that considers the duration of events and their distance in time, or the resource perspective that accounts for the agents that execute the activities), a vast amount of process mining techniques, including most popular algorithms for process discovery and conformance checking, rely only on the control-flow perspective of a process. Analogously, behavior graphs carry over the control-flow information of an uncertain trace: instead of describing the flow of events like their certain counterpart, the behavior graph describes all possible flows of events in the uncertain trace. ## 5 Asymptotic Complexity

In this section, we will provide some values for the asymptotic complexity of the algorithms seen in this paper. In a previous paper [2] we introduced the concept of behavior graph for the representation of uncertain event data, together with a method to obtain such graphs.