## 4 Materials and Methods
### Efficient Construction of Behavior Graphs
A review of related work on the topic of the asymptotic complexity of the transitive reduction and the equivalent problem of matrix multiplication is provided with the complexity analysis of the algorithms examined by this paper, in Section 5. ## 8 Conclusions

The creation of the behavior graphs--a graphical structure of paramount importance for the analysis of uncertain data in the domain of process mining--plays a key role as initial processing step for both conformance checking and process discovery of process traces containing events with timestamp uncertainty, the most critical type of uncertain behavior. It allows, in fact, to represent the time relationship between uncertain events, which can be in a partial order. The behavior graph also carries the information regarding other types of uncertainty, like uncertain activity labels and indeterminate events. Such a representation is vital to establish which possible sequence of events in an uncertain trace most adhere to the behavior prescribed by a reference model, thereby enabling conformance checking; and to measure the number of possible occurrences of the directly-follows relationship between activities in an event log, making process discovery over uncertainty possible. Extracting behavior graphs from uncertain event data is thus concomitantly crucial and time consuming. In this paper, we show an improvement for the performance of uncertainty analysis by proposing a new algorithm that enables the creation of behavior graphs in quadratic time in the number of events in the trace. This novel method additionally allows for the representation of an uncertain log as a multiset of behavior graphs, which relevance is two-fold: it allows the representation of the control-flow information of an uncertain event log in a more compact manner by using less memory, and naturally extends the concept of variant--central throughout the discipline of process mining--to the uncertain domain. We proved the correctness of this novel algorithm, we showed asymptotic upper and lower bounds for its time complexity, and implemented performance experiments for this algorithm that effectively show the gain in computing speed it entails in real-world scenarios. The conceptualization and methodology of this research was a collaborative effort shared among all authors. Other tasks were divided as follows: software and experiment implementation, result analysis and draft preparation, M.P. ; editing, critical reviewing, supervising, M.S.U. and W.M.P.v.d.A. ; funding acquisition, W.M.P.v.d.A. All authors have read and agreed to the published version of the manuscript. We thank the Alexander von Humboldt (AvH) Stiftung for supporting our research interactions. The authors declare no conflict of interest. ## References

* (1) [PERSON] [PERSON]. _Process Mining: Data Science in Action_; Springer: Berlin/Heidelberg, Germany, 2016. * (2) [PERSON]; [PERSON]. Mining uncertain event data in process mining. In Proceedings of the 2019 International Conference on Process Mining (ICPM), Aachen, Germany, 24-26 June 2019; pp. 89-96. * (3) [PERSON], [PERSON]; [PERSON] [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] [PERSON]; [PERSON]; [PERSON] [PERSON]; [PERSON] [PERSON]; [PERSON] [PERSON]; et al. Process mining manifesto. In _International Conference on Business Process Management_; Springer: Berlin/Heidelberg, Germany, 2011; pp. 169-194. * (4) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] The assessment of data quality issues for process mining in healthcare using Medical Information Mart for Intensive Care III, a freely available e-health record database. _Health Inform. J._**2019**, _25_, 1878-1893. [CrossRef] [PubMed]
* (5) [PERSON]; [PERSON] [PERSON]; [PERSON], [PERSON]. Efficient construction of behavior graphs for uncertain event data. In _International Conference on Business Information Systems (BIS)_; Springer: Berlin/Heidelberg, Germany, 2020. * (6) [PERSON]; [PERSON] [PERSON]; [PERSON], [PERSON]. Process Mining for Python (PM4 Py): Bridging the Gap Between Process- and Data Science.