  While supporting the execution of business processes, information systems
record event logs. Conformance checking relies on these logs to analyze whether
the recorded behavior of a process conforms to the behavior of a normative
specification. A key assumption of existing conformance checking techniques,
however, is that all events are associated with timestamps that allow to infer
a total order of events per process instance. Unfortunately, this assumption is
often violated in practice. Due to synchronization issues, manual event
recordings, or data corruption, events are only partially ordered. In this
paper, we put forward the problem of partial order resolution of event logs to
close this gap. It refers to the construction of a probability distribution
over all possible total orders of events of an instance. To cope with the order
uncertainty in real-world data, we present several estimators for this task,
incorporating different notions of behavioral abstraction. Moreover, to reduce
the runtime of conformance checking based on partial order resolution, we
introduce an approximation method that comes with a bounded error in terms of
accuracy. Our experiments with real-world and synthetic data reveal that our
approach improves accuracy over the state-of-the-art considerably.
