## 4 Materials and Methods
### Efficient Construction of Behavior Graphs
As we can see, the list is designed to contain all information about an uncertain event except the values of minimum and maximum timestamps, which we use to sort the list (line 9) and then discard prior to returning the list (lines 10-15). The events of the trace in Table 4 are represented in the list \(\mathcal{L}^{*}\) by entries shown in Table 5. These entries are then sorted by Algorithm 1 yielding the following list \(\mathcal{L}\):  
\[\mathcal{L}=\langle(1,\{a\},\textit{!,'MIN'}),(1,\{a\},\textit{!,'MAX'}),(2,\{ b\},\textit{!,'MIN'}),(3,\{c\},\textit{!,'MIN'}),\]  
\[(3,\{c\},\textit{!,'MAX'}),(4,\{d\},\textit{!,'MIN'}),(5,\{e\},\textit{!,'MIN' }),(5,\{e\},\textit{!,'MAX'}),\]  
\[(2,\{b\},\textit{!,'MAX'}),(4,\{d\},\textit{!,'MAX'}),(6,\{f\},\textit{!,'MIN' }),(6,\{f\},\textit{!,'MAX'})\rangle\]One of the purposes the list \(\mathcal{L}\) serves is gathering the structural information to create the behavior graph; in fact, visiting the list in order is equivalent of sweeping the events of the trace on the time dimension, encountering each timestamp (minimum or maximum) sorted through time. We can visualize this on the Gantt diagram representation of the trace of Table 4, visible in Figure 8.  
Every segment representing an uncertain event in the diagram is translated by TimestampList into two entries in a sorted list, representing the two extremes of the segment. Events without an uncertain timestamp collapse into a single point in the diagram, and their corresponding two entries in the list are characterized by the same timestamp. Now, let us examine Algorithm 2. The idea leading the algorithm is to analyze the time relationship among uncertain events in a more precise manner, as opposed to adding a large number of edges to the graph and then removing them via transitive reduction. This is attained by searching all the viable successors of each event in the sorted timestamp list \(\mathcal{L}\). We scan the list \(\mathcal{L}\) with two nested loops, and we use the inner loop to look for successors of the entry selected by the outer loop. According to the semantics of behavior graphs, events with overlapping intervals as timestamps must not be connected  
Figure 8: A Gantt diagram visualizing the time perspective of the events in Table 4. The horizontal blue bars represent the interval of possible timestamps of uncertain events: such interval is ample for the event with activity label “c”, which has an uncertain timestamp, and is narrow to indicate a precise point in time for the other events. This diagram can show the order relationship between events in a trace, as well as the dimensions of their interval of possible timestamps in scale. \begin{table}
\begin{tabular}{c c c} \hline \multirow{2}{*}{**Event**} & **List \(\mathcal{L}^{*}\) Entry** & **List \(\mathcal{L}^{*}\) Entry** \\  & **(Minimum Timestamp)** & **(Maximum Timestamp)** \\ \hline \(e_{1}\) & (5 December 2011, 1, \(\{a\}\),!, 'MIN') & (5 December 2011, 1, \(\{a\}\),!, 'MAX') \\ \(e_{2}\) & (6 December 2011, 2, \(\{b\}\),!, 'MIN') & (10 December 2011, 2, \(\{b\}\),!, 'MAX') \\ \(e_{3}\) & (7 December 2011, 3, \(\{c\}\),!, 'MIN') & (7 December 2011, 3, \(\{c\}\),!, 'MAX') \\ \(e_{4}\) & (8 December 2011, 4, \(\{d\}\),!, 'MIN') & (8 December 2011, 4, \(\{d\}\),!, 'MAX') \\ \(e_{5}\) & (9 December 2011, 5, \(\{e\}\),!, 'MIN') & (9 December 2011, 5, \(\{e\}\),!, 'MAX') \\ \(e_{6}\) & (12 December 2011, 6, \(\{f\}\),!, 'MIN') & (13 December 2011, 6, \(\{f\}\),!, 'MAX') \\ \hline \end{tabular}
\end{table} 
Table 5: Entries for the list \(\mathcal{L}\) generated by each event in the uncertain trace. Every event \(e\) has two associated entries, one marked as ’MIN’ and the other as ’MAX’. Each entry is a 4-uple containing an integer that acts as event identifier, the set of possible activity labels \(\pi_{a}(e)\) of the uncertain event, the indeterminate event attribute \(\pi_{o}(e)\), and the type of timestamp (‘MIN’ or ’MAX’).