## 4 Materials and Methods
### Efficient Construction of Behavior Graphs
The work introducing the concept of uncertainty in process mining, together with a taxonomy of the various types of uncertainty, specifically illustrated that if a trace displays uncertain attributes, it contains behavior, which can be effectively represented through graphical models--specifically, behavior graphs and behavior nets [2]. Differently to classic process mining, where we have a clearly defined separation between data and model and between the static behavior of data and the dynamic behavior of models, the distinction between data and models becomes more unclear in the presence of uncertainty, because of the variety in behavior that affects the data. Representing traces through process models is used in [2] for the computation of upper and lower bounds for conformance scores of uncertain process traces against classic reference models. Another practical application of behavior graphs in the field of process mining over uncertain event data is presented in [8]. Behavior graphs of uncertain traces are employed to determine the number of possible directly-follows relationships between uncertain events, with the end goal of automatically discovering process models from uncertain event data. Albeit, as said, the application of the concept of uncertainty in data to process mining is recent, the same idea has precedents in the older field of data mining. [PERSON] and [PERSON] [21] offer an overview of the topic of uncertain data and its analysis, with a strong focus on querying. Such data is modeled based on probabilistic databases [22], a foundational concept in the setting of uncertain data mining. A branch of data mining particularly close to process mining is frequent itemsets mining: an efficient algorithm to search for frequent itemsets over uncertain data, the U-Apriori, have been described by [PERSON] et al. [23]. Behavior graphs are Directed Acyclic Graphs (DAGs), which are widely used throughout many areas of science to represent with a graph-like model dependencies, precedence relationships, time information, or partial orders. They are effectively used in circular dependency analysis in software [24], probabilistic graphical models [25], dynamic graphs analytics [26], and compiler design [27]. In process mining, _Conditional Partial Order Graphs_ (CPOGs)--which consist of collections of DAGs--have been exploited by [PERSON] et al. [28] to aid the task of process discovery. We have seen throughout the paper that uncertainty on the timestamp dimension--specifically, representing at which time an event occurred with an interval of possible timestamps--generates, on the precedence relationships of events, a partial order. Although uncertainty research in process mining provides a novel justification of partial ordering that spawns from specific attribute values, the idea of having a partial order instead of a total order among events in a trace has precedents in process mining research. [PERSON] et al. [29; 30] examined the problem of conformance checking through alignments in the case of partially ordered traces, and developed a construct to represent conformance called a _p-alignment_. [PERSON] et al. [31] devised a method to identify highly frequent anomalous patterns in partially ordered process traces. More recently, [PERSON] et al. [32] developed a probabilistic infrastructure that allows an inference of the most likely linear extension of a partial order between events in a trace, with the goal of \"resolving\" the partial order. An important aspect to notice is that conformance checking over uncertain event data is not to be confused with stochastic conformance checking, which concerns measuring conformance of certain event data against models enriched with probabilistic information. The probabilities decorating a stochastic model do not derive from uncertainties in event data, but rather from frequency of activities [33] or from performance indicators [34].