## 4 Materials and Methods
### Preliminaries
Given two vertices \(v,v^{\prime}\in V\), we denote with \(p_{G}(v,v^{\prime})\) the set of all paths beginning in \(v\) and ending in \(v^{\prime}\): \(p_{G}(v,v^{\prime})=\{p\in P_{G}\mid p[1]=v\wedge p[|p|]=v^{\prime}\}\). \(v\) and \(v^{\prime}\) are connected (and \(v^{\prime}\) is reachable from \(v\)), denoted by \(v\overset{G}{\mapsto}v^{\prime}\), if and only if there exists a path between them in \(G\): \(p_{G}(v,v^{\prime})\
eq\emptyset\). Conversely, \(v\overset{G}{\
ot\mapsto}v^{\prime}\Leftrightarrow p_{G}(v,v^{\prime})=\emptyset\). We drop the superscript \(G\) if it is clear from the context. A directed graph \(G\) is acyclic if there exists no path \(p\in P_{G}\) satisfying \(p[1]=p[|p|]\)._  
**Definition 7** (Topological sorting). : _Let \(G=(V,E)\) be an acyclic directed graph. A topological sorting [11]\(o_{G}=\langle v_{1},v_{2},\ldots,v_{|V|}\rangle\in\mathcal{S}_{V}\) is a permutation of the vertices of \(G\) such that for all \(1\leq i<j\leq|V|\) we have that \(v_{j}\
ot\mapsto v_{i}\). We denote with \(\mathcal{O}_{G}\subseteq\mathcal{S}_{V}\) all such possible topological sortings over \(G\)._  
**Definition 8** (Transitive reduction). : _A transitive reduction [12]\(\rho\colon\mathcal{G}\to\mathcal{G}\) of a graph \(G=(V,E)\) is a graph \(\rho(G)=(V,E_{r})\) with \(E_{r}\subseteq E\) where every pair of vertices connected in \(\rho(G)\) is not connected by any other path: for all \((v,v^{\prime})\in E_{r}\), \(p_{G}(v,v^{\prime})=\{\langle v,v^{\prime}\rangle\}\). \(\rho(G)\) is the graph with the minimal number of edges that maintain the reachability between edges of \(G\). The transitive reduction of a directed acyclic graph always exists and is unique [12]._  
This paper proposes an analysis technique on _uncertain event logs_. These execution logs contain information about uncertainty explicitly associated with event data. A taxonomy of different types of uncertain event logs and attribute uncertainty has been described in [2]; we will refer to the notion of _simple uncertainty_, which includes uncertainty without probabilistic information on the control-flow perspective: activities, timestamps, and indeterminate events. **Definition 9** (Universes). : _Let \(\mathcal{U}_{I}\) be the set of all the event identifiers. Let \(\mathcal{U}_{C}\) be the set of all case ID identifiers. Let \(\mathcal{U}_{A}\) be the set of all the activity identifiers. Let \(\mathcal{U}_{T}\) be the totally ordered set of all the timestamp identifiers. Let \(\mathcal{U}_{O}=\{!,?\}\), where the \"!\" symbol denotes determinate events, and the \"?\" symbol denotes indeterminate events._  
**Definition 10** (Simple uncertain events). : \(e=(e_{i},A,t_{min},t_{max},o)\) _is a simple uncertain event, where \(e_{i}\in\mathcal{U}_{E}\) is its event identifier, \(A\in\mathcal{P}_{NE}(\mathcal{U}_{A}\) is the set of possible activity labels for \(e\), \(t_{min}\) and \(t_{max}\) are the lower and upper bounds for the value of its timestamp, and \(o\) indicates if it is an indeterminate event. Let \(\mathcal{U}_{E}=(\mathcal{U}_{I}\times\mathcal{P}_{NE}(\mathcal{U}_{A})\times \mathcal{U}_{T}\times\mathcal{U}_{T}\times\mathcal{U}_{O})\) be the set of all simple uncertain events. Over the uncertain event \(e=(e_{i},A,t_{min},t_{max},o)\) we define the projection functions \(\pi_{a}(e)=A\), \(\pi_{t_{min}}(e)=t_{min}\), \(\pi_{t_{max}}(e)=t_{max}\) and \(\pi_{o}(e)=o\)._  
**Definition 11** (Simple uncertain traces and logs). : \(\sigma\subseteq\mathcal{U}_{E}\) _is a simple uncertain trace if for any \((e_{i},A,t_{min},t_{max},o)\in\sigma\), \(t_{min}<t_{max}\) and all the event identifiers are unique. \(\mathcal{T}_{U}\) denotes the universe of simple uncertain traces. \(L\subseteq\mathcal{T}_{U}\) is a simple uncertain log if all the event identifiers in the log are unique._  
**Definition 12** (Strict partial order over simple uncertain events). : _Let \(e,e^{\prime}\in\mathcal{E}^{S}_{U}\) be two simple uncertain events.