## 2 Conformance Checking over Uncertain Data  
Conformance checking is one of the main tasks in process mining, and consists of measuring the deviation between process execution data (usually in the form of a trace) and a reference model. This is particularly useful for organization, since it enables them to compare historical process data against a normative model created by process experts to identify anomalies and deviations in their operations. Let us assume that we have access to a normative model for the disease of the patient in the running example, shown in Figure 2.  
This model essentially states that the disease is characterized by the occurrence of night sweats and splenomegaly on the patient, which can be verified concurrently, and then should be followed by primary thrombocytopenia. We would like to measure the conformance between the trace in Table 1 and this normative model. A very popular conformance checking technique works via the computation of _alignments_[7]. Through this technique, we are able to identify the deviations in the execution of a process, in the form of behavior happening in the model but not in the trace, and behavior happening in the trace but not in the model. These deviations are identified, and used as basis to compute a conformance score between the trace and the process model. The formulation of alignments in [7] is not applicable to an uncertain trace. In fact, depending on the instantiation of the uncertain attributes of events--like the timestamp of \(e_{3}\) in the trace--the order of event may differ, and so may the conformance score. However, we can look at the best- and worst-case scenarios: the instantiation of attributes of the trace that entails the minimum and maximum number of deviations with respect to the reference model. In our example, two possible outcomes for the sample trace are \(\langle\)_NightSweats_, _Splenomeg_, _PrTP_, _Adm_\(\rangle\) and \(\langle\)_SecTP_, _Splenomeg_, _Adm_\(\rangle\); both represent the sequence of event that might have happened in reality, but their conformance score is very different. The alignment of the first trace against the reference model can be seen in Table 2, while the alignment of the second trace can be seen in Table 3. These two outcomes of the uncertain  
Figure 2: A normative model for the healthcare process case in the running example. The initial marking is displayed; the gray “token slot” represents the final marking. trace in Table 1 represent, respectively, the minimum and maximum amount of deviation possible with respect to the reference model, and define then a lower and upper bound for conformance score. The minimum and maximum bounds for conformance score of an uncertain trace and a reference process model can be found with the uncertain version of the alignment technique that we first described in [2]. To find such bounds, it is necessary to build a Petri net able to simulate all possible behaviors in the uncertain trace, called the _behavior net_. Obtaining a behavior net is possible through a construction that uses behavior graphs as a starting point, using the structural information therein contained to connect places and transitions in the net. The behavior net of the trace in Table 1 is shown in Figure 3.  
The alignments in Tables 2 and 3 show how we can get actionable insights from process mining over uncertain data. In some applications it is reasonable and appropriate to remove uncertain data from an event log via filtering, and then compute log-level aggregate information--such as total number of deviations, or average deviations per trace--using the remaining certain data. Even in processes where this is possible, doing so prevents the important process mining task of case diagnostic. Conversely, uncertain alignments allow not only to have best- and worst-case scenarios for a trace, but also to individuate the specific deviations affecting both scenarios. For instance, the alignments of