Timed Anti-Alignments for Acyclic Marked Graphs

This paper addresses conformance checking in a time-aware setting, that relates the timing of recorded events in the log with the time constraints of the process model specified as a Time Petri Net. To evaluate whether a model reflects the observed executions, several quality criteria were proposed. We define the Timed Anti-Alignment Problem as finding model traces whose timing most deviate from observed log traces. Anti-alignments, as witnesses for imprecision of the model, were proposed in untimed settings to measure precision. We solve the Purely Timed Anti-Alignment Problem for Acyclic Time Marked Graphs. By framing the problem as an optimization task with linear constraints, we enable the use of efficient Linear Programming solvers. Finally, we test our implementation's performance to understand its practicability.