## 4 Materials and Methods
### Efficient Construction of Behavior Graphs  
The set of steps to efficiently create a behavior graph from an uncertain trace is separated into two distinct phases, described by Algorithms 1 and 2. An uncertain event \(e\) is associated with a time interval which is determined by two values: minimum and maximum timestamp of that event \(\pi_{t_{\min}}(e)\) and \(\pi_{t_{\max}}(e)\). If an event \(e\) has a certain timestamp, we have that \(\pi_{t_{\min}}(e)=\pi_{t_{\max}}(e)\). We will examine here the effect of Algorithms 1 and 2 on a running example, the process trace shown in Table 4. Notice that in this running example, no uncertainty on activity labels nor indeterminate events are present: this is because of the fact that the topology of a behavior graph only depends on the (uncertain) timestamps in the events belonging to the corresponding trace. ```
Input : An uncertain trace \(\sigma\). Output : The list of timestamps \(\mathcal{L}\) of \(\sigma\). \(\mathcal{L}^{*}\leftarrow\langle\ \rangle\) ; // Support list \(\mathcal{L}\leftarrow\langle\ \rangle\) ; // List of event attributes \(\mathbb{E}\leftarrow\textsc{Sort}(\sigma)\) ; // Sorts uncertain events by minimum timestamp \(i\gets 1\) while\(i\leq|\mathbb{E}|\)do \(\mathcal{L}^{*}\leftarrow\mathcal{L}^{*}\oplus(\pi_{t_{\min}}(e),i,e,^{\prime} \textsc{MIN}^{\prime})\) \(\mathcal{L}^{*}\leftarrow\mathcal{L}^{*}\oplus(\pi_{t_{\max}}(e),i,e,^{\prime} \textsc{MAX}^{\prime})\) \(i\gets i+1\)  end whileSort(\(\mathcal{L}^{*}\)) ; // Sorts the list based on timestamp value \(i\gets 1\) while\(i\leq|\mathcal{L}^{*}|\)do \((t,id,e,\mathit{type})\leftarrow\mathcal{L}^{*}[i]\) \(\mathcal{L}\leftarrow\mathcal{L}\oplus(id,\pi_{a}(e),\pi_{o}(e),\mathit{type})\) \(i\gets i+1\)  end while return\(\mathcal{L}\)
```  
**Algorithm 1**TimestampList(\(\sigma\)) \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Case ID** & **Event ID** & **Activity** & **Timestamp** & **Event Type** \\ \hline
872 & \(e_{1}\) & a & 5 December 2011 &! \\
872 & \(e_{2}\) & b & [6 December 2011, 10 December 2011] &! \\
872 & \(e_{3}\) & c & 7 December 2011 &! \\
872 & \(e_{4}\) & d & [8 December 2011, 11 December 2011] &! \\
872 & \(e_{5}\) & e & 9 December 2011 &! \\
872 & \(e_{6}\) & f & [12 December 2011, 13 December 2011] &! \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Running example for the creation of the behavior graph. ```
Input : The list \(\mathcal{L}=\textsc{TimestampList}(\sigma)\) of an uncertain trace \(\sigma\). Output : The behavior graph \(\beta(\sigma)=(V,E)\). \(V\leftarrow\{(id,\pi_{a}(e),\pi_{o}(e))\mid(id,\pi_{a}(e),\pi_{o}(e),type)\in \mathcal{L}\}\) \(E\leftarrow\varnothing\) \(i\gets 1\) while\(i<|\mathcal{L}|\)do \((id,a,o,type)\leftarrow\mathcal{L}[i]\) if\(type=\textit{`MAX'}\)then \(j\gets i+1\) while\(j\leq|\mathcal{L}|\)do \((id^{*},a^{*},o^{*},type^{*})\leftarrow\mathcal{L}[j]\) if\(type^{*}=\textit{`MIN'}\)then \(E\gets E\cup\{((id,a,o),(id^{*},a^{*},o^{*}))\}\) elseif\(((id,a,o),(id^{*},a^{*},o^{*}))\in E\)then break  end if \(j\gets j+1\)  end if  end if \(i\gets i+1\)  end while return\((V,E)\)
```  
**Algorithm 2**BehaviorGraph(TimestampList(\(\sigma\)))  
The construction of the graph relies on a preprocessing step shown in Algorithm 1, where a support list \(\mathcal{L}\) is created (lines 4-8). Every entry in this list is a tuple of four elements. For each event \(e\) in the trace, we insert two entries in the list--one for each timestamp \(\pi_{t_{\min}}\) and \(\pi_{t_{\max}}\) appearing in a trace. The four elements in each tuple contained in the list are:  
* an _identifier_, which in the list construction is an integer representing the rank of the uncertain event by minimum timestamp (computed in line 3);
* the activity labels associated with the event \(\pi_{a}(e)\);
* the attribute \(\pi_{o}(e)\), which will carry the information regarding indeterminate events;
* the type of timestamp that generated this entry--if it is a minimum or maximum of an interval.