## 4 Materials and Methods
### Efficient Construction of Behavior Graphs
by a path; thus, we draw outgoing edges from an event only when, reading the list, we arrive at a point in time in which the event has certainly occurred. This is the reason outgoing edges are not drawn when inspecting minimum timestamps (line 6) and incoming edges are not drawn when inspecting maximum timestamps (line 10). First, we initialize the set of nodes with all the triples \((id,\pi_{a}(e),\pi_{o}(e))\) in the entries of \(\mathcal{L}\), and we initialize the edges with an empty set (lines 1-2). For each maximum timestamp that we encounter in the list, we start searching for successors in the following entries (lines 3-9), so we proceed in looking for the successors of \((id,a,o,\textit{type})\) only if \(\textit{type}=\textit{`MAX'}\). If, while searching for successors of the entry \((id,a,o,\textit{`MAX'})\), we encounter the entry \((id^{*},a^{*},o^{*},\textit{type}^{*})\) corresponding to a minimum timestamp (\(\textit{type}^{*}=\textit{`MIN'}\)), we connect \((id,a,o)\) and \((id^{*},a^{*},o^{*})\) in the graph, since their timestamps do not have any possible value in common. The search for successors must continue, since it is possible that other events took place before the maximum timestamp of the event corresponding to \((id^{*},a^{*},o^{*},\textit{type}^{*})\). This configuration occurs for events \(e_{1}\) and \(e_{3}\) in Table 4. As can be seen in Figure 8, \(e_{3}\) can indeed follow \(e_{1}\), but the still undiscovered event \(e_{2}\) is another possible successor for \(e_{1}\). If the entry \((id^{*},a^{*},o^{*},\textit{type}^{*})\) corresponds to a maximum timestamp (line 12), so \(\textit{type}^{*}=\textit{`MAX'}\), there are two separate situations to consider. Case 1: \((id,a,o)\) was not already connected to \((id^{*},a^{*},o^{*})\). Then, the timestamps of the events corresponding to \((id,a,o)\) and \((id^{*},a^{*},o^{*})\) overlap with each other--if they did not, the two nodes would have already been connected, since we would have encountered \((id^{*},a^{*},o^{*},\textit{`MIN'})\) from \((id,a,o,\textit{`MAX'})\) before encountering \((id^{*},a^{*},o^{*},\textit{`MAX'})\). Thus, \((id,a,o)\) must not be connected to \((id^{*},a^{*},o^{*})\) and the search must continue. Events \(e_{3}\) and \(e_{4}\) are an example: when the maximum timestamp of \(e_{4}\) is encountered during the search for the successor of \(e_{3}\), the two are not connected, so the search for a viable successor of \(e_{3}\) has to continue. Case 2: \((id,a,o)\) and \((id^{*},a^{*},o^{*})\) are already connected. This means that we had already encountered \((id^{*},a^{*},o^{*},\textit{`MIN'})\) during the search for the successors of \((id,a,o)\). Since the entire time interval representing the possible timestamp of the event associated with \((id^{*},a^{*},o^{*})\) is detected after the occurrence of \((id,a,o)\), there are no further events to consider as successors of \((id,a,o)\) and the search stops (line 13). In the running example, this happens between \(e_{5}\) and \(e_{6}\): when searching for the successors of \(e_{5}\), we first connect it with \(e_{6}\) when we encounter its minimum timestamp; we then encounter its maximum timestamp, so no other successive event can be a successor for \(e_{5}\). This concludes the walkthrough of the procedure, which shows why Algorithms 1 and 2 can be used to correctly compute the behavior graph of a trace. The behavior graph of the trace in Table 4 obtained through this procedure is shown in Figure 9.  
Let us now prove, in more formal terms, the correctness of these algorithms. We will show that the procedures BehaviorGraph and TimestampList are able to construct a behavior graph with the semantics illustrated in Definition 14. Figure 9: The behavior graph of the trace in Table 4.  
**Theorem 1** (Correctness of the behavior graph construction). : _Let \(\sigma\in\mathcal{T}_{U}\) be an uncertain trace. Let \(bg=(V,E)=\textsc{BehaviorGraph}(\textsc{TimestampList}(\sigma))\) be the behavior graph of \(\sigma\) obtained through Algorithms 1 and 2.