A Full Picture in Conformance Checking: Efficiently Summarizing All Optimal Alignments
摘要
Conformance checking using alignments allows organizations to identify deviations between process executions and the language of a process model. Applications typically derive insights from one cost-minimal alignment per process execution. This offers just one possible explanation for the observed deviations amongst potentially infinitely, and hence incomputably many cost-minimal alignments. In this paper, we define skip alignments on sound block-structured workflow nets, also known as process trees. They represent sets of alignments by lifting deviations to moves on higher-level process structures. We introduce a canonical normal form on skip alignments and show that the set of all cost-minimal skip alignments in normal form is minimal in capturing the deviations from all cost-minimal alignments. We provide an algorithm to efficiently compute all cost-minimal skip alignments in normal form and demonstrate its computational advantage.