Computational Complexity of Alignments

In process mining, alignments quantify the degree of deviation between an observed event trace and a business process model and constitute the most important conformance checking technique. We study the algorithmic complexity of computing alignments over important classes of Petri nets. First, we show that the alignment problem is PSPACE-complete on the class of safe Petri nets and also on the class of safe and sound workflow nets. For live, bounded, free-choice systems, we prove the existence of optimal alignments of polynomial length which positions the alignment problem in NP for this class. We further show that computing alignments is NP-complete even on basic subclasses such as process trees and T-systems. We establish NP-completeness on several related classes as well, including acyclic systems. Finally, we demonstrate that on live, safe S-systems the alignment problem is solvable in P and that both assumptions (liveness and safeness) are crucial for this result.