Technical Report with Proofs for A Full Picture in Conformance Checking: Efficiently Summarizing All Optimal Alignments

Philipp Bär, Moe T. Wynn, Sander J. J. Leemans · 2025

Read Technical Report with Proofs for A Full Picture in Conformance Checking: Efficiently Summarizing All Optimal Alignments by Philipp Bär, Moe T. Wynn, Sander J. J. Leemans (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-10345.txt.

Introduction

Philipp Bär, Moe Wynn, and Sander Leemans wrote a technical report in 2025 that gives full proofs for a companion paper on conformance checking. That field compares a recorded process log with a model of how the process should run. The companion paper claims a way to sum up all best alignments between log and model in an efficient way. The report's sole job is to prove those claims in detail. Readers who need the math behind the method, rather than its use, are the audience.

Catalog record

CREATORPhilipp Bär, Moe T. Wynn, Sander J. J. Leemans
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-10345

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Technical Report with Proofs for A Full Picture in Conformance Checking: Efficiently Summarizing All Optimal Alignments Philipp Bär, Moe T. Wynn, Sander J. J. Leemans Abstract 4 Summarizing Alignments with Skip Alignments 4.1 Skip Alignments Lemma 7 (Finite) ​​A trace and an SB​WF​-net have finitely many skip alignments . Proof Assume a trace \sigma has infinitely many skip alignments on an SBWF-net N . The number of synchronous and log moves is limited by |\sigma| . Since N is finite, only finitely many different skip moves exist. Hence, for every n>0 there must exist a skip alignment \delta such that |\delta|>n . Only loop blocks in N can contribute to an unbounded length of \delta . Therefore, from some m>0 on, all skip alignments \delta with |\delta|>n and n\geq m execute at least one loop block N^{\prime}\in N by consecutively skipping over both its children, contradicting the definition of \mathcal{S}(N^{\prime}) . 4.2 Transforming Alignments to Skip Alignments Lemma 9 (Transformation to Skip Alignments) Let \sigma be a trace and N an SBWF-net. Let \gamma be an alignment for \sigma on N and let \gamma^{\prime} be the mix alignment obtained by replacing all model moves in \gamma with skip moves. Then, the exhaustive application of transformation rules to \gamma^{\prime} results in a skip alignment \delta for \sigma on N . Proof Every move in \delta is a log, synchronous, or skip move. It holds that \pi_{1}(\delta)_{\downharpoonright_{\neq\gg}}=\pi_{1}(\gamma)_{\downharpoonright_{\neq\gg}}=\sigma since only skip moves are modified in the transformation. Furthermore, because \gamma is an alignment on N , \pi_{2}(\gamma)_{\downharpoonright_{\neq\gg}} and \pi_{2}(\gamma^{\prime})_{\downharpoonright_{\neq\gg}} are executions of N . Cycling rules trivially maintain that property. Lifting rules replace moves in \gamma^{\prime} only at the positions their children where executed at, i.e., the application of any rule ensures that \pi_{2}(\delta)_{\downharpoonright_{\neq\gg}} is an execution of N . In \delta , every skip move is maximally general, otherwise one of (L1-L4) could be applied and \delta contains no cycles, otherwise (C1-C2) could be applied. Hence, \pi_{2}(\delta)_{\downharpoonright_{\neq\gg}}\in\mathcal{S}(N) and \delta is a skip alignment for \sigma on N . 4.4 A Canonical Normal Form for Skip Alignments We show that reduction rules may be applied in any order resulting in the same unique skip alignment ( canonicity ). To that end, we first prove termination and then local confluency , i.e., when applying two rules yields two different skip alignments, then there are subsequent reduction rules to make them equal again. Proposition 1 (Termination of Reduction Rules) Let \delta be a skip alignment. Repeated application of the reduction rules to \delta is terminating. Proof We give a weighting function that monotonically decreases with every application of a rule. With every application of (R1) or (R2), the size of the set of pairs t_{1}=\{(i,j)\mid 1\leq i<j\leq|\delta|\land\delta_{i}=\big(\begin{smallmatrix}\gg\\ a\end{smallmatrix}\big)\land\delta_{j}\in\{\big(\begin{smallmatrix}e\\ \gg\end{smallmatrix}\big),\big(\begin{smallmatrix}e\\ a\end{smallmatrix}\big)\}\} decreases. None of (R1-R3) increases the size of this set again. With every application of (R3), the size of the set of pairs t_{2}=\{(i,j)\mid 1\leq i<j\leq|\delta|\land\delta_{i}=\big(\begin{smallmatrix}\gg\\ s(N_{1})\end{smallmatrix}\big)\land\delta_{j}=\big(\begin{smallmatrix}\gg\\ s(N_{2})\end{smallmatrix}\big)\land N_{2}<N_{1}\} decreases. Only the application of (R2) may increase t_{2} by at most |\delta| elements. Hence, (|\delta|\!+\!1)\cdot|t_{1}|+|t_{2}| is monotonically decreasing with every rule application. We prove local confluency for every pair of rules where the left sides overlap. We show that after applying one of the rules the resulting skip alignment can be made equal to the one after applying the other rule. Proposition 2 (Local Confluency of Reduction Rules) The reduction rules are locally confluent. Proof We only inspect moves where there can be overlapping rules, i.e., (R2,R3) and (R2,R2). Let \delta=\langle\hbox to11.78pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 15.75 0}{fill:none} \lx@inpgf@ignorespaces } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}{}\big(\begin{smallmatrix}\gg\\ s(N_{1})\end{smallmatrix}\big)\hbox to11.78pt{\vbox to3.25pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.62263pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0.95 1.97 L 2.86 -1.97 L 4.77 1.97 L 6.68 -1.97 L 8.59 1.97 L 9.55 0 L 15.75 0}{fill:none} \lx@inpgf@ignorespaces } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\allowbreak\big(\begin{smallmatrix}\gg\\ s(N_{2})\end{smallmatrix}\big),\big(\begin{smallmatrix}\gg\\ s(N_{3})\end{smallmatrix}\big)\hbox to11.78pt{\vbox to3.25pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.62263pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0.95 1.97 L 2.86 -1.97 L 4.77 1.97 L 6.68 -1.97 L 8.59 1.97 L 9.55 0 L 15.75 0}{fill:none} \lx@inpgf@ignorespaces } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\big(\begin{smallmatrix}e\\ a\end{smallmatrix}\big)\hbox to11.78pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 15.75 0}{fill:none} \lx@inpgf@ignorespaces } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}{}\rangle . We show that independent of the order in which we apply (R2,R3) to \langle\big(\begin{smallmatrix}\gg\\ s(N_{2})\end{smallmatrix}\big),\big(\begin{smallmatrix}\gg\\ s(N_{3})\end{smallmatrix}\big)\rangle or (R2,R2) to \langle\big(\begin{smallmatrix}\gg\\ s(N_{1})\end{smallmatrix}\big)\hbox to11.78pt{\vbox to3.25pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.62263pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0.95 1.97 L 2.86 -1.97 L 4.77 1.97 L 6.68 -1.97 L 8.59 1.97 L 9.55 0 L 15.75 0}{fill:none} \lx@inpgf@ignorespaces } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\big(\begin{smallmatrix}\gg\\ s(N_{2})\end{smallmatrix}\big)\rangle , the resulting skip alignments can be made equal again. • First applying (R2) pushing \big(\begin{smallmatrix}\gg\\ s(N_{3})\end{smallmatrix}\big) over \big(\begin{smallmatrix}e\\ a\end{smallmatrix}\big) is equal to swapping \big(\begin{smallmatrix}\gg\\ s(N_{2})\end{smallmatrix}\big) with \big(\begin{smallmatrix}\gg\\ s(N_{3})\end{smallmatrix}\big) by (R3) and shifting back \big(\begin{smallmatrix}\gg\\ s(N_{3})\end{smallmatrix}\big) afterwards with (R2). • First applying (R2) to \big(\begin{smallmatrix}\gg\\ s(N_{2})\end{smallmatrix}\big) pushing the move after \big(\begin{smallmatrix}e\\ a\end{smallmatrix}\big) and then applying (R2) to \big(\begin{smallmatrix}\gg\\ s(N_{1})\end{smallmatrix}\big) is equal to applying (R2) first to \big(\begin{smallmatrix}\gg\\ s(N_{1})\end{smallmatrix}\big) and then to \big(\begin{smallmatrix}\gg\\ s(N_{2})\end{smallmatrix}\big) , followed by an additional application of (R3) to the order \langle\big(\begin{smallmatrix}e\\ a\end{smallmatrix}\big),\big(\begin{smallmatrix}\gg\\ s(N_{1})\end{smallmatrix}\big),\allowbreak\big(\begin{smallmatrix}\gg\\ s(N_{2})\end{smallmatrix}\big)\rangle of the first (R2,R2) if the constraint [N_{2}<N_{1}] holds, otherwise we apply (R3) to the result \langle\big(\begin{smallmatrix}e\\ a\end{smallmatrix}\big),\big(\begin{smallmatrix}\gg\\ s(N_{2})\end{smallmatrix}\big),\big(\begin{smallmatrix}\gg\\ s(N_{1})\end{smallmatrix}\big)\rangle of the second (R2,R2). Canonicity follows from both propositions together with Newman’s Lemma [ 1 ] . Lemma 13 (Unique Coinciding Normal Form) Every alignment coincides with a single skip alignment in normal form. Proof We show that for an alignment \gamma the set of corresponding skip alignments \mathcal{C}(\gamma) coincides with a single normal form. Let \delta and \hat{\delta} in \mathcal{C}(\gamma) be corresponding skip alignments of \gamma . With canonicity, they reduce to coinciding normal forms \delta^{\prime} and \hat{\delta}^{\prime} . Assume \delta^{\prime}\neq\hat{\delta}^{\prime} . Both normal forms share the same moves, so their order must be different. At the position i of their first difference, one of \delta^{\prime} and \hat{\delta}^{\prime} has to perform a skip move. W.l.o.g., we assume \delta^{\prime}_{i}=\big(\begin{smallmatrix}\gg\\ s(N_{1})\end{smallmatrix}\big) . • If \hat{\delta}^{\prime}_{i}=\big(\begin{smallmatrix}e\\ \gg\end{smallmatrix}\big) performs a log move, then this move appears at a position \delta^{\prime}_{j} with j>i . Because no synchronous move can take place in between positions i and j in \delta^{\prime} , (R1) can be applied contradicting the normal form. • If \hat{\delta}^{\prime}_{i}=\big(\begin{smallmatrix}e\\ a\end{smallmatrix}\big) performs a synchronous move, then the skip move \delta^{\prime}_{i} is not required before performing the synchronous move in \hat{\delta}^{\prime} , so (R2) can be applied to \delta^{\prime} contradicting the normal form. • If \hat{\delta}^{\prime}_{i}=\big(\begin{smallmatrix}\gg\\ s(N_{2})\end{smallmatrix}\big) performs a skip move, then this move is performed at a position j>i in \delta^{\prime} . If there is a synchronous move in \delta^{\prime} in between i and j , then \big(\begin{smallmatrix}\gg\\ s(N_{2})\end{smallmatrix}\big) is independent from the synchronous move, i.e., (R2) can be applied to \hat{\delta}^{\prime} contradicting the

Read the complete text