The “Timestamp” field indicates either the moment in time in which the event has happened, or the interval of time in which the event may have happened. The “Activity” field indicates the possible choices for the activity instantiated by the event. Lastly, the “Indeterminate event” field contains a “!” if the corresponding event has surely occurred, and a “?” if it might have been recorded despite not occurring in reality. For the sake of readability, in the timestamps column only reports the day of the month. event has been recorded while certainly occurring in reality, i.e., it has been recorded correctly in the information system (e.g., the event \(e_{4}\)). Quality problems and imprecision in data recording such as the ones described in the running example as source of uncertainty are not uncommon; in some settings, they are a frequent occurrence. Healthcare processes are specifically know to be afflicted by these sorts of data anomalies, especially if parts of the process rely on recording information on paper [3; 4]. Existing process mining software cannot manage such uncertain event data. When mining the processes where uncertainty in execution data is prominent, a natural first approach is to filter the event log eliminating cases where uncertainty appear. Unfortunately, in processes with a large portion of cases are affected by such data anomalies, filtering without losing essential information about the process is not feasible. Consequently, new process mining methods to inspect and analyze it must be developed. Uncertain timestamps are the most prominent and critical source of uncertain behavior in a process trace. For example, if \(n\) events have uncertain timestamps such that their order is unknown, the possible configurations that the control-flow of the trace can assume are all the \(n!\) permutations of the events, in the case where all events in a case have timestamps defined by mutually overlapping intervals. This is the worst possible scenario in terms of amount of uncertain behavior introduced by uncertainty on the timestamps of the events ins a trace. Thus, it is important to capture the time relationships between events in a compact and effective way. This is accomplished by the construction of a _behavior graph_, a directed acyclic graph that expresses precedence between events. Figure 1 shows the behavior graph of the process trace in Table 1; every known precedence relationship between events is represented by the edges of the graph, while the pairs of event for which the order is unknown remain unconnected. Effectively, this creates a representation of the partial order where the arcs are defined by the possible values of the timestamps contained in the trace, and where the nodes may refer to sets of possible activities. As we will see, this construct is central to effectively implement both process discovery and conformance checking applied to uncertain event data. In a previous paper [5], we presented a time-effective algorithm for the construction of the behavior graph of an uncertain process trace, attaining quadratic time complexity on the number of events in the trace. This paper elaborates on this previous result, by providing the proof of the correctness of the new algorithm. Additionally, we will show the improvement in performance both theoretically, via asymptotic complexity analysis, and in practice, with experiments on various uncertain event logs comparing computation times of the baseline method against the novel construction algorithm. Furthermore, the version of the algorithms presented in this paper is refined so to preprocess uncertain traces in linear time, individuating the variants--which share the same behavior graph-, and proceed to perform the construction of the behavior graph only once per variant.