Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A*

# Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements 𝐴^∗
Source: [https://arxiv.org/html/2605.26938](https://arxiv.org/html/2605.26938)
###### Abstract

Alignment\-based conformance checking is the state\-of\-the\-art approach for comparing observed process executions with normative process models\. The standard exact solution relies on anA∗A^\{\*\}\-based heuristic search, which can exhibit exponential runtime in the presence of long traces or substantial deviations\. This paper introduces a reformulation of alignment\-based conformance checking as a totally unimodular linear program \(LP\) defined on the reachability graph of the synchronous product\. By exploiting the underlying network\-flow structure, the proposed formulation guarantees the existence of an integral optimal extreme\-point solution through LP relaxation, thereby avoiding the combinatorial overhead associated with integer variables and branch\-and\-bound search\.

We conduct an extensive empirical evaluation on more than 2\.1 million conformance checking instances derived from real\-world and synthetic benchmark datasets\. The results show thatA∗A^\{\*\}and the LP approach exhibit complementary performance characteristics: the former performs best on short, well\-conforming traces, while the LP formulation provides substantial speedups for longer traces with deviations, precisely where conformance checking is most informative\. Based on these findings, we derive simple algorithm\-selection guidelines that combine both approaches, achieving average runtime savings of 38\.6% with 96% selection accuracy compared to always usingA∗A^\{\*\}\.

###### keywords:

process mining , alignment\-based conformance checking , linear programming , total unimodularity

\\affiliation

\[biu\] organization=Faculty of Engineering, Bar\-Ilan University, city=Ramat Gan, country=Israel

Author\-accepted manuscript\.Accepted for publication in*Expert Systems with Applications*\. This version is available under CC BY\-NC\-ND 4\.0\. Please cite the published article\.

## 1Introduction

Conformance checking is a fundamental task in process mining that quantifies how well observed process executions align with a normative process model\. Among the available techniques, alignment\-based conformance checking has become the standard due to its semantic rigor and diagnostic power, as it computes an optimal correspondence between an observed trace and a process model\. Computing such optimal alignments, however, is computationally demanding, and practical solutions typically rely on heuristic search algorithms such asA∗A^\{\*\}or on mixed\-integer linear programming \(MILP\) formulations\.

A central question in this domain is whether exact conformance checking necessarily requires specialized search algorithms and custom implementations, or whether it can be expressed using standard off\-the\-shelf optimization paradigms that benefit from decades of advances in operations research\. While approaches such asA∗A^\{\*\}can be highly effective in favorable cases, they require careful heuristic design, custom implementations, and may exhibit exponential behavior on long or highly deviating traces\. In contrast, problems that admit a formulation within established optimization frameworks can leverage mature solver technology, allowing direct use of off\-the\-shelf solvers without custom implementation effort, provided that their underlying structure supportsefficientexact solution methods\.

This paper shows that alignment\-based conformance checking admits such a formulation\. We present a reformulation of the problem as a linear program defined on the reachability graph of the synchronous product, whose constraint matrix is totally unimodular\. We refer to this formulation as the Unimodular Reformulation for Conformance Checking \(URC2\)\. The key theoretical insight is that the resulting problem corresponds to a minimum\-cost network flow with integral right\-hand sides, which guarantees that every extreme point of the LP feasible region is integral\. In other words, whenever an optimum exists, the LP admits an integral optimal solution\. As a consequence, optimal alignments can be computed using standard LP solvers, without integer variables or branch\-and\-bound search\.

Importantly, this result does not eliminate the inherent state\-space complexity of conformance checking: the reachability graph of the synchronous product may still grow exponentially in the worst case\. Rather, URC2removes combinatorial optimization from within the explored state space by replacing heuristic or integer search with a single linear optimization problem\. In this sense, URC2shifts the computational burden from search control to linear optimization over an explicitly constructed portion of the state space, while relying on solver efficiency rather than heuristic exploration\.

In practice, the current URC2implementation constructs an explicitly bounded subgraph of the reachability graph of the synchronous product by breadth\-first exploration up to a practical depth limit\. This bound is used to control graph construction cost and avoid unbounded expansion in the presence of cycles or concurrency\. The LP is then solved exactly on the constructed subgraph\.

Rather than proposing URC2as a universal replacement for existing methods, we position it as a complement toA∗A^\{\*\}\. Through an extensive empirical study comprising more than 2\.1 million conformance\-checking instances across five real\-world and synthetic benchmark datasets, we show that neither approach dominates\.A∗A^\{\*\}performs best on short, well\-conforming traces, where heuristic guidance keeps the explored state space small\. In contrast, URC2provides substantial performance gains on longer traces with deviations, precisely where heuristic search tends to degrade\. This distinction is practically relevant since conformance checking is most informative in scenarios where deviations are expected, while perfectly conforming executions require little analysis\.

Based on these observations, we identify the conditions under which each approach is preferable and derive a simple algorithm\-selection rule that combines both methods\. This hybrid strategy yields 38\.6% runtime savings compared to consistently applyingA∗A^\{\*\}alone, while preserving optimality\.

The main contributions of this paper are:

1. 1\.A totally unimodular LP formulation\.We reformulate alignment\-based conformance checking as a minimum\-cost network flow problem on the reachability graph of the synchronous product and show that its constraint matrix is totally unimodular\. This guarantees the existence of an integral optimal extreme\-point solution via linear programming, enabling exact alignment computation without integer variables\.
2. 2\.Large\-scale empirical evaluation\.We conduct an extensive experimental study comparing URC2andA∗A^\{\*\}across more than 2\.1 million instances from real\-world and synthetic datasets, analyzing performance across trace lengths, model characteristics, and deviation levels\.
3. 3\.Practical algorithm\-selection guidelines\.We identify the key factors governing the relative performance ofA∗A^\{\*\}and URC2, and provide a simple, actionable selection rule that achieves 96% selection accuracy\. The results demonstrate that the two approaches are complementary: URC2achieves substantial speedups on long, non\-conforming traces, whileA∗A^\{\*\}remains preferable for short, well\-conforming ones\.

The remainder of this paper is structured as follows\. Section[2](https://arxiv.org/html/2605.26938#S2)reviews related work\. Section[3](https://arxiv.org/html/2605.26938#S3)introduces the required concepts and notation\. Section[4](https://arxiv.org/html/2605.26938#S4)presents the URC2formulation and establishes its total unimodularity, followed by an illustrative example in Section[5](https://arxiv.org/html/2605.26938#S5)\. Section[6](https://arxiv.org/html/2605.26938#S6)describes the experimental design, and Section[7](https://arxiv.org/html/2605.26938#S7)reports the empirical results\. Based on these findings, Section[8](https://arxiv.org/html/2605.26938#S8)provides practical guidelines for choosing betweenA∗A^\{\*\}and URC2\. Section[9](https://arxiv.org/html/2605.26938#S9)discusses limitations and future research directions, and Section[10](https://arxiv.org/html/2605.26938#S10)concludes the paper\.

## 2Related Work

Since its formalization, conformance checking has been studied through exact, approximate, decomposition\-based, and symbolic approaches\. This section reviews the most relevant research streams and positions the proposed unimodular LP formulation within this body of work\.

### 2\.1Exact Alignment\-Based Conformance Checking

The notion of alignments was introduced byAdriansyahet al\.\([2011](https://arxiv.org/html/2605.26938#bib.bib1)\)and later formalized inAdriansyah \([2014](https://arxiv.org/html/2605.26938#bib.bib2)\), where optimal alignments between traces and Petri net models are computed usingA∗A^\{\*\}search on the synchronous product\. This formulation has become the standard approach for exact conformance checking and is supported by mature implementations in process mining frameworks such asProMandPM4Py\. The approach relies on heuristic functions derived from the marking equation of the underlying Petri net\. Subsequent work byvan Dongen \([2018](https://arxiv.org/html/2605.26938#bib.bib36)\)introduced an extended marking equation with tighter bounds, reducing the number of linear programs solved during search, particularly for traces with swapped activities\.Li and van Zelst \([2022](https://arxiv.org/html/2605.26938#bib.bib19)\)extended this with a caching strategy for split\-point\-based alignment calculation that improves overall search efficiency\. More recently,Casas\-Ramoset al\.\([2024](https://arxiv.org/html/2605.26938#bib.bib12)\)proposed REACH, which reduces both the number of explored states and the processing time per state through mandatory\-move forcing and partial reachability graph caching of the process model\. Despite these improvements,A∗A^\{\*\}\-based methods preserve the fundamental architecture of best\-first search and may exhibit exponential complexity in the branching factor and alignment length, which can make them impractical for traces with many deviations or models with high concurrency\.

In parallel, mathematical programming approaches have been explored for conformance checking\.De Leoni and Van Der Aalst \([2013](https://arxiv.org/html/2605.26938#bib.bib15)\)proposed a multi\-perspective approach based on mixed\-integer linear programming \(MILP\) to incorporate control\-flow, data, resources, and time\. More recently,Schwanenet al\.\([2024](https://arxiv.org/html/2605.26938#bib.bib24)\)formulated the alignment problem for block\-structured process trees as a MILP, showing that the problem lies in𝖭𝖯\\mathsf\{NP\}for this restricted model class\. Their formulation requires integer variables to encode parallelism and reduces to a polynomial\-time linear program only when parallel operators are absent\.

Our approach differs in scope and mechanism\. Rather than restricting the model class, URC2supports general workflow Petri nets and formulates alignment computation as a minimum\-cost network flow problem defined on the reachability graph of the synchronous product\. The key insight is that the resulting constraint matrix is totally unimodular, which guarantees the existence of an integral optimal extreme\-point solution through linear programming alone, without introducing integer variables, independently of the degree of concurrency\. Consequently, the resulting formulation admits polynomial\-time solvability in the size of the reachability graph\.

### 2\.2Approximate and Heuristic Methods

Approximation and heuristic techniques trade accuracy for scalability\.Schusteret al\.\([2020](https://arxiv.org/html/2605.26938#bib.bib27)\)proposed alignment approximation for process trees by exploiting their hierarchical structure\. Sampling\-based methods\(Baueret al\.,[2019](https://arxiv.org/html/2605.26938#bib.bib4); Fani Saniet al\.,[2020](https://arxiv.org/html/2605.26938#bib.bib17)\)provide statistical guarantees on aggregate conformance measures but sacrifice trace\-level diagnostics\. Heuristic approaches, including evolutionary algorithms\(Buijs,[2014](https://arxiv.org/html/2605.26938#bib.bib10); Taymouri and Carmona,[2018](https://arxiv.org/html/2605.26938#bib.bib30)\), achieve scalability at the cost of optimality guarantees\. Data\-structure optimizations such as trie\-based caching\(Awadet al\.,[2021](https://arxiv.org/html/2605.26938#bib.bib3)\)and tandem\-repeat compression\(Reißneret al\.,[2020](https://arxiv.org/html/2605.26938#bib.bib22)\)reduce redundant computation but depend on trace similarity or repetitive patterns\.

### 2\.3Decomposition Strategies

Model\-based decomposition partitions process models into fragments that are aligned independently\(Munoz\-Gamaet al\.,[2014](https://arxiv.org/html/2605.26938#bib.bib21); Taymouri and Carmona,[2016](https://arxiv.org/html/2605.26938#bib.bib31); Chenget al\.,[2023](https://arxiv.org/html/2605.26938#bib.bib13)\)\. Log\-based decomposition partitions event logs horizontally or vertically for distributed processing\(Valencia\-Parraet al\.,[2021](https://arxiv.org/html/2605.26938#bib.bib34); Bogdanovet al\.,[2024](https://arxiv.org/html/2605.26938#bib.bib8)\)\. These approaches trade global optimality for tractability and may introduce recomposition overhead\.

### 2\.4Symbolic Encodings

Symbolic techniques compact the state space using decision diagrams\(Bloemenet al\.,[2018](https://arxiv.org/html/2605.26938#bib.bib7)\)or SAT/MaxSAT formulations\(Boltenhagenet al\.,[2021](https://arxiv.org/html/2605.26938#bib.bib9)\)\. While effective for pruning, they may incur high memory consumption on complex models\.

### 2\.5Positioning

The unimodular LP formulation URC2occupies a distinct position within alignment\-based conformance checking research\. Unlike decomposition or approximation approaches, URC2finds optimal alignments\. UnlikeA∗A^\{\*\}\-based methods, which may exhibit exponential behavior on nonconforming traces, the LP formulation has polynomial complexity in the size of the constructed reachability graph\. By exploiting the structural properties of the constraint matrix, URC2avoids the combinatorial complexity of MILP formulations and enables direct use of standard off\-the\-shelf LP solvers, without branch\-and\-bound or cutting\-plane procedures\.

At the same time, URC2preserves the diagnostic power of alignment\-based conformance checking, in contrast to token\-based or sampling approaches\. Its main computational overhead lies in constructing a bounded portion of the reachability graph on which the LP is solved\. Our empirical results reveal complementary performance behavior:A∗A^\{\*\}excels on short, well\-conforming traces, whereas URC2provides substantial advantages on longer traces with deviations\. This complementarity has practical implications, as conformance checking is most informative precisely when deviations occur, and motivates algorithm\-selection guidelines that exploit the strengths of both approaches\.

## 3Concepts and Notation

This section introduces concepts required for developing URC2, starting with defining process and trace models, used for representing expected and observed process behaviors, respectively\. Throughout this section, we use standard process mining definitions and notation\(see e\.g\., Van Der Aalst,[2016](https://arxiv.org/html/2605.26938#bib.bib39)\), with some adaptations\. Next, we explain how to merge a process model and a trace as a synchronous product followed by defining a cost function and key alignment concepts\.

###### Definition 1\(Labeled Marked Petri Net\)\.

A labeled marked Petri net is a tuple

N=\(P,T,F,λ,mi,mf\),N=\(P,T,F,\\lambda,m\_\{i\},m\_\{f\}\),where:

PP:finite set of places,

TT:finite set of transitions withP∩T=∅P\\cap T=\\emptyset,

FF:set of directed arcs \(flow relations\), withF⊆\(P×T\)∪\(T×P\)F\\subseteq\(P\\times T\)\\cup\(T\\times P\),

λ\\lambda:labeling functionλ:T→A∪\{τ\}\\lambda:T\\to A\\cup\\\{\\tau\\\}assigning each transition either an activity label or the silent labelτ∉A\\tau\\notin A, whereAAis the set of activities,

mim\_\{i\}:initial marking \(initial token distribution\),

mfm\_\{f\}:final marking \(completion token distribution\)\.

We use the above definition to represent a process model, where places correspond to conditions or states, and transitions to events or activities\. The set of flow relationsFFdefines how tokens can move between places and transitions\. The labeling functionλ\\lambdamaps each transition to an activity; the special labelτ\\tauindicates a silent \(unobservable or internal\) transition\.

![Refer to caption](https://arxiv.org/html/2605.26938v1/toy_acyclic.png)\(a\)Acyclic process model
![Refer to caption](https://arxiv.org/html/2605.26938v1/toy_cyclic.png)\(b\)Cyclic process model

Figure 1:Two Petri nets, without and with a loop\.![Refer to caption](https://arxiv.org/html/2605.26938v1/trace_toy_1.png)\(a\)
![Refer to caption](https://arxiv.org/html/2605.26938v1/trace_toy_2.png)\(b\)
![Refer to caption](https://arxiv.org/html/2605.26938v1/trace_toy_3.png)\(c\)

Figure 2:Three models for traces \(a\)⟨a​b​c​d​e⟩\\langle abcde\\rangle\(b\)⟨a​b​e⟩\\langle abe\\rangle\(c\)⟨a​c​b​d​b​e⟩\\langle acbdbe\\rangle\.Figure[1](https://arxiv.org/html/2605.26938#S3.F1)presents two process models\. The one in Figure[1\(a\)](https://arxiv.org/html/2605.26938#S3.F1.sf1)does not include loops and the other, in Figure[1\(b\)](https://arxiv.org/html/2605.26938#S3.F1.sf2), does\. Mathematically, for both processesP=\{p1,p2,…,p6\}P=\\\{p\_\{1\},p\_\{2\},\\dots,p\_\{6\}\\\},T=\{t1,t2,…,t5\}T=\\\{t\_\{1\},t\_\{2\},\\dots,t\_\{5\}\\\},mi=\[1,0,0,0,0,0\]m\_\{i\}=\[1,0,0,0,0,0\],mf=\[0,0,0,0,0,1\]m\_\{f\}=\[0,0,0,0,0,1\],A=\{a,b,c,d,e\}A=\\\{a,b,c,d,e\\\}andλ​\(t1\)=a,λ​\(t2\)=b,λ​\(t3\)=c,λ​\(t4\)=d,λ​\(t5\)=e\\lambda\(t\_\{1\}\)=a,\\lambda\(t\_\{2\}\)=b,\\lambda\(t\_\{3\}\)=c,\\lambda\(t\_\{4\}\)=d,\\lambda\(t\_\{5\}\)=e\. The sets of flows are different:

F[1\(a\)](https://arxiv.org/html/2605.26938#S3.F1.sf1)=\{\(p1,t1\),\(t1,p2\),\(t1,p3\),\(p2,t2\),\(p2,t4\),\(p3,t3\),\(p3,t4\),\(t2,p4\),\(t3,p5\),\(t4,p4\),\(t4,p5\),\(p4,t5\),\(p5,t5\),\(t5,p6\)\},andF\_\{\\ref\{fig\_acyclic\}\}=\\left\\\{\\begin\{aligned\} &\(p\_\{1\},t\_\{1\}\),\(t\_\{1\},p\_\{2\}\),\(t\_\{1\},p\_\{3\}\),\(p\_\{2\},t\_\{2\}\),\\\\ &\(p\_\{2\},t\_\{4\}\),\(p\_\{3\},t\_\{3\}\),\(p\_\{3\},t\_\{4\}\),\(t\_\{2\},p\_\{4\}\),\\\\ &\(t\_\{3\},p\_\{5\}\),\(t\_\{4\},p\_\{4\}\),\(t\_\{4\},p\_\{5\}\),\(p\_\{4\},t\_\{5\}\),\\\\ &\(p\_\{5\},t\_\{5\}\),\(t\_\{5\},p\_\{6\}\)\\end\{aligned\}\\right\\\},\\text\{and\}F[1\(b\)](https://arxiv.org/html/2605.26938#S3.F1.sf2)=\{\(p1,t1\),\(t1,p2\),\(t1,p3\),\(p2,t2\),\(t4,p2\),\(p3,t3\),\(t4,p3\),\(t2,p4\),\(t3,p5\),\(p4,t4\),\(p5,t4\),\(p4,t5\),\(p5,t5\),\(t5,p6\)\}​\.F\_\{\\ref\{fig\_cyclic\}\}=\\left\\\{\\begin\{aligned\} &\(p\_\{1\},t\_\{1\}\),\(t\_\{1\},p\_\{2\}\),\(t\_\{1\},p\_\{3\}\),\(p\_\{2\},t\_\{2\}\),\\\\ &\(t\_\{4\},p\_\{2\}\),\(p\_\{3\},t\_\{3\}\),\(t\_\{4\},p\_\{3\}\),\(t\_\{2\},p\_\{4\}\),\\\\ &\(t\_\{3\},p\_\{5\}\),\(p\_\{4\},t\_\{4\}\),\(p\_\{5\},t\_\{4\}\),\(p\_\{4\},t\_\{5\}\),\\\\ &\(p\_\{5\},t\_\{5\}\),\(t\_\{5\},p\_\{6\}\)\\end\{aligned\}\\right\\\}\\text\{\.\}
Table[1](https://arxiv.org/html/2605.26938#S3.T1)presents the models’incidence matrices, where rows correspond to places and columns to transitions\. Each entryIi​jI\_\{ij\}indicates the net change in tokens at placepip\_\{i\}when transitiontjt\_\{j\}fires with−1\-1denoting token consumption,\+1\+1token production, and0indicating no effect\. For example,I11=−1I\_\{11\}=\-1corresponds to a token flowing fromp1p\_\{1\}and consumed int1t\_\{1\}, interpreted as flow\(p1,t1\)\(p\_\{1\},t\_\{1\}\)\.I21=1I\_\{21\}=1represents a token produced byt1t\_\{1\}and moving intop2p\_\{2\}, related to flow\(t1,p2\)\(t\_\{1\},p\_\{2\}\)\.

Table 1:Incidence matrices for the process models in Figure[1](https://arxiv.org/html/2605.26938#S3.F1)\.\([1\(a\)](https://arxiv.org/html/2605.26938#S3.F1.sf1)\) Acyclict1t\_\{1\}t2t\_\{2\}t3t\_\{3\}t4t\_\{4\}t5t\_\{5\}p1p\_\{1\}−1\-10000p2p\_\{2\}1−1\-10−1\-10p3p\_\{3\}10−1\-1−1\-10p4p\_\{4\}0101−1\-1p5p\_\{5\}0011−1\-1p6p\_\{6\}00001
\([1\(b\)](https://arxiv.org/html/2605.26938#S3.F1.sf2)\) Cyclict1t\_\{1\}t2t\_\{2\}t3t\_\{3\}t4t\_\{4\}t5t\_\{5\}p1p\_\{1\}−1\-10000p2p\_\{2\}1−1\-1010p3p\_\{3\}10−1\-110p4p\_\{4\}010−1\-1−1\-1p5p\_\{5\}001−1\-1−1\-1p6p\_\{6\}00001

###### Definition 2\(Trace Model\)\.

LetAAbe a finite set of activities\. LetA′A^\{\\prime\}denote the set of all finite sequences overAA, representing possibly completed traces\. Assume thatσ∈A′\\sigma\\in A^\{\\prime\}is a trace of lengthnn, then its corresponding trace model is defined as the Petri net

T​N=\(P,T,F,λ,mi,mf\),TN=\(P,T,F,\\lambda,m\_\{i\},m\_\{f\}\),whereP=\{p0,p1,…,pn\}P=\\\{p\_\{0\},p\_\{1\},\\dots,p\_\{n\}\\\}is the set of places,T=\{t1,t2,…,tn\}T=\\\{t\_\{1\},t\_\{2\},\\dots,t\_\{n\}\\\}is the set of transitions, and

F=\{\(pi,ti\+1\)∣0≤i<n\}∪\{\(ti,pi\)∣1≤i≤n\}F=\\\{\(p\_\{i\},t\_\{i\+1\}\)\\mid 0\\leq i<n\\\}\\;\\cup\\;\\\{\(t\_\{i\},p\_\{i\}\)\\mid 1\\leq i\\leq n\\\}is the set of flow relations\. The initial and final markings are given bymi=\[p0\]m\_\{i\}=\[p\_\{0\}\]andmf=\[pn\]m\_\{f\}=\[p\_\{n\}\], respectively\. The labeling functionλ:T→A\\lambda:T\\to Aassigns each transition its corresponding activity label, i\.e\.,λ​\(ti\)=σ​\(i\)\\lambda\(t\_\{i\}\)=\\sigma\(i\)for1≤i≤n1\\leq i\\leq n\.

A trace model represents the sequence of events observed during an execution, with its structure derived directly from the traceσ\\sigma\. Each transition corresponds to an event, while the initial and final markings define the start and end of the execution\. This structure enables direct comparison with the expected process behavior when integrated into a synchronous product\. Figure[2](https://arxiv.org/html/2605.26938#S3.F2)illustrates this by presenting three traces, \(a\)⟨a​b​c​d​e⟩\\langle abcde\\rangle\(b\)⟨a​b​e⟩\\langle abe\\rangle\(c\)⟨a​c​b​d​b​e⟩\\langle acbdbe\\rangle, as trace models\.

###### Definition 3\(Synchronous Product\)\.

Consider a process model

S​N=\(PS​N,TS​N,FS​N,λS​N,miS​N,mfS​N\),SN=\(P^\{SN\},T^\{SN\},F^\{SN\},\\lambda^\{SN\},m\_\{i\}^\{SN\},m\_\{f\}^\{SN\}\),and a trace model

T​N=\(PT​N,TT​N,FT​N,λT​N,miT​N,mfT​N\)TN=\(P^\{TN\},T^\{TN\},F^\{TN\},\\lambda^\{TN\},m\_\{i\}^\{TN\},m\_\{f\}^\{TN\}\)for an observed traceσ\\sigma\. The synchronous product is defined as

S​P=\(P,T,F,λ,mi,mf\),SP=\(P,T,F,\\lambda,m\_\{i\},m\_\{f\}\),where

PP:P=PS​N∪PT​NP=P^\{SN\}\\cup P^\{TN\}\.

TT:The transition set is partitioned as

T=TM​M∪TL​M∪TS​M,T=T^\{MM\}\\cup T^\{LM\}\\cup T^\{SM\},where

TM​M\\displaystyle T^\{MM\}=\{\(t,≫\)∣t∈TS​N\},\\displaystyle=\\\{\(t,\\gg\)\\mid t\\in T^\{SN\}\\\},TL​M\\displaystyle T^\{LM\}=\{\(≫,t\)∣t∈TT​N\},\\displaystyle=\\\{\(\\gg,t\)\\mid t\\in T^\{TN\}\\\},TS​M\\displaystyle T^\{SM\}=\{\(t1,t2\)∈TS​N×TT​N∣λS​N​\(t1\)=λT​N​\(t2\)\}\.\\displaystyle=\\\{\(t\_\{1\},t\_\{2\}\)\\in T^\{SN\}\\times T^\{TN\}\\mid\\lambda^\{SN\}\(t\_\{1\}\)=\\lambda^\{TN\}\(t\_\{2\}\)\\\}\.
FF:The flow relation is defined as

F=\\displaystyle F=\{\(p,\(t1,t2\)\)∣\(p,t1\)∈FS​N​or​\(p,t2\)∈FT​N\}\\displaystyle\\\{\(p,\(t\_\{1\},t\_\{2\}\)\)\\mid\(p,t\_\{1\}\)\\in F^\{SN\}\\ \\text\{or\}\\ \(p,t\_\{2\}\)\\in F^\{TN\}\\\}∪\{\(\(t1,t2\),p\)∣\(t1,p\)∈FS​N​or​\(t2,p\)∈FT​N\}\.\\displaystyle\\cup\\\{\(\(t\_\{1\},t\_\{2\}\),p\)\\mid\(t\_\{1\},p\)\\in F^\{SN\}\\ \\text\{or\}\\ \(t\_\{2\},p\)\\in F^\{TN\}\\\}\.
mi,mfm\_\{i\},m\_\{f\}:The initial and final markings are given by

mi=miS​N\+miT​N,mf=mfS​N\+mfT​N\.m\_\{i\}=m\_\{i\}^\{SN\}\+m\_\{i\}^\{TN\},\\qquad m\_\{f\}=m\_\{f\}^\{SN\}\+m\_\{f\}^\{TN\}\.
λ\\lambda:The labeling function is defined by

λ​\(\(t1,t2\)\)=\(ℓ1,ℓ2\),\\lambda\(\(t\_\{1\},t\_\{2\}\)\)=\(\\ell\_\{1\},\\ell\_\{2\}\),where

ℓ1=\{λS​N​\(t1\),if​t1∈TS​N,≫,otherwise,ℓ2=\{λT​N​\(t2\),if​t2∈TT​N,≫,otherwise\.\\ell\_\{1\}=\\begin\{cases\}\\lambda^\{SN\}\(t\_\{1\}\),&\\text\{if \}t\_\{1\}\\in T^\{SN\},\\\\ \\gg,&\\text\{otherwise\},\\end\{cases\}\\qquad\\ell\_\{2\}=\\begin\{cases\}\\lambda^\{TN\}\(t\_\{2\}\),&\\text\{if \}t\_\{2\}\\in T^\{TN\},\\\\ \\gg,&\\text\{otherwise\}\.\\end\{cases\}

The synchronous product is a Petri net that integrates the process and trace models, allowing for a detailed comparison of their behaviors\. By categorizing transitions into synchronous moves \(where the process and trace align\), model moves \(indicating missing trace events\), and log moves \(representing unexpected trace events\), this approach provides a structured foundation for conformance checking\. To quantify deviations, a cost function assigns a numerical penalty to each type of move, capturing its impact on alignment quality\.

###### Definition 4\(Cost Function\)\.

For the synchronous product S​P=\(P,T,F,λ,mi,mf\)SP=\(P,T,F,\\lambda,m\_\{i\},m\_\{f\}\), the*cost function*c:T→ℝ≥0c:T\\to\\mathbb\{R\}\_\{\\geq 0\}assigns a non\-negative cost to each transition as follows:

For every synchronous move\(t1,t2\)∈TS​M\(t\_\{1\},t\_\{2\}\)\\in T^\{SM\}, setc​\(\(t1,t2\)\)=0c\(\(t\_\{1\},t\_\{2\}\)\)=0\.

For a model move\(t,≫\)∈TM​M\(t,\\gg\)\\in T^\{MM\}withλS​N​\(t\)=τ\\lambda^\{SN\}\(t\)=\\tau, setc​\(\(t,≫\)\)=ϵc\(\(t,\\gg\)\)=\\epsilon, whereϵ→0\+\\epsilon\\to 0^\{\+\}\.

For all other moves \(i\.e\., nonsynchronous model or log moves\), assign a cost of 1\.

The cost function measures deviations between modeled and observed behavior, assigning no penalty to synchronous moves while penalizing discrepancies\. It plays a key role in determining the optimal alignment between the trace and the process model\.

###### Definition 5\(Optimal Alignment\)\.

ConsiderAAa set of activities,σ∈A′\\sigma\\in A^\{\\prime\}a trace with a trace modelT​NTN,S​NSNas a process model, andS​PSPas the synchronous product ofS​NSNandT​NTN\. Letc:T→ℝ≥0c:T\\rightarrow\\mathbb\{R\}\_\{\\geq 0\}be a cost function\. Then, an optimal alignmentγo​p​t∈LS​P\\gamma^\{opt\}\\in L\_\{SP\}, whereLS​PL\_\{SP\}is the set of possible execution sequences, is a full execution sequence ofS​PSPsuch that for allγ∈LS​P\\gamma\\in L\_\{SP\},c​\(γo​p​t\)≤c​\(γ\)c\(\\gamma^\{opt\}\)\\leq c\(\\gamma\), wherec​\(γ\)=∑1≤i≤\|γ\|c​\(γ​\(i\)\)c\(\\gamma\)=\\sum\_\{1\\leq i\\leq\|\\gamma\|\}\\,c\(\\gamma\(i\)\)\.

In other words, an optimal alignment is the sequence of moves through the synchronous product that minimizes the total cost, representing the best possible correspondence between the observed trace and the expected process behavior\.

To make these concepts concrete, we illustrate them using the process model in Figure[1\(a\)](https://arxiv.org/html/2605.26938#S3.F1.sf1)and the trace in Figure[2\(b\)](https://arxiv.org/html/2605.26938#S3.F2.sf2)\. Applying Definition[3](https://arxiv.org/html/2605.26938#Thmdefinition3)yields the synchronous product shown in Figure[3](https://arxiv.org/html/2605.26938#S3.F3)\. A standard cost function, by Definition[4](https://arxiv.org/html/2605.26938#Thmdefinition4), assigns a unit cost to each log or model move, and zero cost to synchronous moves\. Consequently, finding an optimal alignment according to Definition[5](https://arxiv.org/html/2605.26938#Thmdefinition5)amounts to transferring the tokens from the initial state of the synchronous product,\[p1,p1′\]\[p\_\{1\},p^\{\\prime\}\_\{1\}\], to its final state,\[p6,p4′\]\[p\_\{6\},p^\{\\prime\}\_\{4\}\], while minimizing the number of non\-synchronous moves\. The two optimal alignments are,

γopt=\{\\displaystyle\\gamma^\{\\mathrm\{opt\}\}=\\\{⟨\(t1,t1′\),\(t2,t2′\),\(t3,≫\),\(t5,t3′\)⟩,\\displaystyle\\langle\(t\_\{1\},t^\{\\prime\}\_\{1\}\),\(t\_\{2\},t^\{\\prime\}\_\{2\}\),\(t\_\{3\},\\gg\),\(t\_\{5\},t^\{\\prime\}\_\{3\}\)\\rangle,⟨\(t1,t1′\),\(t3,≫\),\(t2,t2′\),\(t5,t3′\)⟩\}\.\\displaystyle\\langle\(t\_\{1\},t^\{\\prime\}\_\{1\}\),\(t\_\{3\},\\gg\),\(t\_\{2\},t^\{\\prime\}\_\{2\}\),\(t\_\{5\},t^\{\\prime\}\_\{3\}\)\\rangle\\\}\.\(1\)Each alignment has a conformance cost ofc​\(γopt\)=1c\(\\gamma^\{\\mathrm\{opt\}\}\)=1, reflecting a single model move\.

![Refer to caption](https://arxiv.org/html/2605.26938v1/toy_synchronous.png)Figure 3:A synchronous product of process and trace models\.While the optimal alignment can be identified directly from the synchronous product in small illustrative examples, this task becomes computationally challenging for larger and more complex models\. In practice, the search for an optimal alignment is therefore performed on the reachability graph of the synchronous product, which we define next\.

###### Definition 6\(Reachability Graph of a Synchronous Product\)\.

Let

S​P=\(P,T,F,λ,mi,mf\)SP=\(P,T,F,\\lambda,m\_\{i\},m\_\{f\}\)be the synchronous product from Definition[3](https://arxiv.org/html/2605.26938#Thmdefinition3), and letc:T→ℝ≥0c:T\\to\\mathbb\{R\}\_\{\\geq 0\}be the cost function from Definition[4](https://arxiv.org/html/2605.26938#Thmdefinition4)\. Denote byW−,W\+∈ℤ≥0\|P\|×\|T\|W^\{\-\},W^\{\+\}\\in\\mathbb\{Z\}\_\{\\geq 0\}^\{\|P\|\\times\|T\|\}the*backward*and*forward*incidence matrices, whereW−​\(p,t\)W^\{\-\}\(p,t\)andW\+​\(p,t\)W^\{\+\}\(p,t\)give, respectively, the number of tokens consumed from and produced in placeppby firing transitiontt\. The spaceℤ≥0\|P\|×\|T\|\\mathbb\{Z\}\_\{\\geq 0\}^\{\|P\|\\times\|T\|\}denotes matrices of nonnegative integers of dimension\|P\|×\|T\|\|P\|\\times\|T\|\.

Let the place\-transition incidence matrix be

I=W\+−W−\(denoted​IS​P​when referring to​S​P\),I=W^\{\+\}\-W^\{\-\}\\qquad\(\\text\{denoted \}I\_\{SP\}\\text\{ when referring to \}SP\),whereIS​P​\(⋅,t\)I\_\{SP\}\(\\cdot,t\)denotes the column ofIS​PI\_\{SP\}corresponding to transitiontt\.

The*reachability graph*ofS​PSPis the directed, edge\-labeled graph

RG⁡\(S​P\)=\(V,E,ℓE,w,mi,mf\),\\operatorname\{RG\}\(SP\)=\(V,E,\\ell\_\{E\},w,m\_\{i\},m\_\{f\}\),defined as follows:

V⊆ℤ≥0\|P\|V\\subseteq\\mathbb\{Z\}\_\{\\geq 0\}^\{\|P\|\}is the set of all markings reachable from the initial markingmim\_\{i\}\.

E⊆V×T×VE\\subseteq V\\times T\\times Vcontains an edge\(m,t,m′\)\(m,t,m^\{\\prime\}\)if and only ifttis enabled atmmand its firing yieldsm′m^\{\\prime\}, that is,

∀p∈P:m​\(p\)≥W−​\(p,t\),\\forall p\\in P:\\;m\(p\)\\geq W^\{\-\}\(p,t\),and the successor marking is

m′=m\+IS​P​\(⋅,t\)=m−W−​\(⋅,t\)\+W\+​\(⋅,t\)\.m^\{\\prime\}=m\+I\_\{SP\}\(\\cdot,t\)=m\-W^\{\-\}\(\\cdot,t\)\+W^\{\+\}\(\\cdot,t\)\.
ℓE:E→\(A∪\{τ,≫\}\)×\(A∪\{≫\}\)\\ell\_\{E\}:E\\to\(A\\cup\\\{\\tau,\\gg\\\}\)\\times\(A\\cup\\\{\\gg\\\}\)labels each edge by the transition label ofS​PSP:

ℓE​\(m,t,m′\)=λ​\(t\),\\ell\_\{E\}\(m,t,m^\{\\prime\}\)=\\lambda\(t\),whereλ\\lambdais the labeling function defined in Definition[3](https://arxiv.org/html/2605.26938#Thmdefinition3)\.

Hence:

synchronous moves have labels\(a,a\)\(a,a\)fora∈Aa\\in A,

model moves including silent moves have labels\(a,≫\)\(a,\\gg\)fora∈A∪\{τ\}a\\in A\\cup\\\{\\tau\\\},

log moves have labels\(≫,a\)\(\\gg,a\)fora∈Aa\\in A\.

w:E→ℝ≥0w:E\\to\\mathbb\{R\}\_\{\\geq 0\}assigns edge weights by the move cost:

w​\(m,t,m′\)=c​\(t\)\.w\(m,t,m^\{\\prime\}\)=c\(t\)\.

An alignment is a finite path

π=mi→t1m1→t2⋯→tkmk\\pi=m\_\{i\}\\xrightarrow\{t\_\{1\}\}m\_\{1\}\\xrightarrow\{t\_\{2\}\}\\cdots\\xrightarrow\{t\_\{k\}\}m\_\{k\}inRG⁡\(S​P\)\\operatorname\{RG\}\(SP\), wheremk=mfm\_\{k\}=m\_\{f\}\. It induces the transition sequence γ=⟨t1,…,tk⟩\\gamma=\\langle t\_\{1\},\\dots,t\_\{k\}\\rangleinS​PSPwith total cost

w​\(π\)=∑i=1kw​\(mi−1,ti,mi\)=∑i=1kc​\(ti\)\.w\(\\pi\)=\\sum\_\{i=1\}^\{k\}w\(m\_\{i\-1\},t\_\{i\},m\_\{i\}\)=\\sum\_\{i=1\}^\{k\}c\(t\_\{i\}\)\.An*optimal alignment*corresponds to a minimum\-cost alignment path inRG⁡\(S​P\)\\operatorname\{RG\}\(SP\)\.

The reachability graph of the synchronous product in Figure[3](https://arxiv.org/html/2605.26938#S3.F3), constructed according to Definition[6](https://arxiv.org/html/2605.26938#Thmdefinition6), is shown in Figure[4](https://arxiv.org/html/2605.26938#S3.F4)\. Under the standard cost structure, the minimum\-cost paths from the initial to the final marking correspond to the two optimal alignments shown in Equation \([1](https://arxiv.org/html/2605.26938#S3.E1)\), each with total cost one\.

![Refer to caption](https://arxiv.org/html/2605.26938v1/toy_reachability.png)Figure 4:The complete reachability graph of the synchronous product in Figure[3](https://arxiv.org/html/2605.26938#S3.F3)\. Arcs in blue, green and purple signify log\-, synchronous\-, and model\-moves, respectively\.To motivate our reformulation of the conformance checking problem as a linear program, we begin with a fundamental principle from linear programming theory—the concept of total unimodularity \(TU\), defined below\. Total unimodularity ensures that certain linear programs, when defined over integral right\-hand sides, yield integer optimal solutions without explicitly enforcing binary constraints\(Schrijver,[1998](https://arxiv.org/html/2605.26938#bib.bib25); Bertsimas and Tsitsiklis,[1997](https://arxiv.org/html/2605.26938#bib.bib5)\)\. This property provides the theoretical foundation for our exploration: if the constraint matrix underlying the conformance checking formulation is totally unimodular, then the problem can be solved exactly through a linear relaxation\. In URC2, we leverage this insight as the key motivation for developing an LP\-based reformulation that preserves the optimal alignment structure while avoiding integer constraints\.

###### Definition 7\(Total Unimodularity\)\.

A matrixAAis said to be totally unimodular if every square submatrix ofAAhas a determinant of0,\+1\+1, or−1\-1\. That is, for any square submatrixBBofAA, the determinant satisfies:

det\(B\)∈\{0,±1\}\.\\det\(B\)\\in\\\{0,\\pm 1\\\}\.If the constraint matrix of a linear program \(LP\) is totally unimodular and the right\-hand side vector is integral, then every extreme point of the feasible region is integral, ensuring that the LP relaxation of an integer linear program has an integer optimal solution\.

###### Definition 8\(LP Solution being Optimal for the MILP\)\.

Consider an integer linear program:

min⁡cT​xsubject to​A​x≤b,x≥0,x∈ℤn\.\\min\\;c^\{T\}x\\quad\\text\{subject to \}Ax\\leq b,\\;x\\geq 0,\\;x\\in\\mathbb\{Z\}^\{n\}\.Its linear programming \(LP\) relaxation is obtained by allowingxxto take real values:

min⁡cT​xsubject to​A​x≤b,x≥0,x∈ℝn\.\\min\\;c^\{T\}x\\quad\\text\{subject to \}Ax\\leq b,\\;x\\geq 0,\\;x\\in\\mathbb\{R\}^\{n\}\.
If the feasible region of the LP is an integral polyhedron \(i\.e\., all its vertices are integral\), then every optimal solution of the LP relaxation is also an optimal solution of the MILP\. A sufficient condition for this integrality is that the constraint matrixAAis totally unimodular and the right\-hand side vectorbbis integral\.

## 4Model Development

Multiple previous studies have shown that searching for an optimal alignment usingA∗−A^\{\*\}\-like algorithms with various heuristics, or solving a Mixed\-Integer Linear Programming \(MILP\) formulation of the problem, can be time consuming\. We propose an exact reformulation of the alignment problem as a minimum\-cost flow LP on a network\. Because the node\-arc incidence matrix of this network is totally unimodular and the right‐hand side is integral, the linear programming relaxation is integral\. Therefore, for a given constructed reachability graph, the resulting optimization problem is polynomially solvable in the size of that network\(Tardos,[1986](https://arxiv.org/html/2605.26938#bib.bib29); Schrijver,[2003](https://arxiv.org/html/2605.26938#bib.bib26)\)\.

Having defined the synchronous productS​P=\(P,T,F,λ,mi,mf\)SP=\(P,T,F,\\lambda,m\_\{i\},m\_\{f\}\), its reachability graphRG⁡\(S​P\)\\operatorname\{RG\}\(SP\), and the cost structurec:T→ℝ≥0c:T\\to\\mathbb\{R\}\_\{\\geq 0\}, we now formulate the alignment\-based conformance checking problem as a minimum\-cost network flow problem\. This reformulation preserves the structure of optimal alignments while enabling a totally unimodular \(TU\) linear programming representation that is solvable in polynomial time\.

### 4\.1From Reachability Graph to Network Flow

LetRG⁡\(S​P\)=\(V,E,ℓE,w,mi,mf\)\\operatorname\{RG\}\(SP\)=\(V,E,\\ell\_\{E\},w,m\_\{i\},m\_\{f\}\)denote the reachability graph of the synchronous product \(Definition[6](https://arxiv.org/html/2605.26938#Thmdefinition6)\)\. Each nodev∈Vv\\in Vcorresponds to a reachable marking ofS​PSP, and each directed edgee=\(v,t,v′\)∈Ee=\(v,t,v^\{\\prime\}\)\\in Erepresents the firing of transitiont∈Tt\\in Tfrom markingvvto markingv′=v\+IS​P​\(⋅,t\)v^\{\\prime\}=v\+I\_\{SP\}\(\\cdot,t\)\. The weight functionw:E→ℝ≥0w:E\\to\\mathbb\{R\}\_\{\\geq 0\}assigns the move costw​\(e\)=c​\(t\)w\(e\)=c\(t\)\.

The problem of finding an optimal alignment now becomes that of determining a minimum\-cost path inRG⁡\(S​P\)\\operatorname\{RG\}\(SP\)from the initial to the final marking\.

### 4\.2Decision Variables and Flow Conservation

For every edgee∈Ee\\in E, introduce a continuous decision variable

representing the proportion of*case flow*traversing edgeee\. In integral optimal solutions,xe=1x\_\{e\}=1indicates that the corresponding transition is used in the optimal alignment, andxe=0x\_\{e\}=0otherwise\.

Define the*balance vector*b∈ℤ\|V\|b\\in\\mathbb\{Z\}^\{\|V\|\}by

bv=\{1,v=mi,−1,v=mf,0,otherwise\.b\_\{v\}=\\begin\{cases\}1,&v=m\_\{i\},\\\\\[2\.0pt\] \-1,&v=m\_\{f\},\\\\\[2\.0pt\] 0,&\\text\{otherwise\}\.\\end\{cases\}Flow conservation is then expressed by

∑e∈δ\+​\(v\)xe−∑e∈δ−​\(v\)xe=bv,∀v∈V,\\sum\_\{e\\in\\delta^\{\+\}\(v\)\}x\_\{e\}\-\\sum\_\{e\\in\\delta^\{\-\}\(v\)\}x\_\{e\}=b\_\{v\},\\qquad\\forall v\\in V,\(2\)whereδ\+​\(v\)\\delta^\{\+\}\(v\)andδ−​\(v\)\\delta^\{\-\}\(v\)denote the sets of outgoing and incoming edges at nodevv, respectively\. This enforces one unit \(i\.e\., a single case\) of flow from the initial to the final marking, with zero net flow elsewhere\.

### 4\.3Linear Programming Formulation

The alignment problem can now be written as the following linear program:

minx\\displaystyle\\min\_\{x\}\\quad∑e∈Ew​\(e\)​xe\\displaystyle\\sum\_\{e\\in E\}w\(e\)\\,x\_\{e\}\(3\)s\.t\.∑e∈δ\+​\(v\)xe−∑e∈δ−​\(v\)xe=bv,\\displaystyle\\sum\_\{e\\in\\delta^\{\+\}\(v\)\}x\_\{e\}\-\\sum\_\{e\\in\\delta^\{\-\}\(v\)\}x\_\{e\}=b\_\{v\},∀v∈V,\\displaystyle\\forall v\\in V,\(4\)0≤xe≤1,\\displaystyle 0\\leq x\_\{e\}\\leq 1,∀e∈E\.\\displaystyle\\forall e\\in E\.\(5\)
The objective \([3](https://arxiv.org/html/2605.26938#S4.E3)\) accumulates the total move cost along a chosen path\. Constraints \([4](https://arxiv.org/html/2605.26938#S4.E4)\) and \([5](https://arxiv.org/html/2605.26938#S4.E5)\) ensure conservation of flow and limit the feasible region to unit flow betweenmim\_\{i\}andmfm\_\{f\}\. An optimal basic feasible solution to this LP corresponds to a path inRG⁡\(S​P\)\\operatorname\{RG\}\(SP\)whose total cost equals the minimal conformance deviation\.

### 4\.4Total Unimodularity and Integrality

LetB∈\{−1,0,1\}\|V\|×\|E\|B\\in\\\{\-1,0,1\\\}^\{\|V\|\\times\|E\|\}be the node–arc incidence matrix of thereachability graphRG⁡\(S​P\)\\operatorname\{RG\}\(SP\), whereBv,e=1B\_\{v,e\}=1ife∈δ\+​\(v\)e\\in\\delta^\{\+\}\(v\),Bv,e=−1B\_\{v,e\}=\-1ife∈δ−​\(v\)e\\in\\delta^\{\-\}\(v\), and0otherwise\. Constraints \([4](https://arxiv.org/html/2605.26938#S4.E4)\) can thus be written compactly as

SinceBBis the incidence matrix of a directed network, it is totally unimodular\(Tardos,[1986](https://arxiv.org/html/2605.26938#bib.bib29); Schrijver,[2003](https://arxiv.org/html/2605.26938#bib.bib26)\)\. For completeness, the full incidence matrix of the reachability graph in Figure[4](https://arxiv.org/html/2605.26938#S3.F4), is provided in the supplementary material\.

This follows directly from the fact that each column ofBBcontains exactly one\+1\+1and one−1\-1, with all other entries equal to zero\. Becausebbis integral and the variable bounds in Constraints \([5](https://arxiv.org/html/2605.26938#S4.E5)\) are integral, every basic feasible solution of the LP is integral \(xe∈\{0,1\}x\_\{e\}\\in\\\{0,1\\\}\)\. Therefore, solving the LP yields an optimal integral path without requiring explicit binary constraints\.

### 4\.5Recovering the Optimal Alignment

Let𝒫=\{e1,e2,…,ek\}\\mathcal\{P\}=\\\{e\_\{1\},e\_\{2\},\\dots,e\_\{k\}\\\}denote the set of edges withxei=1x\_\{e\_\{i\}\}=1in the optimal solution\. Traversing𝒫\\mathcal\{P\}reconstructs the optimal firing sequenceγopt=⟨t1,t2,…,tk⟩\\gamma^\{\\mathrm\{opt\}\}=\\langle t\_\{1\},t\_\{2\},\\dots,t\_\{k\}\\rangle, where eachei=\(vi−1,ti,vi\)e\_\{i\}=\(v\_\{i\-1\},t\_\{i\},v\_\{i\}\)\.

Each transition in the synchronous product has two labels, one from the process model side and one from the trace side\. Hence, the labeling function returns a pair:

λ:T→\(A∪\{τ,≫\}\)×\(A∪\{≫\}\),\\lambda:T\\to\(A\\cup\\\{\\tau,\\gg\\\}\)\\times\(A\\cup\\\{\\gg\\\}\),where\(a,a\)\(a,a\)is a synchronous move,\(a,≫\)\(a,\\gg\)fora∈A∪\{τ\}a\\in A\\cup\\\{\\tau\\\}is a model move, and\(≫,a\)\(\\gg,a\)fora∈Aa\\in Ais a log move\. The total alignment cost isc​\(γopt\)=∑ic​\(ti\)c\(\\gamma^\{\\mathrm\{opt\}\}\)=\\sum\_\{i\}c\(t\_\{i\}\), which equals the LP objective value\.

### 4\.6Complexity and Scalability

Since the constraint matrixBBis TU, the problem \([3](https://arxiv.org/html/2605.26938#S4.E3)\)–\([5](https://arxiv.org/html/2605.26938#S4.E5)\) is integral\. Therefore, for a given explicitly constructed reachability graph, the resulting optimization problem is polynomially solvable in the size of that graph and yields exact alignments without introducing integer variables\. This remains valid for synchronous products with loops\.

In practical terms, URC2replaces the traditionalA∗A^\{\*\}or MILP search with a single LP of size\(\|E\|,\|V\|\)\(\|E\|,\|V\|\), whose solution directly yields the optimal alignment and conformance cost\.

Note that this does not contradict the PSPACE\-hardness of reachability, since the reachability graph itself may be exponentially large\.

### 4\.7MILP Formulation on the Synchronous Product

An alternative, straightforward, mathematical programming formulation of the alignment\-based conformance checking problem can be derived directly on the synchronous product, rather than on its \(typically much larger\) reachability graph\. However, as will be shown, the main drawback of this formulation is that its constraint matrix does not, in general, possess the total unimodularity property, thereby requiring the problem to be solved as a computationally hard integer linear program\.

LetS​P=\(P,T,F,λ,mi,mf\)SP=\(P,T,F,\\lambda,m\_\{i\},m\_\{f\}\)be the synchronous product \(Definition[3](https://arxiv.org/html/2605.26938#Thmdefinition3)\)\. Denote byI≡IS​P∈ℤ\|P\|×\|T\|I\\equiv I\_\{SP\}\\in\\mathbb\{Z\}^\{\|P\|\\times\|T\|\}the place–transition incidence matrix ofS​PSP, byc∈ℝ≥0\|T\|c\\in\\mathbb\{R\}\_\{\\geq 0\}^\{\|T\|\}the move\-cost vector \(cf\. Definition[4](https://arxiv.org/html/2605.26938#Thmdefinition4)\), and bymi,mf∈ℤ≥0\|P\|m\_\{i\},m\_\{f\}\\in\\mathbb\{Z\}\_\{\\geq 0\}^\{\|P\|\}the initial and final markings\. Fix an upper boundn∈ℤ\>0n\\in\\mathbb\{Z\}\_\{\>0\}on the alignment length\.

The decision variablesxj,k∈\{0,1\}x\_\{j,k\}\\in\\\{0,1\\\}that equals 1 if transitionj∈Tj\\in Tfires at stepk∈\{1,…,n\}k\\in\\\{1,\\dots,n\\\}, andzk∈\{0,1\}z\_\{k\}\\in\\\{0,1\\\}that equals 1 if the alignment has terminated at or before stepkk\. For convenience, letx⋅,k:=\(x1,k,…,x\|T\|,k\)⊤x\_\{\\cdot,k\}:=\(x\_\{1,k\},\\dots,x\_\{\|T\|,k\}\)^\{\\top\}denote the vector of transition\-decision variables at stepkk\.

Mathematically, we formulate the alignment\-based optimization problem as:

minx,z\\displaystyle\\min\_\{x,z\}\\quad∑k=1n∑j=1\|T\|cj​xj,k\\displaystyle\\sum\_\{k=1\}^\{n\}\\sum\_\{j=1\}^\{\|T\|\}c\_\{j\}\\,x\_\{j,k\}\(6\)s\.t\.mi\+I​\(∑k=1nx⋅,k\)=mf,\\displaystyle m\_\{i\}\+I\\\!\\Big\(\\sum\_\{k=1\}^\{n\}x\_\{\\cdot,k\}\\Big\)=m\_\{f\},\(7\)mi\+I​\(∑τ=1kx⋅,τ\)≥0,∀k=1,…,n,\\displaystyle m\_\{i\}\+I\\\!\\Big\(\\sum\_\{\\tau=1\}^\{k\}x\_\{\\cdot,\\tau\}\\Big\)\\geq 0,\\quad\\forall k=1,\\dots,n,\(8\)∑j=1\|T\|xj,k\+zk=1,∀k=1,…,n,\\displaystyle\\sum\_\{j=1\}^\{\|T\|\}x\_\{j,k\}\+z\_\{k\}=1,\\quad\\forall k=1,\\dots,n,\(9\)zk\+1≥zk,∀k=1,…,n−1,\\displaystyle z\_\{k\+1\}\\geq z\_\{k\},\\quad\\forall k=1,\\dots,n\-1,\(10\)xj,k∈\{0,1\},zk∈\{0,1\}\.\\displaystyle x\_\{j,k\}\\in\\\{0,1\\\},\\;z\_\{k\}\\in\\\{0,1\\\}\.\(11\)
The objective, \([6](https://arxiv.org/html/2605.26938#S4.E6)\), minimizes the total cost of all fired transitions\. Synchronous moves incur zero cost, visible log/model deviations cost 1, andτ\\tau\-model moves incur a negligible costϵ\>0\\epsilon\>0\(e\.g\.,10−610^\{\-6\}\)\.

Constraint \([7](https://arxiv.org/html/2605.26938#S4.E7)\) ensures global token balance across all places, requiring that the fired transitions transform the initial markingmim\_\{i\}into the final markingmfm\_\{f\}\. Constraint \([8](https://arxiv.org/html/2605.26938#S4.E8)\) guarantees that all intermediate markings remain nonnegative, thereby preserving Petri\-net firing feasibility at every prefix of the alignment\. Constraint \([9](https://arxiv.org/html/2605.26938#S4.E9)\) enforces that at each step exactly one transition fires or, alternatively, that the alignment has already terminated\.

Constraint \([10](https://arxiv.org/html/2605.26938#S4.E10)\) ensures that once the alignment terminates \(zk=1z\_\{k\}=1\), it remains terminated in all subsequent steps\.

Binary decision variables are defined by Constraint \([11](https://arxiv.org/html/2605.26938#S4.E11)\) for all transition\-step combinations and termination indicators\.

A natural LP relaxation replaces \([11](https://arxiv.org/html/2605.26938#S4.E11)\) by0≤xj,k≤1,0≤zk≤10\\leq x\_\{j,k\}\\leq 1,\\;0\\leq z\_\{k\}\\leq 1, while keeping \([7](https://arxiv.org/html/2605.26938#S4.E7)\)–\([10](https://arxiv.org/html/2605.26938#S4.E10)\) unchanged\. This provides a lower bound for the MILP and can serve as a heuristic butit does not guarantee integrality\. This is because the incidence matrixIIis not totally unimodular for many Petri\-nets that include free\-choice, AND\-splits and joins, synchronization and loops\. Even if the incidence matrix would be totally unimodular, the combined constraint matrix in \([7](https://arxiv.org/html/2605.26938#S4.E7)\)–\([10](https://arxiv.org/html/2605.26938#S4.E10)\) is typically*not*totally unimodular since the prefix\-feasibility constraints \([8](https://arxiv.org/html/2605.26938#S4.E8)\) introduce cumulative blocks that place multiple identical copies ofIIin the same columns across many rows\. Moreover, the per\-step equalities \([9](https://arxiv.org/html/2605.26938#S4.E9)\) couple allx⋅,kx\_\{\\cdot,k\}densely within each time slice; and these dense assignment\-like rows interact with the global balance rows \([7](https://arxiv.org/html/2605.26938#S4.E7)\)\. Together, these patterns violate standard TU criteria \(e\.g\., Ghouila\-Houri\), so the LP relaxation can admit fractional solutions in general, which was confirmed in experiments\.

Thus, the LP relaxation of the MILP is generally insufficient, necessitating the solution of the full MILP to obtain an optimal alignment\. As expected, preliminary experiments confirmed that MILP formulations consistently exceeded practical time limits and are therefore excluded from our empirical evaluation\.

## 5Illustrative Example as a Minimum\-Cost Network Flow

![Refer to caption](https://arxiv.org/html/2605.26938v1/x1.png)\(a\)
![Refer to caption](https://arxiv.org/html/2605.26938v1/x2.png)\(b\)
![Refer to caption](https://arxiv.org/html/2605.26938v1/x3.png)\(c\)

Figure 5:\(a\) A process of handling insurance claims by an insurance company, and \(b\) a trace representing a process realization\. \(c\) is the Synchronous product between the trace \(labeled as an event net\) and the process model \(labeled as a process net\) with synchronous moves\. The three figures were taken fromAdriansyah \([2014](https://arxiv.org/html/2605.26938#bib.bib2)\)\.We now use the illustrative example shown in Fig\.[5](https://arxiv.org/html/2605.26938#S5.F5)\(process, trace, and their synchronous product\) to demonstrate how the LP formulation can be instantiated as a minimum\-cost flow problem on the state graph induced by the synchronous product\.

### 5\.1State Graph from the Synchronous Product

LetS​P=\(P,T,F,λ,mi,mf\)SP=\(P,T,F,\\lambda,m\_\{i\},m\_\{f\}\)be the synchronous product in Fig\.[5](https://arxiv.org/html/2605.26938#S5.F5)c\. Its*state graph*isG=\(V,E\)G=\(V,E\)with

V=ℛ​\(S​P\)V=\\mathcal\{R\}\(SP\): all markings reachable frommim\_\{i\}inS​PSP, and

E=\{e=\(v,t,v′\)∣v∈V,t∈T​enabled at​v,v′=v\+IS​P​\(⋅,t\)\}E=\\\{\\,e=\(v,t,v^\{\\prime\}\)\\mid v\\in V,\\ t\\in T\\text\{ enabled at \}v,\\ v^\{\\prime\}=v\+I\_\{SP\}\(\\cdot,t\)\\,\\\}, whereIS​PI\_\{SP\}is the incidence matrix of the synchronous product \(see, Table[2](https://arxiv.org/html/2605.26938#S5.T2)\)\.

For eachv∈Vv\\in Vwe write the outgoing and incoming arc sets as

δ\+​\(v\)\\displaystyle\\delta^\{\+\}\(v\)=\{e=\(v,t,v′\)∈E\},\\displaystyle=\\\{\\,e=\(v,t,v^\{\\prime\}\)\\in E\\,\\\},δ−​\(v\)\\displaystyle\\delta^\{\-\}\(v\)=\{e=\(u,t,v\)∈E\}\.\\displaystyle=\\\{\\,e=\(u,t,v\)\\in E\\,\\\}\.Enabledness is defined using the backward incidence matrixW−W^\{\-\}of the synchronous productS​PSP—a transitionttis enabled at markingvvif and only ifv​\(p\)≥W−​\(p,t\)v\(p\)\\geq W^\{\-\}\(p,t\)for allp∈Pp\\in P\.

Table 2:Incidence matrix of the synchronous product of Fig\.[5](https://arxiv.org/html/2605.26938#S5.F5)\.Synchronous MovesModel MovesLog Moves\(t1,t1′\)\(t\_\{1\},t\_\{1\}^\{\\prime\}\) \(t4,t2′\)\(t\_\{4\},t\_\{2\}^\{\\prime\}\) \(t1,t3′\)\(t\_\{1\},t\_\{3\}^\{\\prime\}\) \(t6,t4′\)\(t\_\{6\},t\_\{4\}^\{\\prime\}\) \(t7,t5′\)\(t\_\{7\},t\_\{5\}^\{\\prime\}\) \(t1,≫\)\(t\_\{1\},\\gg\) \(t2,≫\)\(t\_\{2\},\\gg\) \(t3,≫\)\(t\_\{3\},\\gg\) \(t4,≫\)\(t\_\{4\},\\gg\) \(t5,≫\)\(t\_\{5\},\\gg\) \(t6,≫\)\(t\_\{6\},\\gg\) \(t7,≫\)\(t\_\{7\},\\gg\) \(t8,≫\)\(t\_\{8\},\\gg\) \(t9,≫\)\(t\_\{9\},\\gg\) \(t10,≫\)\(t\_\{10\},\\gg\) \(≫,t1′\)\(\\gg,t\_\{1\}^\{\\prime\}\) \(≫,t2′\)\(\\gg,t\_\{2\}^\{\\prime\}\) \(≫,t3′\)\(\\gg,t\_\{3\}^\{\\prime\}\) \(≫,t4′\)\(\\gg,t\_\{4\}^\{\\prime\}\) \(≫,t5′\)\(\\gg,t\_\{5\}^\{\\prime\}\) p1p\_\{1\}−1\-10−1\-100−1\-100000000000000p2p\_\{2\}101001−1\-10000000000000p3p\_\{3\}0−1\-1000010−1\-100000000000p4p\_\{4\}1010010−1\-1000000000000p5p\_\{5\}0−1\-1000001−1\-100000000000p6p\_\{6\}010000001−1\-100−1\-10000000p7p\_\{7\}000−1\-1000001−1\-1000000000p8p\_\{8\}0001000000100−1\-1000000p9p\_\{9\}0000−1\-1000010−1\-100000000p10p\_\{10\}0000100000010−1\-1000000p11p\_\{11\}00000000000011−1\-100000p12p\_\{12\}00000000000000100000p1′p\_\{1\}^\{\\prime\}−1\-100000000000000−1\-10000p2′p\_\{2\}^\{\\prime\}1−1\-100000000000001−1\-1000p3′p\_\{3\}^\{\\prime\}01−1\-100000000000001−1\-100p4′p\_\{4\}^\{\\prime\}001−1\-100000000000001−1\-10p5′p\_\{5\}^\{\\prime\}0001−1\-100000000000001−1\-1p6′p\_\{6\}^\{\\prime\}00001000000000000001

### 5\.2Move Costs for the Example

We adopt the move\-cost function of Definition[4](https://arxiv.org/html/2605.26938#Thmdefinition4)by which synchronous moves have cost0,τ\\tau\-model moves have costϵ\>0\\epsilon\>0\(tiny\), and all other non\-synchronous moves have cost11\. For Fig\.[5](https://arxiv.org/html/2605.26938#S5.F5), the\|T\|=20\|T\|=20transitions are ordered as in Table[2](https://arxiv.org/html/2605.26938#S5.T2), with the cost vector

c=\(0,0,0,0,0,1,1,1,1,ϵ,1,1,1,ϵ,1,1,1,1,1,1\),c=\(0,0,0,0,0,1,1,1,1,\\epsilon,1,1,1,\\epsilon,1,1,1,1,1,1\),where indexjjcorresponds to thejj\-th transition \(column\) of Table[2](https://arxiv.org/html/2605.26938#S5.T2)\. Each arce=\(v,tj,v′\)∈Ee=\(v,t\_\{j\},v^\{\\prime\}\)\\in Einherits the transition cost, i\.e\.,w​\(e\)=cjw\(e\)=c\_\{j\}\.

### 5\.3Start/End Balance

For Fig\.[5](https://arxiv.org/html/2605.26938#S5.F5), the initial marking ismi=\[p1,p1′\]m\_\{i\}=\[p\_\{1\},p^\{\\prime\}\_\{1\}\]and the final marking ismf=\[p12,p6′\]m\_\{f\}=\[p\_\{12\},p\_\{6\}^\{\\prime\}\]\. The balance vectorbbroutes a single case frommim\_\{i\}tomfm\_\{f\}as defined in Section[4\.2](https://arxiv.org/html/2605.26938#S4.SS2)\.

### 5\.4Min\-Cost Flow LP

Letxe∈\[0,1\]x\_\{e\}\\in\[0,1\]be the flow on arce∈Ee\\in E\. The alignment problem is an instance of the LP formulation \([3](https://arxiv.org/html/2605.26938#S4.E3)\)–\([5](https://arxiv.org/html/2605.26938#S4.E5)\), with edge weightsw​\(e\)w\(e\)as defined in Definition[6](https://arxiv.org/html/2605.26938#Thmdefinition6)and balance vectorbbenforcing a single unit of flow frommim\_\{i\}tomfm\_\{f\}\.

### 5\.5Solving and Reading the Alignment

The node\-arc incidence matrix ofGGis totally unimodular; sincebbis integral, an optimal*basic*solution of the LP is integral and thus yields a singlemi→mfm\_\{i\}\\\!\\to m\_\{f\}path𝒫=\{e1,…,eL\}\\mathcal\{P\}=\\\{e\_\{1\},\\dots,e\_\{L\}\\\}\.

Traversing𝒫\\mathcal\{P\}recovers the alignment\. Mathematically, foreℓ=\(vℓ,tℓ,vℓ\+1\)e\_\{\\ell\}=\(v\_\{\\ell\},t\_\{\\ell\},v\_\{\\ell\+1\}\), append

\(a,a\)\(a,a\)iftℓt\_\{\\ell\}is a synchronous move on labelaa,

\(a,≫\)\(a,\\gg\)iftℓt\_\{\\ell\}is a log move onaa,

\(≫,a\)\(\\gg,a\)iftℓt\_\{\\ell\}is a model move onaa\(includingτ\\tau\)\.

Because synchronous transitions have zero\-cost, the optimal path uses synchronous arcs wherever enabled, inserting the minimum number of \(costly\) log/model moves necessary to connectmim\_\{i\}tomfm\_\{f\}\.

## 6Experiments

### 6\.1Experimental Design

Our experimental evaluation, including more than 2\.1 million process instances across a variety of publicly available process mining datasets, aims to identify the conditions under which one approach may be more suitable, and the key factors governing algorithms’ performance\.

Initial experiments revealed that performance varies across datasets in ways not explained by conventional factors such as trace length or model size\. We hypothesize that fitness affects the depth of the search methods such asA∗A^\{\*\}\(that is, the number of alignment steps\), and precision governs the size of the synchronous product and reachability graph explored in optimization\-based approaches\.

Therefore, for each dataset we discovered a collection of process models exhibiting varying levels of fitness and precision by applying several well\-established discovery algorithms, including the Alpha Miner\(Van der Aalstet al\.,[2004](https://arxiv.org/html/2605.26938#bib.bib37)\), the Heuristics Miner using multiple dependency\-filtering thresholds\(Weijterset al\.,[2006](https://arxiv.org/html/2605.26938#bib.bib33)\), and the Inductive Miner \(IM\)\(Leemanset al\.,[2013](https://arxiv.org/html/2605.26938#bib.bib18)\), for which we performed a noise\-threshold search over the range\[0\.0,0\.4\]\[0\.0,0\.4\]\. Fitness and precision were evaluated using token\-based replay techniques followingRozinat and Van der Aalst \([2008](https://arxiv.org/html/2605.26938#bib.bib23)\)\. We selected process models using a two\-tier strategy\. For most datasets, we targeted sound models achieving fitness≥0\.9\\geq 0\.9and precision≥0\.7\\geq 0\.7, consistent with quality thresholds commonly employed in real\-world process mining applications\. To test our hypothesis that alignment cost proxied by model fitness is the primary determinant of LP advantage, we supplemented these models with additional variants spanning the fitness\-precision spectrum\. This design enables systematic comparison of algorithm performance across diverse model characteristics\. For the PLG2 synthetic benchmark, we employed the reference models provided with each generated log\(Burattin and Sperduti,[2010](https://arxiv.org/html/2605.26938#bib.bib11); Munoz\-Gamaet al\.,[2014](https://arxiv.org/html/2605.26938#bib.bib21)\)\. We also screened additional candidate logs, including BPI Challenge 2015, but did not include them when the discovered process models consistently exhibited very low precision across discovery methods, since such underconstrained models are not suitable reference models for the type of control\-flow conformance evaluation considered in this paper\.

By comparing algorithm behavior across a fitness\-precision spectrum within each dataset, we can isolate systematic empirical relationships between model characteristics and the relative efficiency ofA∗A^\{\*\}versus LP, independent of dataset\-specific confounds\.

In the used LP implementation, we first construct explicitly a bounded reachability subgraph of the synchronous product by breadth\-first exploration up to a practical depth limit, and only then solve the LP on that constructed subgraph\. Hence, unless stated otherwise, the reported RG node counts, edge counts, and RG\-construction times refer to this bounded subgraph\. Instances for which graph construction exceeded the time or size limit were reported as timeouts\. For all instances solved by both methods, the LP objective value matched theA∗A^\{\*\}objective value, as expected\. In the implementation,τ\\tau\-edge pruning was disabled, and the only active pruning during reachability\-graph construction was elimination of self\-loops, which is safe because self\-loops leave the marking unchanged and, under the nonnegative move\-cost structure used here, cannot improve a minimum\-cost path to the final marking\.

### 6\.2Hardware and Software Environment

Experiments were executed on a server with two Intel Xeon Gold 6248R processors \(48 cores\) and 403 GB RAM\. All code ran inPython3\.9\.21\. Both methods were executed sequentially on a single process\.

The two methods rely on LP solvers for different purposes and at different scales\. The URC2formulation was solved usingGurobi11 \(primal simplex method, 30\-second timeout\)\.PM4Py’sA∗A^\{\*\}implementation \(version 2\.7\.19\.1\) usescvxopt\_solver\_custom\_align, a lightweight LP backend optimized for alignment computation, to solve the marking\-equation heuristic during search\. Each heuristic LP hasO​\(\|P\|\+\|T\|\)O\(\|P\|\+\|T\|\)variables and is invoked at every expanded search state\. In contrast, URC2solves a single LP defined over the reachability graph, with a much higher number of variables that corresponds to the number of edges in the constructed RG\. We verified that this solver asymmetry does not favor URC2\. On the contrary, replacingPM4Py’s solver with Gurobi for the marking\-equation heuristic resulted in a significant \( 3×\\times\) slowdown ofA∗A^\{\*\}, because Gurobi’s per\-call overhead dominates on the small LPs called hundreds of times per trace\. The default solver configuration is therefore already favorable toA∗A^\{\*\}\.

We compare against standardA∗A^\{\*\}rather than specialized variants because \(1\) it is the default in major toolkits and represents the highly optimized, practitioner\-facing implementation most commonly used in practice; \(2\) advanced variants improve heuristics and pruning within the same search paradigm but do not change the fundamental sensitivity of best\-first search to alignment cost, and \(3\) our contribution, polynomial\-time optimality via LP, is independent of the baseline\.

PM4Pybenefits from CPython\-compiled internals \(e\.g\., the heap queue implemented in C and a custom\-optimizedcvxoptbackend\) and years of engineering optimization\. URC2’s reachability graph construction accelerates the core successor\-computation loops via Numba JIT compilation, but the surrounding orchestration remains in Python\. Overall,PM4Pyrepresents a substantially more mature and optimized implementation, which if anything favorsA∗A^\{\*\}in the reported comparison\. To support reproducibility, the implementation and experiment scripts are publicly available in the author’s[GitHub repository](https://github.com/Izack-Cohen/unimodular-conformance-checking)\. Raw event logs are not redistributed and should be obtained from their original public sources\.

### 6\.3Datasets

To evaluate the conformance checking approaches, we selected four widely studied real\-life event logs from different domains–public administration, financial services, and healthcare, and a set of standard synthetic datasets from the PLG2 process generator with a reference model\. These datasets are typical in process mining research and provide a broad spectrum of trace lengths, behavioral complexity, and model sizes\. Table[3](https://arxiv.org/html/2605.26938#S6.T3)summarizes key characteristics of the used datasets\.

Table 3:Overview of the datasets used in our study\.DatasetDomainLengthNotesRoad Traffic Fine\(de Leoni and Mannhardt,[2015](https://arxiv.org/html/2605.26938#bib.bib14)\)Public Administration2–20High\-volume, low variabilityBPI Challenge 2012\(van Dongen,[2012](https://arxiv.org/html/2605.26938#bib.bib35)\)Financial Services3–175Loan application with complex decision pointsBPI Challenge 2013\(Steeman,[2013](https://arxiv.org/html/2605.26938#bib.bib28)\)IT Service Management1–123Help\-desk tickets; low structural complexitySepsis Cases\(Mannhardt,[2016](https://arxiv.org/html/2605.26938#bib.bib20)\)Healthcare1–400High variability; emergency workflowsPLG2 Synthetic\(Burattin and Sperduti,[2010](https://arxiv.org/html/2605.26938#bib.bib11)\)Benchmark12–167Synthetic models with noise injection

Here is a brief description of each dataset\.

##### Road Traffic Fine Management Process

This event log originates from an Italian municipal system for managing traffic fines\. It contains real\-world cases with short traces \(2–20 events\) representing procedural steps such as fine creation, payment, and appeal\. The dataset is frequently used in benchmarking studies due to its high volume and simple behavioral structurede Leoni and Mannhardt \([2015](https://arxiv.org/html/2605.26938#bib.bib14)\)\.

##### BPI Challenge 2012 \(Loan Application\)

The BPI Challenge 2012 event log\(van Dongen,[2012](https://arxiv.org/html/2605.26938#bib.bib35)\)corresponds to a Dutch financial institution’s loan application process\. It contains traces with more complex structures than the Road traffic Fine Management event log, including data attributes, cancellations, and loops\. With traces ranging from 3 to 175 activities\. It is widely used in alignment, discovery, and performance analysis research\.

##### BPI Challenge 2013 \(Incident Management\)

This dataset captures an incident and problem management process from a large IT service provider\(Steeman,[2013](https://arxiv.org/html/2605.26938#bib.bib28)\)\. Trace lengths range range from 1–123 events, and the process has a low structural complexity with discovered models that typically contain less than 20 places\. The dataset has been used extensively for evaluating conformance checking, predictive monitoring, and behavior analysis\.

##### Sepsis Cases \(Hospital Emergency Care\)

The Sepsis Cases log\(Mannhardt,[2016](https://arxiv.org/html/2605.26938#bib.bib20)\)contains patient event recordings from the emergency department of a Dutch hospital\. It includes clinical activities such as lab tests, diagnosis, and treatment steps\. The dataset is characterized by high trace variability and complex medical processes with 3–185 events per case\. It is a standard benchmark for evaluating conformance checking under high variability\.

##### Synthetic PLG2 Benchmark Suite

We employed synthetic logs generated using the PLG2 process generator\(Burattin and Sperduti,[2010](https://arxiv.org/html/2605.26938#bib.bib11)\)\. The benchmark includes models, clean traces \(perfect fitness\) and noise\-augmented variants with injected deviations, enabling controlled comparison of algorithm behavior under varying conformance levels\.

### 6\.4Performance Metrics

We evaluated the methods using the following metrics:

- –Optimality: Percentage of traces solved to optimality within the time limit \(30 s\)\.
- –Cost Agreement: Verification that both methods produced identical alignment costs was confirmed for all completed instances\.
- –Computation Time: Mean across all solved traces\.
- –Scalability: Performance correlation with trace length, model size, etc\.

When relevant, we categorized results by trace length, fitness, and model size to identify where one method begins to outperform the other\.

## 7Results

This section reports the results for the investigated datasets and process–model variants\. Throughout this section, we distinguish between*traces*and*conformance checking instances*\. A conformance checking instance is defined as a pair\(σ,M\)\(\\sigma,M\), where a traceσ\\sigmais evaluated against a specific process–model variantMM\. Because multiple model variants are evaluated per dataset, the number of instances substantially exceeds the number of traces\.

Unless stated otherwise, all performance statistics \(runtime, win rates, speedups\) are averages computed over completed conformance checking instances\. The total number of evaluated conformance checking instances exceeds 2\.1 million\.

### 7\.1Aggregate Performance Overview

Table[4](https://arxiv.org/html/2605.26938#S7.T4)summarizes the performance ofA∗A^\{\*\}and LP across the datasets\. The results confirm that both methods produce identical optimal alignment costs, validating the theoretical correctness of the LP formulation\.

Table 4:Aggregate performance comparison across datasets\. All alignment costs matched betweenA∗A^\{\*\}and LP \(100% cost agreement\)\. Win rate indicates the percentage of instances where LP was faster thanA∗A^\{\*\}\. When Optimal is less than 100% some instances timed out\.†\\daggerPLG2 comprises 4 unique process models evaluated across 21 log configurations \(clean/noisy variants with different trace lengths\)\.Trace LengthMean TimeDatasetTracesInstancesModelsMinMeanMaxPlacesA∗A^\{\*\}LPWinOptimal\(\#\)\(\#\)\(\#\)\(mean\)\(ms\)\(ms\)\(%\)\(%\)Sepsis Cases1,0509,4509313\.918525\.57881,17219\.195\.3BPI Challenge 201213,08752,3484320\.017532\.535612826\.1100\.0BPI Challenge 20137,55475,5401018\.71239\.78\.618\.129\.5100\.0Road Traffic Fine150,3701,954,8101323\.72020\.29\.3113\.52\.7100\.0PLG2 Synthetic40,50040,5004†1233\.916737–31763068814\.199\.3Total212,5612,132,64840

### 7\.2Key Findings

Our experiments reveal a hierarchy of factors that determine the relative performance ofA∗A^\{\*\}versus LP:

1. 1\.Alignment cost \(deviations\): The dominant factor\. When traces deviate significantly from the model \(higher alignment costs\),A∗A^\{\*\}’s search space explodes while LP maintains stable performance\. Figure[6](https://arxiv.org/html/2605.26938#S7.F6)illustrates this contrast:A∗A^\{\*\}time grows exponentially with alignment cost, while LP time is governed by reachability graph size regardless of conformance level\. This explains why LP is slower for perfectly conforming traces \(cost 0\) than for traces with 1–2 deviations\. Cost\-0 traces come from longer traces that produce larger reachability graphs \(1,736 vs\. 395 nodes\)\. The effect of increasing alignment costs is dramatic, withA∗A^\{\*\}slowing down up to 366×\\timeson noisy synthetic traces while LP time remains essentially constant\. BPI Challenge 2013 confirms this on real\-world data, with LP winning 96\.7% of traces with alignment cost 2–4\.
2. 2\.Model size \(places\): Strong effect on reachability graph size \(r=0\.79r=0\.79\)\. Small models \(fewer than 15 places\) favor LP regardless of trace length, as the reachability graph remains compact\. For large models with many places and specifically many silent transitions, reachability graph construction effort becomes dominant, favoringA∗A^\{\*\}\.
3. 3\.Trace length: LP’s advantage increases with trace length due toA∗A^\{\*\}’s exponential complexity in the worst case\. A clear crossover point exists for datasets with sufficient trace length variation\.
4. 4\.Model precision: Moderate and model\-dependent effect on reachability\-graph size\. In general, lower\-precision models tend to produce larger reachability graphs because they permit more behavioral alternatives\. However, this relationship is not monotone in our experiments, since precision co\-varies with other structural properties such as silent transitions and model size\. Accordingly, precision has only a weak direct effect on LP win rate \(r=0\.07r=0\.07\) and fitness/alignment cost remains the main factor\.

![Refer to caption](https://arxiv.org/html/2605.26938v1/fig_time_by_alignment_cost.png)Figure 6:Mean execution time by alignment cost\. Values in parentheses indicate mean RG size\. LP time correlates with RG size rather than alignment cost, whileA∗A^\{\*\}time grows with the number of deviations\.
### 7\.3Per\-Dataset Analysis

#### 7\.3\.1BPI Challenge 2012 \(Loan Application\)

BPI Challenge 2012 demonstrates a crossover behavior\. With 13,087 traces evaluated against 4 model variants, LP becomes increasingly competitive as trace length grows\. The models range from 25–39 places with fitness 0\.81–0\.95 and precision 0\.66–0\.75\.

Table[5](https://arxiv.org/html/2605.26938#S7.T5)presents LP win rate, speedup, and detailed time breakdown by trace length\. Figure[7](https://arxiv.org/html/2605.26938#S7.F7)illustrates the scaling behavior ofA∗A^\{\*\}and LP as trace length increases\.

Table 5:BPI Challenge 2012: LP win rate, speedup of LP with respect toA∗A^\{\*\}, and time breakdown by trace length\. RG = reachability graph construction time; Solve = LP solver time\.TraceLengthInstancesLP Win\(%\)SpeedupA∗A^\{\*\}\(ms\)LP Total\(ms\)RG\(ms\)Solve\(ms\)RGNodes1–1025,8680\.10\.33×\\times7\.823\.79\.114\.430711–205,4046\.00\.52×\\times42\.682\.530\.951\.386721–307,38843\.21\.01×\\times148\.8147\.558\.089\.01,40731–509,63267\.52\.25×\\times559\.4248\.8105\.0143\.22,08751–1003,82089\.15\.03×\\times2,456488\.4214\.8272\.83,442\>\>10023699\.28\.51×\\times9,9031,164577\.2585\.26,440

![Refer to caption](https://arxiv.org/html/2605.26938v1/x4.png)Figure 7:Mean execution time vs\. trace length forA∗A^\{\*\}and LP on BPI Challenge 2012, stratified by model fitness\. Both algorithms exhibit polynomial scaling, butA∗A^\{\*\}grows faster than LP, with crossover occurring at approximately 25–30 activities\. Fitness threshold: 0\.9\.The crossover point occurs at approximately 25 activities, where LP begins to outperformA∗A^\{\*\}in more than 50% of cases\. For traces exceeding 100 activities, LP achieves a 99\.2% win rate with an average speedup of 8\.51×\\timesoverA∗A^\{\*\}\. This confirms the theoretical advantage of LP’s polynomial complexity overA∗A^\{\*\}’s exponential worst\-case behavior\. The time breakdown reveals that reachability graph construction accounts for approximately 40–50% of LP time, providing additional speedup opportunities\.

#### 7\.3\.2BPI Challenge 2013 \(Incident Management\)

BPI Challenge 2013 provides a unique complement to BPI 2012, demonstrating that alignment cost, in addition to trace length, is a dominant factor determining LP performance\. With 7,554 unique traces evaluated against 10 model variants \(75,540 instances\), LP achieves a 29\.5% overall win rate despite short average trace lengths \(8\.7 activities\)\.

Table[6](https://arxiv.org/html/2605.26938#S7.T6)presents LP performance segmented by alignment cost\. The results reveal a striking pattern: LP wins only 2\.6% of traces with zero alignment cost \(perfect fitness\), but 96\.7% win rate on traces with alignment cost 2–4\.

Table 6:BPI Challenge 2013: LP win rate by alignment cost, demonstrating the dominant role of trace\-model deviations\. Speedup refers toA∗A^\{\*\}with respect to LP times\.Alignment CostInstancesLP Win \(%\)Speedup0 \(perfect\)44,6312\.60\.32×\\times19,67732\.90\.92×\\times2–416,65796\.71\.63×\\times5–102,93146\.81\.43×\\times\>\>101,64425\.70\.87×\\timesWe wondered why LP win rate drops for high costs \(≥5\\geq 5\)\. Analysis reveals that traces with cost\>\>10 come almost exclusively from the 2\-place model \(fitness 0\.308\), which has very small reachability graphs \(mean 29 nodes\)\. With such a compact model,A∗A^\{\*\}remains efficient even with high alignment costs because the branching factor is minimal\. The drop in LP win rate for costs 5–10 reflects a similar phenomenon: this range contains a mixture of traces from both compact models \(whereA∗A^\{\*\}excels regardless of cost\) and larger models \(where LP maintains its advantage\)\. Specifically, the 2\-place and 8\-place models contribute to this cost range, diluting LP’s overall win rate\. In contrast, costs 2–4 are dominated by traces from the 12\-place model \(fitness 0\.902, mean 135 RG nodes\), where LP achieves 98\.2% win rate \(see, Table[7](https://arxiv.org/html/2605.26938#S7.T7)\)\. This confirms that model size modulates the alignment\-cost effect: LP’s advantage on nonconforming traces is strongest when reachability graphs are sufficiently large to offset construction overhead\.

Table[7](https://arxiv.org/html/2605.26938#S7.T7)provides a thorough analysis across different model configurations, revealing how fitness, precision, and size interact\. For example, the 8\-place models provide a clear demonstration: all have identical RG size \(77 nodes\) but vary dramatically in LP win rate based solely on fitness\. The model with fitness 0\.940 \(average alignment cost was 1\.8\) achieves 99\.4% LP win rate, while the model with fitness 0\.999 \(average alignment cost was 0\.0\) achieves only 6\.8%\. This 15×\\timesdifference in LP win rate is entirely explained by alignment cost\.

Table 7:BPI Challenge 2013: Model characteristics and algorithm performance\. Precision affects RG size; fitness \(via alignment cost\) determines LP win rate\.PlacesFitnessPrecisionRG NodesMean CostLP Win \(%\)20\.3080\.600297\.757\.980\.9400\.924771\.899\.480\.9970\.912770\.112\.980\.9970\.885770\.111\.480\.9990\.883770\.06\.8100\.9250\.8311740\.40\.1100\.9290\.7161160\.54\.0110\.9960\.6241350\.13\.3120\.9020\.7231352\.298\.2171\.0000\.6268710\.00\.6
#### 7\.3\.3Sepsis Cases \(Hospital Emergency Care\)

The Sepsis dataset \(1,050 unique traces×\\times9 model variants = 9,450 instances, 9,010 valid\) presents a challenging case for LP due to large reachability graphs \(mean 8,215 nodes\)\. The models range from 22–34 places with fitness 0\.88–0\.93 and precision 0\.52–0\.70\. Despite high LP overhead, LP achieves a 19\.1% overall win rate, with performance improving significantly for longer traces\.

Table[8](https://arxiv.org/html/2605.26938#S7.T8)presents LP performance stratified by trace length\.

Table 8:Sepsis Cases: LP win rate by trace length, showing crossover at approximately 20–25 activities\. Speedup refers toA∗A^\{\*\}with respect to LP times\.Trace LengthInstancesLP Win \(%\)SpeedupMeanA∗A^\{\*\}Mean LP1–207,90916\.20\.34×\\times350 ms1,045 ms21–501,04039\.11\.34×\\times2,679 ms1,993 ms\>\>506160\.76\.98×\\times25\.3 s3,631 ms

The crossover occurs at approximately 20–25 activities, higher than BPI 2012 due to the larger reachability graphs\. For the longest traces \(\>\>50 activities\), LP achieves nearly 7×\\timesspeedup\. Note that 95\.3% of instances produced optimal alignments from both methods; the remaining 4\.7% timed out during LP reachability graph construction on the most complex model variant \(34 places\)\.

#### 7\.3\.4Road Traffic Fine Management

Road Traffic Fine, which includes very short traces \(mean 3\.7 activities, max 20\), was evaluated using 13 model variants\. Combined with high fitness models, this creates conditions strongly favoringA∗A^\{\*\}\. LP win rate, which is only 2\.7%, is associated with the longer traces \(15\-20 activities\) from lower\-fitness model variants where alignment costs exceed 2\-3 deviations\.

#### 7\.3\.5PLG2 Synthetic Benchmark

We mainly selected PLG2 synthetic datasets to provide controlled experiments that highlight the role of alignment cost, and fitness as its proxy, in determining algorithm performance\. The benchmark comprises 21 log files based on 4 unique process models, with clean and noisy trace variants at different trace lengths\. Each log is evaluated against its reference model \(hence instances = traces = 40,500\)\. Of these, 40,230 instances \(99\.3%\) produced optimal alignments from both methods\.

From this benchmark, Table[9](https://arxiv.org/html/2605.26938#S7.T9)compares clean \(perfect fitness\) and noisy variants across representative models\.

Table 9:PLG2 synthetic benchmark: clean vs\. noisy trace variants\. Each row pair shows the same model with clean traces \(perfect fitness\) and noisy traces \(with injected deviations\)\.A∗A^\{\*\}slowdown indicates the ratio of noisy to cleanA∗A^\{\*\}runtime\.ModelVariantTracesPlacesFitnessMeanlengthMeanA∗A^\{\*\}MeanLPLP win\(%\)A∗A^\{\*\}slowdownA48\-m37Clean2,000551\.00036\.513\.4 ms728\.5 ms0\.2–Noisy2,000550\.98236\.2685\.0 ms667\.8 ms19\.151×\\timesA48\-m50Clean2,000551\.00049\.814\.4 ms981\.0 ms0\.1–Noisy2,000550\.98249\.92,745 ms1,046 ms34\.8190×\\timesA32\-m27Clean2,000371\.00026\.77\.4 ms109\.5 ms0\.4–Noisy2,000370\.96626\.775\.4 ms106\.4 ms31\.610×\\timesA32\-m41Clean2,000371\.00041\.39\.8 ms189\.5 ms0\.1–Noisy2,000370\.95640\.9589\.4 ms185\.6 ms63\.960×\\timesA57\-m52Clean2,000641\.00052\.315\.4 ms1,856 ms0\.0–Noisy2,000640\.97151\.15,635 ms1,759 ms41\.2366×\\times

On clean traces \(perfect fitness\),A∗A^\{\*\}dominates with sub\-millisecond execution times because the heuristic guides search directly to the optimal alignment\. However, when noise is introduced:

- –A∗A^\{\*\}slows down by 10–366×\\timesrelative to its clean\-trace performance on the same model due to increased search efforts,
- –LP time remains essentially unchanged \(within 10%\) because the reachability graph size is independent of alignment cost, and
- –LP win rate increases from<<1% to 19–64%\.

Aggregating across all PLG2 logs: clean traces \(11 logs, 20,230 instances\) show 0\.2% LP win rate with meanA∗A^\{\*\}time of 32\.2 ms, while noisy traces \(10 logs, 20,000 instances\) show 28\.1% LP win rate with meanA∗A^\{\*\}time of 1,234 ms—a 38×\\timesaverage slowdown forA∗A^\{\*\}\.

### 7\.4LP\-Dominant Conditions

Based on our experimental analysis, Table[10](https://arxiv.org/html/2605.26938#S7.T10)identifies the conditions under which LP consistently outperformsA∗A^\{\*\}\.

Table 10:LP\-dominant subsets: Performance when restricting to favorable conditions\. Speedup refers toA∗A^\{\*\}with respect to LP times\.DatasetConditionInstancesLP Win \(%\)SpeedupBPI Challenge 2012Trace\>\>504,05689\.75\.47×\\timesBPI Challenge 2012Trace\>\>10023699\.28\.51×\\timesBPI Challenge 2013Cost≥\\geq221,23284\.31\.58×\\timesSepsis CasesTrace\>\>506160\.76\.98×\\timesPLG2 A48\-m50\-noiseTrace\>\>5087879\.43\.33×\\timesTo understand LP performance bottlenecks, we analyzed the time distribution between reachability graph construction and LP solving\. Table[11](https://arxiv.org/html/2605.26938#S7.T11)includesA∗A^\{\*\}time for direct comparison\.

Table 11:LP time breakdown: RG construction vs\. LP solving, withA∗A^\{\*\}comparison\. RG \(%\) is computed as RG Build / \(RG Build \+ LP Solve\)\. remaining time \(∼\\sim5–10%\) includes synchronous product construction and result extraction overhead\.DatasetA∗A^\{\*\}\(ms\)RG Build\(ms\)LP Solve\(ms\)RG\(%\)RGNodesSepsis Cases78835981330\.68,215BPI Challenge 2012356547442\.01,104BPI Challenge 20138\.65\.812\.132\.1177Road Traffic Fine9\.337\.076\.232\.7797![Refer to caption](https://arxiv.org/html/2605.26938v1/fig_rg_time_vs_size.png)Figure 8:RG construction time vs\. graph size across all datasets\. The fitted line shows near\-linear scaling \(R2=0\.93R^\{2\}=0\.93\)\.Generally, reachability graph construction accounts for more than 30%, and sometimes much more, of total LP time, which includes synchronous product construction, reachability graph enumeration, LP solving, and result extraction overhead\. Figure[8](https://arxiv.org/html/2605.26938#S7.F8)shows that RG construction time scales near\-linearly with graph size across all datasets, confirming predictable overhead growth\. The size of the reachability graph, measured as the number of reachable markings \(states\), is jointly determined by process model size and trace length\. A partial correlation analysis across all datasets, correlating RG node count with process model places \(controlling for trace length\) and with trace length \(controlling for model places\), reveals that the dominant factor varies by dataset characteristics: in datasets with high trace length variability \(e\.g\., BPI 2012 with traces ranging 3–175 activities\), trace length explains nearly all variance in RG size \(R2=0\.99R^\{2\}=0\.99\); in datasets with constrained trace lengths \(e\.g\., Road Traffic Fine\), model size \(number of places\) becomes more influential \(R2=0\.50R^\{2\}=0\.50vs0\.050\.05for trace length\)\. This dataset\-dependent relationship explains why LP overhead is governed primarily by model size for short\-trace datasets, while trace length becomes the critical bottleneck for datasets with longer, more variable traces\.

### 7\.5Summary of Findings

The key findings are:

- –Correctness: For all instances solved by both methods, the LP objective value matched theA∗A^\{\*\}objective value exactly, providing strong empirical evidence that the LP formulation returns the same optimal alignment cost asA∗A^\{\*\}on the benchmarked solved cases\.
- –Scalability: LP exhibits polynomial complexity, achieving up to 8\.5×\\timesspeedup overA∗A^\{\*\}on long traces\.
- –Robustness to deviations: UnlikeA∗A^\{\*\}, LP performance is largely independent of alignment cost\. On noisy traces whereA∗A^\{\*\}slows down 10–366×\\times, LP time remains constant\. BPI 2013 confirms this finding on real\-world data: LP achieves 96\.7% win rate on traces with alignment cost 2–4\.
- –Complementarity:A∗A^\{\*\}and LP exhibit complementary performance characteristics, withA∗A^\{\*\}excelling on short, conforming traces and LP on longer traces with deviations\. This motivates a selection formula developed in Section[8](https://arxiv.org/html/2605.26938#S8)\.

The key practical insight is that LP excels in situations most relevant to conformance checking: long traces with significant deviations from the process model\.

## 8Algorithm Selection

We propose a selection formula that predicts the faster method using features available before execution\. The formula builds on two observations: \(1\)A∗A^\{\*\}exhibits exponential degradation with increasing deviations while LP maintains stable performance, and \(2\) LP’s reachability graph construction overhead pays off only for sufficiently long traces\.

Since alignment cost is unknown before execution, we use model fitnessFFas a proxy\. The expected number of deviations for a trace of lengthLLcan be approximated as\(1−F\)×L\(1\-F\)\\times L, representing the proportion of non\-conformant activities multiplied by trace length\. This yields the following selection rule:

Use LP when:​L\>20∧\(1−F\)×L\>1\.5\\text\{Use LP when: \}L\>20\\land\(1\-F\)\\times L\>1\.5\(12\)whereLLis the trace length andFFis the model fitness\. The first condition ensures traces are long enough to justify LP’s construction overhead, while the second targets traces whereA∗A^\{\*\}is expected to struggle due to high alignment costs\.

The proposed selection rule is not intended as a universal threshold that is optimal across all datasets, model\-discovery pipelines, and cost settings\. Rather, it should be viewed as an empirically grounded practical guideline whose cross\-dataset robustness is confirmed by the leave\-one\-dataset\-out analysis reported below\.

Figure[9](https://arxiv.org/html/2605.26938#S8.F9)validates this threshold: LP win rate jumps from 3–7% below the threshold to 41–64% above it\.

The thresholds in Equation \([12](https://arxiv.org/html/2605.26938#S8.E12)\) were obtained through a grid search overLthresh∈\{15,20,25,30,35,40\}L\_\{\\mathrm\{thresh\}\}\\in\\\{15,20,25,30,35,40\\\}anddevthresh∈\{0\.5,1\.0,1\.5,2\.0,2\.5\}\\mathrm\{dev\}\_\{\\mathrm\{thresh\}\}\\in\\\{0\.5,1\.0,1\.5,2\.0,2\.5\\\}, selecting the combination that maximized total time savings relative to always usingA∗A^\{\*\}while avoiding regression on any individual dataset\. The selected combination lies in a stable region of the parameter space: nearby alternatives produce comparable savings \(Table[13](https://arxiv.org/html/2605.26938#S8.T13)\), indicating that the result is not sensitive to the precise threshold values\. To verify that this stability extends across datasets, we performed leave\-one\-dataset\-out \(LODO\) cross\-validation: in each of five folds the grid search was re\-run on four datasets and the winning thresholds were evaluated on the held\-out dataset\. Every fold selectedL∈\{20,25\}L\\in\\\{20,25\\\}anddev∈\{1\.0,1\.5\}\\mathrm\{dev\}\\in\\\{1\.0,1\.5\\\}, and Equation \([12](https://arxiv.org/html/2605.26938#S8.E12)\) matched or outperformed the LODO\-optimal rule on four of five held\-out datasets\. The single exception \(BPI 2013\) differed by only 0\.5 percentage points\. On the Sepsis fold, where the LODO\-optimal rule chose a more aggressive deviation threshold \(1\.01\.0vs\.1\.51\.5\), Equation \([12](https://arxiv.org/html/2605.26938#S8.E12)\) achieved higher savings \(\+28\.4%\+28\.4\\%vs\.\+20\.0%\+20\.0\\%\) because the conservative threshold avoids selecting LP on traces with prohibitively large reachability graphs\. We note that while model precision and silent transitions influence LP overhead, they did not improve the selection rule consistently beyond trace length and fitness in our experiments\. We therefore retain the two\-feature rule for interpretability; richer selection models incorporating structural features are left as future work\.

Consequently, LP is not selected for long traces from high\-fitness models \(e\.g\.,L=100L=100withF=0\.99F=0\.99yields\(1−F\)×L=1\.0<1\.5\(1\-F\)\\times L=1\.0<1\.5\), whereA∗A^\{\*\}remains efficient despite trace length because few deviations are expected\.

![Refer to caption](https://arxiv.org/html/2605.26938v1/fig_lp_winrate_expected_dev.png)Figure 9:LP win rate by expected deviations across all datasets\. The dashed line marks the selection threshold at\(1−F\)×L=1\.5\(1\-F\)\\times L=1\.5\.### 8\.1Empirical Validation

We evaluated the selection formula across the four real\-world datasets by simulating a hybrid approach: for each trace, we use the time of whichever algorithm the formula selects\. Table[12](https://arxiv.org/html/2605.26938#S8.T12)presents the results compared to always usingA∗A^\{\*\}\(the conventional approach\) and the theoretical oracle that always selects the faster algorithm\.

Table 12:Algorithm selection performance across datasets\. Savings are relative to always usingA∗A^\{\*\}\. The hybrid approach applies Equation[12](https://arxiv.org/html/2605.26938#S8.E12)\.DatasetInstancesAlwaysA∗A^\{\*\}HybridOracleSavingsSepsis Cases9,0107,101s5,082s3,619s\+28\.4%BPI Challenge 201252,34818,637s5,952s5,153s\+68\.1%BPI Challenge 201375,540650s658s533s−\-1\.2%Road Traffic Fine1,954,81011,665s11,665s9,079s\+0\.0%Total2,091,70838,053s23,356s18,384s\+38\.6%The formula achieves 38\.6% time savings overall, with substantial gains on datasets where LP has clear advantages \(BPI 2012: \+68\.1%, Sepsis: \+28\.4%\) while avoiding major slowdowns\. The formula shows a small slowdown on BPI 2013 \(−\-1\.2%\) due to the dataset being dominated by short, high\-fitness traces whereA∗A^\{\*\}is efficient\. The formula never selects LP for Road Traffic Fine traces because the combination of short traces \(meanL=3\.7L=3\.7\) and fitness \(F≥0\.77F\\geq 0\.77\) keeps\(1−F\)×L\(1\-F\)\\times Lbelow the threshold\.

We compared the proposed formula against simpler alternatives in Table[13](https://arxiv.org/html/2605.26938#S8.T13)\. The fitness\-based formula outperforms pure length thresholds by correctly identifying whenA∗A^\{\*\}will struggle regardless of trace length\.

Table 13:Comparison of selection formulas\. Per\-dataset savings shown as percentage improvement over always usingA∗A^\{\*\}\.FormulaSepsisBPI 2012BPI 2013RoadTotalL\>30L\>30\+20\.0\+67\.4−\-15\.0\+0\.0\+36\.5\(1−F\)×L\>2\(1\-F\)\\times L\>2\+19\.6\+66\.4−\-0\.5−\-0\.1\+36\.1Equation[12](https://arxiv.org/html/2605.26938#S8.E12)\+28\.4\+68\.1−\-1\.2\+0\.0\+38\.6Notably, the simple thresholdL\>30L\>30causes a 15\.0% slowdown on BPI 2013 because it triggers LP on long traces from high\-fitness models whereA∗A^\{\*\}is faster\. The fitness\-based formula substantially reduces this slowdown by recognizing that high fitness implies low alignment costs\. Nevertheless, using even simple rules for selecting betweenA∗A^\{\*\}and LP can lead to substantial time savings\.

### 8\.2Limitations and Error Analysis

Compared to an oracle who always selects the right option, the formula achieves 96\.0% classification accuracy, with two types of errors:

##### False Positives \(0\.36% of the instances\)

The formula selects LP butA∗A^\{\*\}was faster\. These 7,557 instances occur predominantly on low\-precision models \(<0\.6<0\.6\), where the reachability graph becomes large despite high fitness\. In such cases, LP’s graph construction overhead exceedsA∗A^\{\*\}’s search time\. The total time cost is 1,649 seconds with median cost of 92 ms per error\.

##### False Negatives \(3\.64% of instances\)

The formula selectsA∗A^\{\*\}but LP was faster\. These 76,181 instances occur almost exclusively on short traces \(L≤20L\\leq 20\), which are filtered by the length threshold\. Crucially, 94\.3% of false negatives have costs below 10 ms, meaning that the formula correctly identifies that LP’s overhead is not justified for such traces even when LP would technically be faster\. The total time cost is 3,323 seconds with median cost of only 0\.7 ms per error\.

##### Safe Mistakes

The formula prioritizes avoiding high LP overhead over capturing every LP opportunity\. Using LP on high\-fitness, low\-precision models can result in significant slowdowns, as LP must construct enormous reachability graphs for models thatA∗A^\{\*\}handles efficiently\. The formula’s conservative thresholds sacrifice potential gains on short traces \(where costs are typically small\) to prevent these high losses\.

The formula produces a net benefit of 38\.6% improvement in the total computation time compared to always usingA∗A^\{\*\}\. The total time cost of formula errors is 4,972 seconds, compared to the unattained oracle’s correct selections\.

### 8\.3Practical Considerations

The selection formula requires only trace length and model fitness, both available before conformance checking\. Model fitness is typically computed during process discovery or can be estimated efficiently using token\-based replay\. The formula adds negligible computational overhead while providing substantial time savings on datasets where LP excels\.

For practitioners, we recommend the formula as a default selection strategy when both algorithms are available\. On datasets dominated by short, conformant traces, the formula will conservatively default toA∗A^\{\*\}, incurring no penalty\. On datasets with longer traces or lower fitness, it will identify opportunities for LP acceleration\. The formula can also be tuned: lowering the length threshold toL\>15L\>15captures more LP opportunities at the cost of increased false positives, while raising the deviation threshold to\(1−F\)×L\>2\(1\-F\)\\times L\>2provides more conservative LP selection\. The LODO cross\-validation reported above confirms that the selected thresholds are not dataset\-specific: all five held\-out folds recovered thresholds within the same narrow region, supporting the use of Equation \([12](https://arxiv.org/html/2605.26938#S8.E12)\) as a default starting point for new datasets and model configurations\. Future work may explore richer selection models that incorporate additional structural features, such as precision, silent transitions, or other proxies for reachability\-graph growth\. In this paper, we deliberately retain a simple and interpretable rule based on features that are readily available before conformance checking\.

## 9Limitations and Future Directions

While our experiments demonstrate the complementary strengths of LP andA∗A^\{\*\}for conformance checking, both approaches exhibit limitations that warrant discussion\.

We deliberately compare URC2against standardA∗A^\{\*\}as implemented inPM4Py, the practical baseline most practitioners encounter, rather than specialized variants\. Our central insight that the LP defined over the reachability graph is solvable in polynomial time due to total unimodularity holds independently of the chosen baseline\.

### 9\.1Limitations of the LP Approach

The LP approach’s primary bottleneck is reachability graph construction, which consumed 30–42% of total LP time across our experiments \(Table[11](https://arxiv.org/html/2605.26938#S7.T11)\)\. This overhead becomes prohibitive under two conditions:

##### Low\-Precision Models

Models with low precision permit many behavioral paths not observed in the event log, resulting in large reachability graphs\. In our experiments, models with precision below 0\.6 produced reachability graphs where LP times can exceedA∗A^\{\*\}by factors of 40 or more, even for traces where LP would theoretically find alignments faster\. The selection formula mitigates this by avoiding LP on high\-fitness models \(whereA∗A^\{\*\}is efficient regardless of precision\), but cannot fully address cases where LP would otherwise be advantageous\.

##### Silent Transitions

Models with numerous silent \(τ\\tau\) transitions exhibit combinatorial growth in reachability graph size, as each silent transition introduces additional state\-space branches\. This effect compounds with low precision, as silent transitions often appear in “flower” constructs that generalize model behavior\. In the Sepsis dataset, models produced reachability graphs averaging 8,215 nodes, compared to 177 nodes for the simpler BPI 2013 models\.

##### Memory Considerations

The LP approach stores the reachability graph in memory, unlikeA∗A^\{\*\}’s incremental exploration\. While memory did not emerge as a bottleneck in our experiments, this trade\-off warrants future investigation\.

##### Solver Selection\.

URC2uses the Gurobi solver, whereasPM4Py’s A∗relies on cvxopt\_solver\_custom\_align, a lightweight backend specifically optimized for alignment computation\. This asymmetry reflects the differing computational profiles of the two approaches\. A∗typically solves hundreds of small LPs per trace, where solvers with low per\-call overhead are most efficient\. URC2solves a single, much larger LP over the reachability graph, where solver efficiency at scale matters\. In our experiments, equipping A∗with Gurobi increased its runtime by a factor of more than 3 due to per\-call overhead, confirming that the default configuration is already favorable to A∗\.

More broadly, achieving a perfectly symmetric comparison is inherently difficult\.PM4Py’sA∗A^\{\*\}benefits from CPython\-compiled components \(heap operations, linear algebra\) and years of engineering optimization\. URC2accelerates the core successor\-computation loops of reachability graph construction via Numba JIT compilation, but the surrounding orchestration remains in Python\. Overall,PM4Pyrepresents a more mature and optimized implementation, and the reported comparison therefore favorsA∗A^\{\*\}rather than URC2\. Engineering differences may shift the crossover point identified earlier, but the underlying complementarity betweenA∗A^\{\*\}and URC2—driven by the exponential sensitivity ofA∗A^\{\*\}to alignment cost versus the stability of the LP approach—remains independent of implementation choices\.

##### Control\-Flow Conformance

Our formulation addresses control\-flow conformance only\. The total unimodularity result relies on the reduction to a pure node–arc flow model on the reachability graph\. In multi\-perspective conformance checking, additional data, resources, or time constraints would generally appear as side constraints beyond standard flow conservation, which may destroy the network\-flow structure and the corresponding TU guarantee\. Extending the approach to such settings is therefore nontrivial and left for future work\.

These limitations suggest several directions for future work, beyond the scope of this paper\. Symbolic representations using Decision Diagrams\(Thierry\-Mieg,[2015](https://arxiv.org/html/2605.26938#bib.bib32)\)could compress the reachability graph exponentially for models with regular structure\. Lazy construction strategies could generate only selected portions of the reachability graph guided by the trace or by lower\-bound information, thereby reducing the explicit breadth\-first exploration that currently dominates LP preprocessing time in our implementation\. Additionally, GPU\-accelerated graph construction could further accelerate this preprocessing stage\.

### 9\.2Limitations of theA∗A^\{\*\}Approach

TheA∗A^\{\*\}algorithm exhibits complementary weaknesses:

##### Exponential Degradation

A∗A^\{\*\}search time grows exponentially with deviations\. Each deviation expands the search frontier as demonstrated by 10–366×\\timesslowdowns on noisy traces \(Table[9](https://arxiv.org/html/2605.26938#S7.T9)\)\. This degradation is fundamental toA∗A^\{\*\}’s best\-first search strategy and cannot be fully addressed through heuristic improvements\.

##### Unpredictable Pathologies

We observed cases whereA∗A^\{\*\}exhibited extreme runtimes on short, seemingly simple traces\. These pathological cases arise from interactions between the trace, model structure, and search heuristic that cannot be predicted from features like trace length or model fitness\.

A natural concern is whether the proposed LP formulation offers a genuine advantage overA∗A^\{\*\}search, given thatA∗A^\{\*\}does not require explicit construction of the reachability graph, whereas the LP is defined over such a graph\. Although the reachability graph of a Petri net may be exponential in the worst case, this difficulty is inherent to exact conformance checking and is not specific to the LP approach\. In our current implementation, we explicitly construct a bounded reachability subgraph of the synchronous product by breadth\-first exploration and then solve the LP on that subgraph\. A more selective construction of only the ultimately relevant states is not part of the current implementation and remains an interesting direction for future work\.

The essential difference therefore is not the elimination of state\-space explosion, but the optimization paradigm applied once a relevant portion of the state space has been constructed\. On the same constructed graph,A∗A^\{\*\}still explores states through heuristic\-guided branching, which may lead to exponential runtimes under high branching factors or long optimal alignments\. In contrast, URC2solves a single minimum\-cost flow LP on the constructed graph\. Since the corresponding constraint matrix is totally unimodular, the LP relaxation is integral, and the optimization problem is polynomially solvable in the size of the constructed graph without integer variables\. Hence, the main contribution of the LP reformulation is not to avoid state\-space explosion, but to avoid additional combinatorial optimization during alignment computation once the graph has been constructed\. This distinction explains why the LP formulation can outperformA∗A^\{\*\}in practice on long, deviating traces\.

LP andA∗A^\{\*\}exhibit complementary performance characteristics that are predictable from model quality metrics, enabling an informed and systematic selection of the most suitable approach\.

Our empirical evaluation benchmarks againstPM4Py’s standardA∗A^\{\*\}implementation\. Advances within theA∗A^\{\*\}paradigm—including the extended marking equation\(van Dongen,[2018](https://arxiv.org/html/2605.26938#bib.bib36)\), cache\-enhanced split\-point search\(Li and van Zelst,[2022](https://arxiv.org/html/2605.26938#bib.bib19)\), and REACH\(Casas\-Ramoset al\.,[2024](https://arxiv.org/html/2605.26938#bib.bib12)\)—improve heuristic quality and pruning, reducing search effort\. A direct comparison with these methods would be valuable but faces cross\-framework challenges, as these techniques are implemented outside the Python ecosystem used by bothPM4Pyand URC2\. Such a comparison, alongside LP\-side improvements such as model\-level reachability graph caching and lazy graph construction, is a promising direction for future work\. That said, we note that the complementarity between search\-based and LP\-based approaches is structural: improvedA∗A^\{\*\}variants shift the crossover point but do not eliminate the exponential sensitivity of best\-first search to alignment cost\.

## 10Conclusion

This paper demonstrated that a totally unimodular LP reformulation enables exact alignment computation on an explicitly constructed reachability graph without integer constraints\. In particular, once that graph has been constructed, the resulting optimization subproblem is polynomially solvable\.

Extensive empirical evaluation confirms that LP can significantly outperform classicalA∗A^\{\*\}search in regimes characterized by long traces and substantial deviations, achieving up to 8\.5×\\timesspeedup and 99% win rates\.

We developed an algorithm\-selection formula based on trace length and model fitness that achieves 38\.6% time savings over always usingA∗A^\{\*\}, with 96% accuracy in identifying when LP’s polynomial complexity advantage outweighs its construction overhead\.

The results provide clear, data\-driven guidance for off\-the\-shelf solver selection: use LP for long traces \(L\>20L\>20\) with expected deviations\(1−F\)×L\>1\.5\(1\-F\)\\times L\>1\.5, and default toA∗A^\{\*\}otherwise\. Leave\-one\-dataset\-out cross\-validation confirms that these thresholds generalize across datasets with diverse characteristics, enabling practitioners to adopt the rule as a robust default without specialized implementations\.

## Funding

This research was supported by the Israel Science Foundation \(ISF\), grant no\. 353/24\. The funding source had no role in the study design, analysis, interpretation of results, or decision to submit the article for publication\.

## Declaration of Competing Interest

The author declares that he has no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper\.

##### Declaration of generative AI and AI\-assisted technologies in the manuscript preparation process:

During the preparation of this work the author used ChatGPT and Claude for editing and analysis\. After using this tool/service, the author reviewed and edited the content as needed and takes full responsibility for the content of the published article\.

## References

- A\. Adriansyah, B\. F\. van Dongen, and W\. M\. van der Aalst \(2011\)Conformance checking using cost\-based fitness analysis\.InIEEE 15th international Enterprise Distributed Object Computing Conference,pp\. 55–64\.Cited by:[§2\.1](https://arxiv.org/html/2605.26938#S2.SS1.p1.2)\.
- A\. Adriansyah \(2014\)Aligning observed and modeled behavior\.PhD Thesis,Technische Universiteit EindhovenMathematics and Computer Science, Research TU/e / Graduation TU/e\.External Links:[Link](https://doi.org/10.6100/IR770080),[Document](https://dx.doi.org/10.6100/IR770080)Cited by:[§2\.1](https://arxiv.org/html/2605.26938#S2.SS1.p1.2),[Figure 5](https://arxiv.org/html/2605.26938#S5.F5),[Figure 5](https://arxiv.org/html/2605.26938#S5.F5.3.2)\.
- A\. Awad, K\. Raun, and M\. Weidlich \(2021\)Efficient approximate conformance checking using trie data structures\.In2021 3rd International Conference on Process Mining \(ICPM\),Vol\.,pp\. 1–8\.External Links:[Document](https://dx.doi.org/10.1109/ICPM53251.2021.9576845)Cited by:[§2\.2](https://arxiv.org/html/2605.26938#S2.SS2.p1.1)\.
- M\. Bauer, H\. Van der Aa, and M\. Weidlich \(2019\)Estimating process conformance by trace sampling and result approximation\.InInternational Conference on Business Process Management,pp\. 179–197\.Cited by:[§2\.2](https://arxiv.org/html/2605.26938#S2.SS2.p1.1)\.
- D\. Bertsimas and J\. N\. Tsitsiklis \(1997\)Introduction to linear optimization\.Athena Scientific\.Cited by:[§3](https://arxiv.org/html/2605.26938#S3.p13.1)\.
- V\. Bloemen, J\. van de Pol, and W\. M\.P\. van der Aalst \(2018\)Symbolically aligning observed and modelled behaviour\.In18th International Conference on Application of Concurrency to System Design \(ACSD\),Vol\.,pp\. 50–59\.External Links:[Document](https://dx.doi.org/10.1109/ACSD.2018.00008)Cited by:[§2\.4](https://arxiv.org/html/2605.26938#S2.SS4.p1.1)\.
- E\. Bogdanov, I\. Cohen, and A\. Gal \(2024\)A scalable and near\-optimal conformance checking approach for long traces\.arXiv preprint arXiv:2406\.05439\.Cited by:[§2\.3](https://arxiv.org/html/2605.26938#S2.SS3.p1.1)\.
- M\. Boltenhagen, T\. Chatain, and J\. Carmona \(2021\)Optimized sat encoding of conformance checking artefacts\.Computing103\(1\),pp\. 29–50\.Cited by:[§2\.4](https://arxiv.org/html/2605.26938#S2.SS4.p1.1)\.
- J\. C\. A\. M\. Buijs \(2014\)Flexible evolutionary algorithms for mining structured process models\.Ph\.D\. Thesis,Technische Universiteit Eindhoven\.Cited by:[§2\.2](https://arxiv.org/html/2605.26938#S2.SS2.p1.1)\.
- A\. Burattin and A\. Sperduti \(2010\)PLG: a framework for the generation of business process models and their execution logs\.InInternational Conference on Business Process Management,pp\. 214–219\.Cited by:[§6\.1](https://arxiv.org/html/2605.26938#S6.SS1.p3.3),[§6\.3](https://arxiv.org/html/2605.26938#S6.SS3.SSS0.Px5.p1.1),[Table 3](https://arxiv.org/html/2605.26938#S6.T3.4.1.6.1.1.1)\.
- J\. Casas\-Ramos, M\. Mucientes, and M\. Lama \(2024\)REACH: researching efficient alignment\-based conformance checking\.Expert Systems with Applications241,pp\. 122467\.Cited by:[§2\.1](https://arxiv.org/html/2605.26938#S2.SS1.p1.2),[§9\.2](https://arxiv.org/html/2605.26938#S9.SS2.SSS0.Px2.p5.4)\.
- L\. Cheng, C\. Liu, and Q\. Zeng \(2023\)Optimal alignments between large event logs and process models over distributed systems: an approach based on petri nets\.Information Sciences619,pp\. 406–420\.Cited by:[§2\.3](https://arxiv.org/html/2605.26938#S2.SS3.p1.1)\.
- M\. de Leoni and F\. Mannhardt \(2015\)Road traffic fine management process\.Note:4TU\.ResearchDataDatasetExternal Links:[Document](https://dx.doi.org/10.4121/uuid%3A270fd440-1057-4fb9-89a9-b699b47990f5),[Link](https://doi.org/10.4121/uuid:270fd440-1057-4fb9-89a9-b699b47990f5)Cited by:[§6\.3](https://arxiv.org/html/2605.26938#S6.SS3.SSS0.Px1.p1.1),[Table 3](https://arxiv.org/html/2605.26938#S6.T3.4.1.2.1.1.1)\.
- M\. De Leoni and W\. M\. Van Der Aalst \(2013\)Aligning event logs and process models for multi\-perspective conformance checking: an approach based on integer linear programming\.InBusiness Process Management: 11th International Conference, BPM 2013, Beijing, China, August 26\-30, 2013\. Proceedings,pp\. 113–129\.Cited by:[§2\.1](https://arxiv.org/html/2605.26938#S2.SS1.p2.1)\.
- M\. Fani Sani, S\. J\. van Zelst, and W\. M\. van der Aalst \(2020\)Conformance checking approximation using subset selection and edit distance\.InInternational Conference on Advanced Information Systems Engineering \(CAiSE\),pp\. 234–251\.Cited by:[§2\.2](https://arxiv.org/html/2605.26938#S2.SS2.p1.1)\.
- S\. J\. Leemans, D\. Fahland, and W\. M\. Van Der Aalst \(2013\)Discovering block\-structured process models from event logs\-a constructive approach\.InInternational Conference on Applications and Theory of Petri Nets and Concurrency,pp\. 311–329\.Cited by:[§6\.1](https://arxiv.org/html/2605.26938#S6.SS1.p3.3)\.
- T\. Li and S\. J\. van Zelst \(2022\)Cache enhanced split\-point\-based alignment calculation\.In2022 4th International Conference on Process Mining \(ICPM\),pp\. 120–127\.Cited by:[§2\.1](https://arxiv.org/html/2605.26938#S2.SS1.p1.2),[§9\.2](https://arxiv.org/html/2605.26938#S9.SS2.SSS0.Px2.p5.4)\.
- F\. Mannhardt \(2016\)Sepsis cases \- event log\.Note:4TU\.ResearchDataDatasetExternal Links:[Document](https://dx.doi.org/10.4121/uuid%3A915d2bfb-7e84-49ad-a286-dc35f063a460),[Link](https://doi.org/10.4121/uuid:915d2bfb-7e84-49ad-a286-dc35f063a460)Cited by:[§6\.3](https://arxiv.org/html/2605.26938#S6.SS3.SSS0.Px4.p1.1),[Table 3](https://arxiv.org/html/2605.26938#S6.T3.4.1.5.1.1.1)\.
- J\. Munoz\-Gama, J\. Carmona, and W\. M\. Van Der Aalst \(2014\)Single\-entry single\-exit decomposed conformance checking\.Information Systems46,pp\. 102–122\.Cited by:[§2\.3](https://arxiv.org/html/2605.26938#S2.SS3.p1.1),[§6\.1](https://arxiv.org/html/2605.26938#S6.SS1.p3.3)\.
- D\. Reißner, A\. Armas\-Cervantes, R\. Conforti, M\. Dumas, D\. Fahland, and M\. La Rosa \(2020\)Scalable alignment of process models and event logs: an approach based on automata and s\-components\.Information Systems94,pp\. 101561\.Cited by:[§2\.2](https://arxiv.org/html/2605.26938#S2.SS2.p1.1)\.
- A\. Rozinat and W\. M\. Van der Aalst \(2008\)Conformance checking of processes based on monitoring real behavior\.Information Systems33\(1\),pp\. 64–95\.Cited by:[§6\.1](https://arxiv.org/html/2605.26938#S6.SS1.p3.3)\.
- A\. Schrijver \(1998\)Theory of linear and integer programming\.John Wiley & Sons\.Cited by:[§3](https://arxiv.org/html/2605.26938#S3.p13.1)\.
- A\. Schrijver \(2003\)Combinatorial optimization: polyhedra and efficiency\.Algorithms and Combinatorics, Vol\.24,Springer\.Cited by:[§4\.4](https://arxiv.org/html/2605.26938#S4.SS4.p1.8),[§4](https://arxiv.org/html/2605.26938#S4.p1.1)\.
- D\. Schuster, S\. van Zelst, and W\. M\. van der Aalst \(2020\)Alignment approximation for process trees\.InInternational Conference on Process Mining,pp\. 247–259\.Cited by:[§2\.2](https://arxiv.org/html/2605.26938#S2.SS2.p1.1)\.
- C\. T\. Schwanen, W\. Pakusa, and W\. M\. van der Aalst \(2024\)Process tree alignments\.InInternational Conference on Enterprise Design, Operations, and Computing,pp\. 300–317\.Cited by:[§2\.1](https://arxiv.org/html/2605.26938#S2.SS1.p2.1)\.
- W\. Steeman \(2013\)BPI Challenge 2013, incidents\.Note:4TU\.ResearchDataExternal Links:[Document](https://dx.doi.org/10.4121/uuid%3A500573e6-accc-4b0c-9576-aa5468b10cee),[Link](https://doi.org/10.4121/uuid:500573e6-accc-4b0c-9576-aa5468b10cee)Cited by:[§6\.3](https://arxiv.org/html/2605.26938#S6.SS3.SSS0.Px3.p1.1),[Table 3](https://arxiv.org/html/2605.26938#S6.T3.4.1.4.1.1.1)\.
- É\. Tardos \(1986\)A strongly polynomial algorithm to solve combinatorial linear programs\.Operations Research34\(2\),pp\. 250–256\.Cited by:[§4\.4](https://arxiv.org/html/2605.26938#S4.SS4.p1.8),[§4](https://arxiv.org/html/2605.26938#S4.p1.1)\.
- F\. Taymouri and J\. Carmona \(2016\)A recursive paradigm for aligning observed behavior of large structured process models\.InInternational Conference on Business Process Management,pp\. 197–214\.Cited by:[§2\.3](https://arxiv.org/html/2605.26938#S2.SS3.p1.1)\.
- F\. Taymouri and J\. Carmona \(2018\)An evolutionary technique to approximate multiple optimal alignments\.InInternational Conference on Business Process Management,pp\. 215–232\.Cited by:[§2\.2](https://arxiv.org/html/2605.26938#S2.SS2.p1.1)\.
- Y\. Thierry\-Mieg \(2015\)Symbolic model\-checking using ITS\-tools\.InInternational Conference on Tools and Algorithms for the Construction and Analysis of Systems,pp\. 231–237\.Cited by:[§9\.1](https://arxiv.org/html/2605.26938#S9.SS1.SSS0.Px5.p2.1)\.
- Á\. Valencia\-Parra, Á\. J\. Varela\-Vaca, M\. T\. Gómez\-López, J\. Carmona, and R\. Bergenthum \(2021\)Empowering conformance checking using big data through horizontal decomposition\.Information Systems99,pp\. 101731\.Cited by:[§2\.3](https://arxiv.org/html/2605.26938#S2.SS3.p1.1)\.
- W\. Van der Aalst, T\. Weijters, and L\. Maruster \(2004\)Workflow mining: discovering process models from event logs\.IEEE Transactions on Knowledge and Data Engineering16\(9\),pp\. 1128–1142\.Cited by:[§6\.1](https://arxiv.org/html/2605.26938#S6.SS1.p3.3)\.
- W\. Van Der Aalst \(2016\)Data science in action\.InProcess mining: Data science in action,pp\. 3–23\.Cited by:[§3](https://arxiv.org/html/2605.26938#S3.p1.1)\.
- B\. F\. van Dongen \(2018\)Efficiently computing alignments: using the extended marking equation\.InBusiness Process Management \(BPM\),LNCS, Vol\.11080,pp\. 197–214\.External Links:[Document](https://dx.doi.org/10.1007/978-3-319-98648-7%5F12)Cited by:[§2\.1](https://arxiv.org/html/2605.26938#S2.SS1.p1.2),[§9\.2](https://arxiv.org/html/2605.26938#S9.SS2.SSS0.Px2.p5.4)\.
- B\. van Dongen \(2012\)BPI Challenge 2012\.Note:4TU\.ResearchDataExternal Links:[Document](https://dx.doi.org/10.4121/uuid%3A3926db30-f712-4394-aebc-75976070e91f),[Link](https://doi.org/10.4121/uuid:3926db30-f712-4394-aebc-75976070e91f)Cited by:[§6\.3](https://arxiv.org/html/2605.26938#S6.SS3.SSS0.Px2.p1.1),[Table 3](https://arxiv.org/html/2605.26938#S6.T3.4.1.3.1.1.1)\.
- A\. J\. Weijters, W\. M\. van Der Aalst, and A\. A\. De Medeiros \(2006\)Process mining with the heuristicsminer algorithm\.Technical reportTechnische Universiteit Eindhoven\.Cited by:[§6\.1](https://arxiv.org/html/2605.26938#S6.SS1.p3.3)\.