1. Computing alignments with maximum synchronous moves via replay in coordinate planes
- Author
-
Hui Yan, Uzay Kaymak, Pieter Van Gorp, Xudong Lu, Shan Nan, Huilong Duan, Information Systems IE&IS, JADS Den Bosch (TU/e), JADS Research, EAISI Foundational, EAISI Health, and Signal Processing Systems
- Subjects
Event logs ,Information Systems and Management ,Synchronous moves ,Artificial Intelligence ,Control and Systems Engineering ,Business process models ,Heuristic strategy ,Conformance check ,Software ,Computer Science Applications ,Theoretical Computer Science ,Optimal alignments - Abstract
Optimal alignments are the basis of conformance checking. For long, researchers have been devoted to the efficiency issue of computing optimal alignments. This paper focuses on the optimality issue. Specifically, we aim to find alignments with maximum synchronous moves and minimum deviations. This paper introduces a coordinate-plane search space, which allows enumerating all the possible alignments. The alignments with maximum synchronous moves are translated into the lowest-cost paths, such that heuristic strategies (such as the Dijkstra algorithm) can be applied. Both theoretical proof and experimental results show that 100% optimality can be achieved.
- Published
- 2022