REACH: Researching Efficient Alignment-based Conformance Checking

Expert Systems With Applications 241 (2024) 122467 Available online 22 November 2023 0957-4174/© 2023 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/bync-nd/4.0/). Contents lists available at ScienceDirect Expert Systems With Applications journal homepage: www.elsevier.com/locate/eswa REACH: Researching Efficient Alignment-based Conformance Checking Jacobo Casas-Ramos∗, Manuel Mucientes, Manuel Lama Centro Singular de Investigación en Tecnoloxías Intelixentes (CiTIUS), Universidade de Santiago de Compostela, Santiago de Compostela, Spain ARTICLE INFO Keywords: Process mining Conformance checking Alignments ABSTRACT Conformance checking techniques compare how a process is supposed to be executed according to a model with how it is executed in reality according to an event log. Alignment-based approaches are the most successful solutions for conformance checking. Optimal alignments are a way of finding the best match between the real and the modeled behavior and identifying the differences. However, finding these optimal alignments is a challenging task, especially for complex cases where the log and the model have many events and paths. The difficulty lies in the computational complexity required to find these alignments. To address this problem, we propose an efficient algorithm named reach based on the A* search algorithm. The core components of the proposal are the use of a partial reachability graph for faster execution of process models for alignment computation and a set of optimization techniques for reducing the number of states explored by the A* algorithm. These improve performance by both reducing the required computation time per state and the number of states to process respectively. To evaluate the performance and scalability, we conducted tests using 227 pairs of logs and models, comparing the results obtained with those from 10 state-of-the-art approaches. Results show that reach outperforms the other proposals in runtimes, and even aligns logs and models that no other algorithm is able to align. 1. Introduction Companies need to automate and digitalize their processes to become more competitive, cut costs and avoid delays in their operations. In this context, a process is a set of activities with coordination requirements among them, which are executed by a set of resources to achieve an objective (Carmona, van Dongen, Solti, & Weidlich,2018). These processes are described by means of process models that clearly detail the activities to be performed as well as when and which resources will execute them. However, in practice the execution of the processes differs from the process models that were designed to automate the process, making it difficult to understand what is happening in the process and to take decisions. Process mining is an emerging discipline whose aim is to get information about what is really happening in the execution of a process, giving an understanding of the real processes that take place in an organization (van der Aalst et al.,2012). To achieve this, process mining techniques use an event log as input. An event log is a set of traces, each containing a sequence of events. Each event has information about the activity that has been executed, the timestamp of that activity, the trace identifier, the resource that has performed the activity, and, optionally, contextual information about the event execution. With this in mind, three fundamental descriptive process mining techniques have emerged: (i) process discovery, which aims to retrieve the underlying ∗Corresponding author. E-mail addresses: [email protected] (J. Casas-Ramos), [email protected] (M. Mucientes), [email protected] (M. Lama). process model that represents the behavior recorded in an event log; (ii) conformance checking, where a process model is compared with a log of the same process to analyze and quantify the deviations between the modeled and the observed behavior, as recorded in the log; and (iii) process enhancement, where a process model is modified and improved based on the information from the log. In this paper, we focus on conformance checking, particularly in the computation of the alignments between the process model and the log traces. Several conformance checking approaches have appeared in recent years. These approaches can be classified in token replay-based (Berti & van der Aalst,2021;Rozinat & Van der Aalst,2008) and alignmentbased (Adriansyah,2014;de Leoni & van der Aalst,2013;de Leoni, Lanciano, & Marrella,2018;de Leoni & Marrella,2017;Lu, Fahland, & van der Aalst,2015;Taymouri & Carmona,2016;van Dongen, 2018). The former approaches try to execute all events on the model, registering all states of the process model and modifying the execution state when it is needed for a proper event execution on the model — possibly reporting errors that would be false positives. Alignmentbased approaches are widely regarded as the most effective solutions for conformance checking, as they return much more accurate results, pinpointing the optimal model deviations. These methods align each trace with the closest path allowed by the model, even if they do https://doi.org/10.1016/j.eswa.2023.122467 Received 3 January 2023; Received in revised form 27 October 2023; Accepted 4 November 2023 Expert Systems With Applications 241 (2024) 122467 2 J. Casas-Ramos et al. not match perfectly. Some of these techniques (Adriansyah,2014; de Leoni & van der Aalst,2013;de Leoni et al.,2018;Lu et al., 2015;Taymouri & Carmona,2016;van Dongen,2018) are based on the A* algorithm (Hart, Nilsson, & Raphael,1968), a graph search algorithm that uses a heuristic to guide the search while ensuring optimal results. However, alignment-based approaches encounter challenges when dealing with intricate models and extensive logs, resulting in extended processing times and even not being able to compute some alignments. Several approaches tackle this problem by relaxing restrictions and returning non-optimal alignments (Leemans, Fahland, & van der Aalst,2018;Reißner, Armas-Cervantes, Conforti, et al.,2020; Reißner, Armas-Cervantes, & La Rosa,2020;Reißner, Conforti, Dumas, La Rosa, & Armas-Cervantes,2017), which might not be suitable for applications where an exact description of the differences between the process model and the log is required. In this paper, we introduce reach, an extension of the A* algorithm designed to compute optimal alignments efficiently. It incorporates a series of optimizations to enhance performance and scalability. They significantly reduce the number of states that need to be explored to reach the optimal solution and the processing time spent on each state. The main contributions of the proposal are: •A new heuristic that quickly finds required activities – activities that must be executed to reach the end of the model – and compares them with the remaining trace in order to provide more accurate estimates and speed up the algorithm without losing its optimality. •Techniques for reducing the number of states explored by the A* algorithm. These include optimizations that check and force the execution of required moves by exploring the rest of the trace and the model. Furthermore, a greedy algorithm that returns a suboptimal alignment is used as an upper bound of cost for the main algorithm. These optimizations filter states that will not lead to the optimal alignment, as another state will lead to an alignment of less cost. This also removes all neighbors generated by the ignored states recursively, greatly reducing the computational cost. •Efficient execution of process models for alignment computation using a partial and incremental reachability graph. It works by saving information about how process models run for alignment computation. It prevents performing repeated model operations at each step of the A* algorithm. The remainder of this article is organized as follows. Section 2 studies and compares previous work. Next, Section 3defines all the required concepts on which this work is based. The algorithm is described in detail in Section 4. Section 5describes the experiments and discusses the results, compared to the current state of the art. Finally, the conclusions and the future work are presented in Section 6. 2. Related work Conformance checking is a very active field in process mining. One of its most popular approaches is token-based replay over Petri nets (Berti & van der Aalst,2021;Rozinat & Van der Aalst,2008). It involves executing each event of the Petri net as they appear in the trace. If an event cannot be executed, the tokens required to execute it are inserted and counted. Once the full trace has been replayed, all the remaining tokens that are not in a sink place are counted. The fitness metric, which is a measure of conformance between the log and the model, is computed based on these counts. Unfortunately, this technique is less accurate than alignment-based approaches, as it assumes the model is always correct. Furthermore, the provided diagnostics are hard to understand for the end-user, as they are tied to the Petri net model representation and replay. In van den Broucke, Munoz-Gama, Carmona, Baesens, and Vanthienen (2014) they propose a decomposition-based extension of token-based replay that is more efficient, but it shares the aforementioned disadvantages. A recent development in this field is stochastic conformance checking (Leemans, van der Aalst, Brockhoff, & Polyvyanyy,2021), which involves comparing event logs and process models while recognizing that logs represent only a subset of possible behaviors. The major disadvantage of the approach is that stochastic process model discovery is a necessary prerequisite for applying this technique. It is a computationally expensive task that has much higher memory requirements than traditional process discovery techniques. The algorithm depends on an input parameter (probability mass) that makes the returned metrics more stable when it is increased. However, the runtime of the algorithm increases very quickly with respect to this parameter for most datasets. This is even worse if the model presents concurrency and looping behavior. Alignment-based techniques (Adriansyah,2014) can identify and explicitly list all discrepancies, enabling the detection of optimal trace executions through the model. These techniques still rely internally on the execution of process models, but they can find the path through the model with the least number of discrepancies possible. There are also techniques, like behavioral alignments (Garcia-Banuelos, van Beest, Dumas, Rosa, & Mertens,2018), that provide textual summaries of conformance without actually computing alignments. These descriptions might be easier for end-users, but they are not as useful as alignments. Alignments link event data to the model, and can be used for post-processing tasks such as fitness calculation, performance analysis, model repair, or prediction tasks. Alignments are considered the standard for conformance checking. In order to find the optimal alignments, most approaches use a pathfinding algorithm like A* for aligning the trace and the model. A* requires a heuristic, which defines the way to explore the state space of the problem. On the one hand, simple heuristics lead to faster exploration but more explored states (Adriansyah,2014;de Leoni et al., 2018;Lu et al.,2015), which makes computing alignments for medium or large models impractical without other states reduction techniques. On the other hand, complex heuristics focus on reducing the number of states at the cost of more processing time per state. An illustrative instance of a complex heuristic is rooted in Integer Linear Programming (ILP), utilizing constraints extracted from the model, the remaining trace, and an optimization cost function. Given a state (marking in the model and remaining trace events), the ILP solver is capable of determining the minimum cost that a solution may have, so it is suitable as a heuristic for A* (de Leoni & van der Aalst,2013;Taymouri & Carmona,2016;van Dongen,2018). However, a drawback of complex heuristics is that the computational cost for each discovered state often surpasses the efficiency gained through state reduction. de Leoni and Marrella (2017) convert the alignment problem to the Planning Domain Definition Language and use an external automated planner to compute the alignments. Their algorithm can modify the planning framework for alignment computation. Nevertheless, their approach depends on the blind A* heuristic, which guarantees optimality but significantly underestimates the remaining cost. Considering the exponential complexity of optimal algorithms, researchers have introduced non-optimal techniques for computing alignments. These methods were proposed as a compromise between the quality of the results and the computational cost. These techniques do not guarantee that the alignment with the least cost will be found, but they provide approximations with a quality that depends on the model and the log. One such technique is (Taymouri & Carmona, 2018), utilizing an evolutionary algorithm to offer improved alignment approximations, albeit without the assurance of discovering all optimal alignments. Another approach that uses local search to reduce processing time and memory usage is (Taymouri & Carmona,2020), with the added limitation of only being able to return one of the alignments. It is worth mentioning (van Dongen, Carmona, Chatain, & Taymouri,2017), Expert Systems With Applications 241 (2024) 122467 3 J. Casas-Ramos et al. which also performs an iterative search in order to find a possibly non-optimal alignment. A prevalent method for non-optimal alignments involves decomposing models into smaller, more computationally efficient parts and aggregating partial results, even though this may not always result in optimal alignments (Munoz-Gama, Carmona, & van der Aalst,2014; Sani, van Zelst, & van der Aalst,2020;van der Aalst,2013). Alternatively, a recomposing technique that is capable of obtaining optimal alignments from the partial pseudo-alignments was developed in Lee, Verbeek, Munoz-Gama, van der Aalst, and Sepúlveda (2018), but it was only executed with manual decompositions of models. Another decomposing optimal technique is described in Munoz-Gama, Carmona, and van der Aalst (2013), but it is limited to sound and safe workflow nets. Finally, another type of non-optimal technique is based on building automata capable of aligning the log and the model (Leemans et al.,2018;Reißner, Armas-Cervantes, Conforti, et al.,2020;Reißner, Armas-Cervantes, & La Rosa,2020;Reißner et al.,2017). These approaches, while non-optimal, give good approximations of the optimal alignments for most cases. The method in Leemans et al. (2018) splits the activities into multiple subsets to handle very complex models with many activities. Consequently, it increases performance on models with lots of activities at the expense of lower cost accuracy of the resulting alignments. The state of the art still struggles when facing complex models and logs, leading to large runtimes, and even not being able to compute some alignments. To address this issue, several proposals have relaxed restrictions and returned non-optimal alignments. However, in this paper, we present an A*-based algorithm that increases performance while still providing optimal alignments. This algorithm introduces several techniques for reducing the number of states of the search space to be explored: a new heuristics to better guide the states to explore, a greedy algorithm to find an upper cost bound of the optimal alignment, and two optimizations that check each state to force certain mandatory moves instead of generating all possible neighboring states. Furthermore, our approach introduces an efficient way to execute process models that relies on a partial and incremental reachability graph in order to speed up the computation required for each state. These techniques speed up computation and mitigate the scalability problem currently present in the state-of-the-art proposals. 3. Preliminaries To perform conformance checking a log and a process model are needed. Logs consist of events, organized into traces, with each trace representing the execution of the associated process model. Every event must have the execution timestamp, the trace identifier that groups the events of the same process execution, and the executed activity. Table 1 shows an example of a log with two traces from an e-learning platform, where each row of the table is an event. For the sake of simplicity, we define traces as a sequence of executed activities, sorted by the execution timestamps of each event or in the order of appearance in the log in case of ties. Definition 1 (Trace).A trace 𝜎=⟨𝑎1,…, 𝑎𝑛⟩is a sequence of activities 𝑎𝑖extracted from events that share the case identifier. Each trace or case contains activities belonging to the same process execution, which are ordered by the execution timestamp of their event. Note that if two activities have the same execution timestamp, they are sorted by the order in which they have been registered. The ++ operator concatenates two sequences. Given a trace 𝜎, the notation 𝜎[𝑖∶] refers to the subsequence from position 𝑖(zero-indexed, inclusive) to the end of the sequence. Table 1 Example of a log corresponding to an e-learning process. A gray font highlights the events of the trace Case234. Timestamp Trace ID Activity 2021-09-01 22:16:29 Case234 Enroll 2021-09-03 16:12:24 Case675 Enroll 2021-10-04 08:09:56 Case234 Class 2021-10-19 00:00:13 Case234 Class 2021-11-01 04:10:07 Case675 Class 2021-11-15 02:09:48 Case234 Test 2021-11-29 13:53:30 Case675 Test 2021-12-13 07:24:41 Case675 Class 2022-01-17 23:03:31 Case675 Exam 2022-01-19 06:42:33 Case234 Exam ... In Table 1, traces refer to the actions of a student in a virtual course. To track the actions of an individual student, we can extract a trace by filtering the recorded events (log table rows) with the same trace identifier. A student executed the activity in the column ‘‘Activity’’ at the moment indicated by the column ‘‘Timestamp’’. For instance, the trace identified as Case234 documents the sequence of activities executed by the student: 〈Enroll, Class, Class, Test, Exam〉. Definition 2 (Log).An event log 𝐿=[𝜎1,…, 𝜎𝑛]is a multiset of traces 𝜎𝑖. Each trace corresponds to one execution of the process. A process model describes the allowed behavior by giving activities a structure with initial and final states. In the realm of conformance checking, Petri nets are the dominant technique for representing process models. Definition 3 (Petri Net).A Petri net is a tuple 𝑃 𝑁 = (𝑃 , 𝑇 , 𝐹 , 𝜆)where •𝑃is the set of places. •𝑇is the set of transitions. These may contain silent transitions 𝜏, which are related to the model structure, and non-silent transitions, which are related to the execution of activities. 𝑇𝑠denotes the set of silent transitions and 𝑇𝑛𝑠 =𝑇⧵𝑇𝑠is the set of non-silent transitions. •𝑃∩𝑇= ∅. •𝐹∈ (𝑃×𝑇)∪(𝑇×𝑃)is the set of directed arcs that connect places to transitions and vice versa. •𝜆∶𝑇𝑛𝑠 ←←→ 𝐴maps every non-silent transition to a label — an activity that may appear in the log. Multiple transitions can have the same label, as our algorithm supports handling duplicate activities in the process model. We also use 𝜆𝑟to perform the reverse mapping — map an activity to the set of non-silent transitions with the given label. Petri nets are directed bipartite graphs where nodes are places and transitions. We denote ∙𝑡as the input places (∙𝑡= {𝑝∈𝑃∣ (𝑝, 𝑡) ∈ 𝐹}) and 𝑡∙as the output places (𝑡∙= {𝑝∈𝑃∣ (𝑡, 𝑝) ∈ 𝐹}) of a transition 𝑡∈𝑇. These are the places directly linked by arcs to and from transition 𝑡, respectively. The same operator can be applied to places to retrieve the connected transitions. In order to execute Petri nets, it is necessary to introduce the concepts of token and marking. A place 𝑝∈𝑃can store any number of tokens in the marking 𝑀, as given by the function 𝑡𝑜𝑘𝑒𝑛𝑠(𝑀, 𝑝). Hence, we define a marking as a multiset of places that represents the number of tokens in each place. Definition 4 (Marking).Let 𝑃 𝑁 = (𝑃 , 𝑇 , 𝐹 , 𝜆)be a Petri net and let  be the power multiset function. A marking 𝑀∈(𝑃)of that Petri net is a multiset of places. This multiset represents the places that contain tokens and the number of tokens they contain. 𝑀0∈(𝑃)is the initial marking of the Petri net. Expert Systems With Applications 241 (2024) 122467 4 J. Casas-Ramos et al. Fig. 1. Example of a Petri/workflow net that models a very simplified process of an e-learning course. Places are represented as circles and transitions as rectangles — a silent transition is shown as a thin black rectangle. The filled circles inside some places indicate the number of tokens they contain. The end place is shown with a circumference inside. Enabled transitions are shown with green borders. In this process, students can enroll in the course and, once enrolled, they can attend any number of classes and/or take tests, performing at least one of those activities. Lastly, a final exam is required to complete the course. In this example, the Enroll transition is executed, leading the Petri net from its initial marking (a) to the next marking (b). Due to the execution of Enroll, a token is consumed in the initial place, and one is produced in its output place, enabling the Class and Test transitions. A complete process execution for this model would be 〈Enroll, Class, Exam〉. During the execution of Petri nets, tokens are added to and removed from places. Specifically, at the start of the process, the Petri net is initialized with the tokens of the initial marking 𝑀0. A transition 𝑡∈𝑇 is enabled at a marking 𝑀iff ∀𝑝∈∙𝑡∶𝑡𝑜𝑘𝑒𝑛𝑠(𝑀, 𝑝)>0. This condition means that the transition is enabled when there is at least one token available for consumption in each place connected to the transition through an input arc. To execute that transition 𝑡, all input places 𝑝∈∙𝑡 consume one token; and all output places 𝑝∈𝑡∙receive a token. When a marking including tokens in a place marked as final is reached, the process is considered as finished. Fig. 1(a) shows an example of a Petri net. Workflow nets (van der Aalst,1996) are a class of Petri nets focused on modeling processes: they have a single input place and a single output place, and all transitions are in a path from the start to the end places. Definition 5 (Workflow Net).Let 𝑃 𝑁 = (𝑃 , 𝑇 , 𝐹 , 𝜆)be a Petri net. It is a workflow net if and only if: •There is a single input place 𝑝𝑖∈𝑃.∙𝑝𝑖= ∅. •There is a single output place 𝑝𝑜∈𝑃.𝑝𝑜∙= ∅. •Adding a transition 𝑡with ∙𝑡=𝑝𝑜and 𝑡∙=𝑝𝑖, would cause the Petri net to become a strongly connected graph. A workflow net has proper completion if for any reachable marking 𝑀by executing any sequence of enabled transitions ⟨𝑡0,…, 𝑡𝑛⟩, 𝑡𝑜𝑘𝑒𝑛𝑠(𝑀, 𝑝𝑜)>0⟹𝑀= [𝑝𝑜], i.e., any sequence of fired transitions that reach the end will only have one token in the output place. In practice, process executions frequently deviate from the intended process models. For instance, in the context of the virtual course from Fig. 1(a), students are expected to attend classes before taking the final exam. However, in reality, some students may choose to skip these lessons and still manage to complete the course, even though this behavior is not accounted for in the designed process model. This is shown in Fig. 2. Alignments provide the necessary information to identify deviations of traces from the process model. An alignment can be computed for each trace given a process model, as a trace is an execution of the model. An alignment defines a path that traverses both the trace and the process model from start to end. It provides detailed conformance information useful for multiple tasks like model repair, auditing and prediction, even if the trace and the model do not match perfectly. This is achieved by associating the executed activities in the trace with the transitions in the model. Alignments are built from legal moves, which consume an activity of the trace and execute a non-silent transition with a matching label in the process model, or perform an asynchronous move by only executing a transition on the model (model move) or advancing on the trace (log move). Definition 6 (Legal Move).Let 𝑀be the current marking in the model, let 𝜎be the trace to align, and let 𝑖be the first index – zero-based – of the trace that still needs to be aligned so that 𝜎[𝑖]is the next activity to align. Furthermore, let 𝑀[𝑡⟩denote that marking 𝑀enables transition 𝑡. A legal move is one of the following. •A synchronous move (𝜎[𝑖], 𝑡)is available iff 𝑀[𝑡⟩and 𝜆(𝑡) = 𝜎[𝑖]. This move will update 𝑖with the next index of the trace. It will also update 𝑀by executing the transition 𝑡, i.e., 𝑀−∙𝑡+𝑡∙. Note that if the end of the trace was reached (𝑖=|𝜎|), no more synchronous moves can be made. •A log move (𝜎[𝑖],>>) is available iff 𝑖 < |𝜎|. This will increase 𝑖 by one, advancing on the trace. •A model move (>>, 𝑡) is available iff 𝑀[𝑡⟩. As a result of this move, 𝑀is updated to 𝑀−∙𝑡+𝑡∙. If 𝑡is a silent transition 𝜏, the move is called a silent move. Log and model moves are referred to as asynchronous moves. Definition 7 (Alignment).An alignment 𝛾=⟨𝛾1,…, 𝛾𝑛⟩is a sequence of legal moves (Definition 6). A complete alignment’s moves 𝛾1,…, 𝛾𝑛 advance through the model and the trace. Alignments start from the initial marking of the model and the start of the trace and reach the end of the model and the end of the trace. Definition 8 (Cost Function, Alignment Cost, Optimal Alignment).A cost function 𝐶∶ (𝐴∪ {≫}) × (𝑇∪ {≫}) →(0,∞)assigns a cost to each possible legal move, where 𝐴is the set of activities in the log and 𝑇 is the set of transitions in the process model. Generally, the cost for synchronous moves is lower than the cost for asynchronous moves. Each valid alignment is assigned a cost 𝑐𝛾=𝑐𝛾1+⋯+𝑐𝛾𝑛which is the sum of all the costs of its moves. Hence, the optimal alignment for a given trace and model is the one with the minimum cost. There may be several different optimal alignments. Fig. 3 shows two alignments for the model depicted in Fig. 1 alongside a trace. When conducting conformance checking, it is frequently beneficial to provide quality metrics. These metrics offer a concise summary of the results, condensing all calculated alignments into a single, easily interpretable value. One of the most well-established metrics is fitness. It gives an idea of the similarity between the log and the model based on the cost of the computed alignment. Fitness can be calculated for individual alignments or for the entire log. All optimal alignments of a trace have the same fitness as it is derived from the cost of the alignment. Definition 9 (Alignment Fitness).Let 𝛾be an alignment between the trace 𝜎and the model 𝑀, with cost 𝑐𝛾(Definition 8). The fitness for that alignment is defined as: 𝑓𝛾= 1 − 𝑐𝛾 𝜎𝑐+𝑀𝑐 where 𝜎𝑐is the sum of costs for the asynchronous log moves for all of the trace activities and 𝑀𝑐is the sum of costs of the asynchronous model moves required for the minimum cost path through the model or, in other words, the cost of the optimal alignment of the empty trace and the model. Fitness indicates how much the trace matches the model, quantifying all differences. Thus, it compares the cost of the given alignment Expert Systems With Applications 241 (2024) 122467 5 J. Casas-Ramos et al. Fig. 2. (a) The process model from our running example and (b) the real process model discovered from the event log. Fig. 3. Two optimal alignments using the default cost function for the trace Enroll, Exam, Test and the model in Fig. 1. Each column represents a move, indicating the activity of the trace in the first row and the executed transition of the model in the second row. Moves are executed from left to right to take the trace and the model from the initial state to the end. >> is used for asynchronous moves indicating that no action is taken. A move in the model uses >> in the trace row to show that only the transition in the model is executed, and a move in the log uses >> in the model row. These alignments show the user how there was a skipped required activity that could have been either Class or Test, and the executed activity Test should not have been executed after the final Exam was taken, according to the model. The cost for each of these alignments, assuming a cost function that assigns a cost of 1 to asynchronous moves and 0 to synchronous moves, is 2in both cases, and their fitness is 𝑓= 1 − 2 3+3 = 0. Û 6. Fig. 4. High-level diagram of reach algorithms and their interactions. Continuous arrows show the control flow of the algorithm, while discontinuous ones show the usage of another algorithm, returning the control flow to the caller. with the cost of the alignment with only asynchronous moves: it first traverses the whole model via its shortest path adding the executed transitions as model moves, and then adds log moves for the whole trace. A fitness of 1 (perfect fitness) shows that the trace was executed correctly for the model (fitting trace), while lower fitness values indicate that discrepancies between the trace and the model were found. To calculate fitness for an entire log, the fitness values of individual traces are averaged. This gives an idea at a glance of how well the log conforms to the process model. Definition 10 (Log Fitness).Let 𝛾𝐿=[𝛾1,…,𝛾𝑛] be a multiset of optimal alignments between each trace of the log 𝐿=[𝜎1,…, 𝜎𝑛]and the model 𝑀. The fitness of the log (𝑓) is the average fitness of the alignments: 𝑓=(∑𝑛 𝑖=1 𝑓𝛾𝑖)∕𝑛, where 𝑓𝛾𝑖is the fitness of the alignment 𝛾𝑖(Definition 9). 4. Conformance checking based on alignments The goal of the reach algorithm is to find the best alignment or all the best alignments for a model 𝑃 𝑁 and each trace in a log 𝐿. Fig. 4 shows an overview diagram containing the algorithms detailed in this section and how they relate to each other. Algorithm 1receives the inputs and runs the preprocessing steps of Algorithms 8and 9. Subsequently, the main search loop commences, iteratively invoking Algorithm 2to create neighbors of previously discovered states. Algorithms 3,6and 7are optimizations applied each time a neighbor is generated. Some algorithms depend on the partial reachability graph for the execution of operations on the model, as indicated by the discontinuous arrows of Fig. 4. Prior to initiating the processing of each log trace, the algorithm performs some preprocessing tasks. Firstly, once per model, it computes the shortest path through the model following the cost function (Algorithm 1:3). While this is not required to find the optimal alignments, it is done to properly compute the fitness metric. Once each optimal alignment is computed, its fitness can be quickly calculated following Definition 9. Secondly, the log is simplified, detecting and counting duplicate traces, so that only one of those is processed. This task is executed only once per log (Algorithm 1:4). Lastly, an optimization for reducing the number of states generated that will be explained in Algorithm 8is initialized. A* is a complete and optimal search algorithm (Hart et al.,1968). This implies that, if the problem has a solution, the algorithm will discover it – complete search algorithm –, and it will always discover the optimal solution if it exists. It stands out for its optimal efficiency with the main drawback being its exponential space complexity. It requires an admissible and consistent heuristic function to select the best path to pursue while guaranteeing optimality. This algorithm fits very well the alignment problem. A directed graph where the nodes are partial alignments is defined, for which each available legal move (Definition 6) generates a new connected neighbor. The start node is the empty partial alignment, which contains no moves. Within this state graph, the algorithm needs to find the minimum cost path between the start and goal nodes, where a goal node is a complete alignment — an alignment that reaches the end of the model and the end of the trace. This is the kind of problem that A* solves with optimal efficiency, meaning that no other optimal algorithm would find the solution expanding fewer nodes if provided the same information. The proposed conformance checking approach (Algorithm 1) is grounded in the A* algorithm (Adriansyah,2014), a method for navigating the state space to identify the optimal alignment. Each state is a (partially) built alignment, meaning an alignment whose sequence of legal moves begins with the initial marking and the start of the trace. Concretely, states are defined as 𝑆=(𝑀,𝑖,𝛾,𝑐,ℎ), where: •𝑀represents the state of execution of the process model. For Petri nets, it is the current marking. Expert Systems With Applications 241 (2024) 122467 6 J. Casas-Ramos et al. Algorithm 1 reach core algorithm. Input: The process model 𝑃 𝑁, the log 𝐿to align to 𝑃 𝑁, and a boolean 𝑜𝑝𝑡 that is true to return all optimal alignments, otherwise one of them is given. Output: Optimal alignments. 1: procedure Execute(𝑃 𝑁,𝐿,𝑜𝑝𝑡) 2: 𝑟𝑒𝑠𝑢𝑙𝑡𝑠 ←∅ 3: 𝑃 𝑁.𝑙𝑒𝑎𝑠𝑡𝐶𝑜𝑠𝑡 ←ShortestPath(𝑃 𝑁)⊳Needed for computing fitness 4: 𝐿←SimplifyLog(𝐿) 5: LessStatesModelInit(𝑃 𝑁)⊳Alg. 8 6: for all 𝜎∈𝐿do 7: 𝑎𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠 ←Align(𝑃 𝑁,𝜎,𝑜𝑝𝑡)⊳Align the trace 8: 𝑟𝑒𝑠𝑢𝑙𝑡𝑠 ←Aggregate(𝑟𝑒𝑠𝑢𝑙𝑡𝑠,𝑎𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠)⊳Aggregate the results 9: end for 10: return 𝑟𝑒𝑠𝑢𝑙𝑡𝑠 11: procedure ShortestPath(𝑃 𝑁) 12: 𝑆←Align(𝑃 𝑁,EmptyTrace,𝑓𝑎𝑙𝑠𝑒)[0] ⊳Align the empty trace, returning the final state 13: return 𝑆.𝑐 ⊳ Return the cost 𝑐of the optimal alignment 14: procedure Align(𝑃 𝑁,𝜎,𝑜𝑝𝑡) 15: 𝑔𝑟𝑒𝑒𝑑𝑦𝐴𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡 ←AlignGreedy(𝑃 𝑁,𝜎)⊳Alg. 9 16: 𝑚𝑎𝑥𝐶𝑜𝑠𝑡 ←𝑔𝑟𝑒𝑒𝑑𝑦𝐴𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡.𝑐 ⊳ The cost of the greedy alignment limits the optimal cost 17: 𝑆←InitialState(𝑃 𝑁,𝜎) 18: 𝑜𝑝𝑒𝑛 ←∅⊳Priority queue that stores states 19: Add(𝑜𝑝𝑒𝑛, 𝑆)⊳Insert state, sorted by 𝑆.𝑐 +𝑆.ℎ 20: 𝑎𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠 ←∅⊳Found optimal alignments 21: while 𝑎𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠 = ∅ || (𝑜𝑝𝑡 && 𝑆.𝑐 +𝑆.ℎ < 𝑚𝑖𝑛({𝑆.𝑐 ∣𝑆∈𝑎𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠} ∪ {+𝑖𝑛𝑓}) + 𝑚𝑖𝑛_𝑐)do 22: 𝑆←Poll(𝑜𝑝𝑒𝑛)⊳Extract the next best state 23: if ¬IsFinal(𝑆)then 24: AddNeighbors(𝜎, 𝑆, 𝑜𝑝𝑒𝑛, 𝑚𝑎𝑥𝐶𝑜𝑠𝑡)⊳Alg. 2 25: else 26: 𝑎𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠 ←𝑎𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠 ∪𝑆 ⊳ Record the final state of the optimal alignment 27: end while 28: return 𝑎𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠 •𝑖is the zero-based index of the trace from which the remaining activities are not yet aligned. •𝛾=⟨𝛾0,…, 𝛾𝑖−1⟩is the partial or complete alignment, consisting of the sequence of legal moves taken. •𝑐is the current cost, which is the sum of the costs of the movements made. •ℎis the heuristic value, i.e., an optimistic estimate of the remaining cost to complete the alignment. Before executing the main algorithm, a greedy search is performed (Algorithm 1:15-16). If it finds an alignment, it is used as a maximum cost limit to avoid generating unnecessary states and speed up the algorithm. The greedy search will be discussed further in Section 4.2.2. The algorithm begins with the initial state (Algorithm 1:17), which is an alignment without any move, at the initial marking of the model and at the first event of the trace, with cost 0. States are kept in a priority queue that sorts states by increasing order of 𝑆.𝑐+𝑆.ℎ (Algorithm 1:19), where 𝑆.𝑐 is the cost and 𝑆.ℎ is the heuristic. 𝑆.𝑐 +𝑆.ℎ is used to guide the exploration of A*, ensuring optimal results. The main loop (Algorithm 1:21) explores each state in the order given by the priority queue while a solution is not found. The algorithm can also retrieve the set of all optimal alignments by iterating while 𝑆.𝑐 +𝑆.ℎ is lower than the cost of any found solution (𝑚𝑖𝑛({𝑆.𝑐 ∣𝑆∈𝑎𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠} ∪ {+𝑖𝑛𝑓})) plus the minimum cost of an asynchronous move (𝑚𝑖𝑛_𝑐) — as A* requires synchronous moves to have a negligible cost strictly greater than 0. At each step, a state is removed from the priority queue (Algorithm 1:22). If the given state is not final, the algorithm creates the neighbors of that state by using all the feasible legal moves (Definition 6). For each neighbor, it is necessary to update the process model state, the trace progress, the cost, and the heuristic. Otherwise, if the state is final, it is an optimal alignment and it is added to the alignments set (Algorithm 1:23-26). The AddNeighbors function detailed in Algorithm 2adds all the children states from a parent based on the available legal moves — called from Algorithm 1:24. Given the set of enabled transitions of the parent state (Algorithm 2:2), and the next trace activity of the parent state (Algorithm 2:4), neighbors are created by executing all available legal moves. Specifically, one neighboring state is generated for each move: •A synchronous move for each enabled transition of the model that shares the label with the next activity of the trace – note that model transitions can have duplicate labels – (Algorithm 2:6-7). •An asynchronous movement in the log if the end of the trace is not yet reached (Algorithm 2:10). •As many asynchronous movements in the model as transitions are enabled from the current marking of the model (Algorithm 2:12-13). The conditions at Algorithm 2:9and Algorithm 2:11 are optimizations. These optimizations reduce the exploration of unnecessary states by skipping certain asynchronous moves in the log and the model when specific conditions are met (Section 4.2.2). For each move, a new neighboring state 𝑆must be created and 𝑆.𝛾 must be updated, the sequence of legal moves (Algorithm 2:15-22). Each call to AddMove defines the new state that can advance to the next activity on the trace, and/or execute a transition in the model, depending on the kind of move (Algorithm 2:23-26). The cost and heuristic values are then updated for the new state, just before inserting it in the priority queue, where it will be sorted by the sum of both values (Algorithm 2:27-31). The condition at Algorithm 2:30 avoids inserting in the open queue states that are not capable of reaching the optimal alignment, as they match a previously discovered state – equal 𝑆.𝑀 and 𝑆.𝑖 values – with Expert Systems With Applications 241 (2024) 122467 7 J. Casas-Ramos et al. Algorithm 2 Neighbor generation. Input: A current or parent state 𝑆and a priority queue 𝑜𝑝𝑒𝑛 for the new states to be inserted into. Output: None, it adds neighbors to 𝑜𝑝𝑒𝑛. 1: procedure AddNeighbors(𝜎,𝑆,𝑜𝑝𝑒𝑛,𝑚𝑎𝑥𝐶𝑜𝑠𝑡) 2: 𝑒𝑡𝑟𝑠 ←EnabledTransitions(𝑆.𝑀)⊳Alg. 4: enabled transitions from the current state 3: if 𝑆.𝑖 < |𝜎|then ⊳If the end of 𝜎was not reached yet 4: 𝑎𝑐𝑡𝑖𝑣𝑖𝑡𝑦 ←𝜎[𝑆.𝑖]⊳The next activity recorded in the trace 5: 𝑡𝑟𝑠 ←𝜆𝑟(𝑎𝑐𝑡𝑖𝑣𝑖𝑡𝑦)⊳An activity may map to multiple model transitions 6: for all 𝑡𝑟 ∈𝑡𝑟𝑠 ∩𝑒𝑡𝑟𝑠 do 7: AddMove(𝜎,𝑆,𝑜𝑝𝑒𝑛,Sync,𝑡𝑟,𝑚𝑎𝑥𝐶𝑜𝑠𝑡)⊳Generate synchronous movements 8: end for 9: if ¬LessStatesLog(𝜎, 𝑆)then ⊳Alg. 6 10: AddMove(𝜎,𝑆,𝑜𝑝𝑒𝑛,Log,𝑎𝑐𝑡𝑖𝑣𝑖𝑡𝑦,𝑚𝑎𝑥𝐶𝑜𝑠𝑡)⊳Generate asynchronous log movements 11: if ¬LessStatesModel(𝜎, 𝑆)then ⊳Alg. 7 12: for all 𝑡𝑟 ∈𝑒𝑡𝑟𝑠 do 13: AddMove(𝜎,𝑆,𝑜𝑝𝑒𝑛,Model,𝑡𝑟,𝑚𝑎𝑥𝐶𝑜𝑠𝑡)⊳Generate asynchronous model movements 14: end for 15: procedure AddMove(𝜎,𝑆𝑝𝑎𝑟𝑒𝑛𝑡,𝑜𝑝𝑒𝑛,𝑡𝑦𝑝𝑒,𝑡𝑟,𝑚𝑎𝑥𝐶𝑜𝑠𝑡) 16: 𝑆←NewState() 17: if 𝑡𝑦𝑝𝑒 =Sync then ⊳Record the performed legal move in 𝛾for the current state 18: 𝑆.𝛾 ←𝑆𝑝𝑎𝑟𝑒𝑛𝑡.𝛾 ++ (𝜆(𝑡𝑟), 𝑡𝑟) 19: if 𝑡𝑦𝑝𝑒 =Log then 20: 𝑆.𝛾 ←𝑆𝑝𝑎𝑟𝑒𝑛𝑡.𝛾 ++ (𝑡𝑟,>>) 21: if 𝑡𝑦𝑝𝑒 =Model then 22: 𝑆.𝛾 ←𝑆𝑝𝑎𝑟𝑒𝑛𝑡.𝛾 ++ (>>, 𝑡𝑟) 23: if 𝑡𝑦𝑝𝑒 ≠Model then ⊳Synchronous or log movements advance on the trace 24: 𝑆.𝑖 ←𝑆𝑝𝑎𝑟𝑒𝑛𝑡.𝑖 + 1 25: if 𝑡𝑦𝑝𝑒 ≠Log then ⊳Synchronous or model movements advance on the model 26: 𝑆.𝑀 ←ExecuteTransition(𝑆𝑝𝑎𝑟𝑒𝑛𝑡.𝑀, 𝑡𝑟)⊳Alg. 5 27: if 𝑡𝑦𝑝𝑒 ≠Sync then 𝑆.𝑐 ←𝑆𝑝𝑎𝑟𝑒𝑛𝑡.𝑐 + 1 ⊳Update cost and heuristic for the new state 28: else 𝑆.𝑐 ←𝑆𝑝𝑎𝑟𝑒𝑛𝑡.𝑐 +𝑒𝑝𝑠𝑖𝑙𝑜𝑛 29: 𝑆.ℎ =Heuristic(𝜎, 𝑆)⊳Alg. 3 30: if ShouldAdd(𝑆,𝑜𝑝𝑒𝑛,𝑚𝑎𝑥𝐶𝑜𝑠𝑡)then ⊳Add the state to the queue 31: Add(𝑜𝑝𝑒𝑛, 𝑆) 32: return S a higher or equal 𝑆.𝑐, or they exceed the 𝑆.𝑐+𝑆.ℎ threshold established by the greedy algorithm. To achieve optimality, the A* algorithm employed in reach must meet three conditions. First, the cost change when advancing to a neighbor must be strictly positive. To satisfy this requirement, the cost of synchronous and silent moves is always a negligible value greater than 0 (𝑒𝑝𝑠𝑖𝑙𝑜𝑛). A standard cost of 1 is applied to all other asynchronous moves. Second, the heuristic must be admissible, meaning that it must return an underestimate of the remaining cost to the closest goal node in terms of cost. In third place, the heuristic must also be consistent – also called monotone – in order to provide optimal results. A consistent heuristic returns an estimate for any node that is lower or equal to the least cost of advancing to a neighbor plus its heuristic estimate, 𝑆𝑝𝑎𝑟𝑒𝑛𝑡.ℎ ≤𝑆.𝑐 −𝑆𝑝𝑎𝑟𝑒𝑛𝑡.𝑐 +𝑆.ℎ, where 𝑆is a state successor of 𝑆𝑝𝑎𝑟𝑒𝑛𝑡. This is because using a consistent heuristic ensures that once a node is explored, it will not be reached again with a lower cost. Note that a consistent heuristic is also admissible. The admissibility and monotonicity of the proposed heuristic will be discussed in Section 4.1. 4.1. Heuristic Heuristics substantially affect the performance of the A* algorithm and, as such, are the focus of many state-of-the-art papers. We propose a new heuristic, called Model Move Required (MMR) that balances the time required to compute the heuristic —which would mean a higher processing time per state—, and the accuracy of the estimates it provides —which enables reducing the number of states that need to be explored to achieve optimality. It works by finding a subset of the required transitions – transitions that must be executed to reach the end of the model – and by comparing their labels to the remaining trace activities. Algorithm 3presents the MMR heuristic, which calculates an optimistic approximation of the cost to complete an alignment from a given state. The heuristic needs to identify a subset of the non-silent transitions that are necessary to execute from the current marking to reach a final state (Algorithm 3:2). The first step is to figure out the required transitions for the state for which the heuristic will be computed (Algorithm 3:8). Each token of that state marking is added to the queue of 𝑝𝑙𝑎𝑐𝑒𝑠 to visit (Algorithm 3:12-14). Then, the main loop starts visiting each 𝑝𝑙𝑎𝑐𝑒 of that queue until it is empty (Algorithm 3:15). Each visited 𝑝𝑙𝑎𝑐𝑒 is removed from the queue, and already visited places are skipped or otherwise marked as visited (Algorithm 3:16-19). Next, 𝑝𝑙𝑎𝑐𝑒∙is retrieved, i.e., the successor 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠 of 𝑝𝑙𝑎𝑐𝑒. If the list only contains one transition, it is registered as a required transition (Algorithm 3:20-24). All the successor places of the transition are added to the queue of 𝑝𝑙𝑎𝑐𝑒𝑠 to visit (Algorithm 3:25). Fig. 5 presents an example that illustrates the behavior of the required transitions procedure. When the queue of 𝑝𝑙𝑎𝑐𝑒𝑠 to visit is empty, the algorithm collected a subset of all the required transitions. Following the collection of the required transitions, their unique labels are compared with the remaining distinct activities in the trace to calculate the heuristic (Algorithm 3:4). For each mandatory model activity that does not appear in the remaining trace (Algorithm 3:5), the cost of the asynchronous move Expert Systems With Applications 241 (2024) 122467 8 J. Casas-Ramos et al. Algorithm 3 Model Move Required heuristic. Input: An state 𝑆. Output: The heuristic value. 1: procedure Heuristic(𝜎, 𝑆) 2: 𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑𝑇 𝑟𝑠 ←RequiredTransitions(𝑆.𝑀)⊳Subset of the required transitions (cached) 3: 𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑 ←{𝜆(𝑡) ∣ 𝑡∈𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑𝑇 𝑟𝑠}⊳Set of required unique activities of the model 4: 𝑟𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔 ←toSet(𝜎[𝑆.𝑖∶]) ⊳Set of unique activities of the trace suffix starting at 𝑆.𝑖 5: 𝑚𝑖𝑠𝑠𝑖𝑛𝑔 ←𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑 ∖𝑟𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔 ⊳ Set of required activities not found in the remaining trace 6: 𝑚𝑖𝑛𝐶𝑜𝑠𝑡𝑀𝑜𝑣𝑒𝑠 ←𝑟𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔 ∖𝑚𝑖𝑠𝑠𝑖𝑛𝑔 ⊳ Set of required extra moves, assumed synchronous 7: return |𝑚𝑖𝑠𝑠𝑖𝑛𝑔|+|𝑚𝑖𝑛𝐶𝑜𝑠𝑡𝑀𝑜𝑣𝑒𝑠|∗𝑒𝑝𝑠𝑖𝑙𝑜𝑛 ⊳ Heuristic, under the standard cost function 8: procedure RequiredTransitions(𝑀) 9: 𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑𝑇 𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠 ←∅⊳The output of this function is the set of required transitions 10: 𝑝𝑙𝑎𝑐𝑒𝑠 ←∅⊳Queue that stores places to visit 11: 𝑝𝑙𝑎𝑐𝑒𝑠𝑉 𝑖𝑠𝑖𝑡𝑒𝑑 ←∅⊳Queue that stores visited places 12: for all 𝑝𝑙𝑎𝑐𝑒 ∈TokenPlaces(𝑀)do ⊳For each token place in the current marking 13: Add(𝑝𝑙𝑎𝑐𝑒𝑠,𝑝𝑙𝑎𝑐𝑒)⊳Insert the initial place in the queue to visit it later 14: end for 15: while ¬Empty(𝑝𝑙𝑎𝑐𝑒𝑠)do ⊳While there are more places to visit 16: 𝑝𝑙𝑎𝑐𝑒 ←Poll(𝑝𝑙𝑎𝑐𝑒𝑠)⊳Extract the next place to explore 17: if 𝑝𝑙𝑎𝑐𝑒 ∈𝑝𝑙𝑎𝑐𝑒𝑠𝑉 𝑖𝑠𝑖𝑡𝑒𝑑 then 18: continue ⊳Skip the place if already visited 19: Add(𝑝𝑙𝑎𝑐𝑒𝑠𝑉 𝑖𝑠𝑖𝑡𝑒𝑑,𝑝𝑙𝑎𝑐𝑒)⊳Mark the place as visited 20: 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠 ←𝑝𝑙𝑎𝑐𝑒∙⊳Get the successors of the place 21: if |𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠|≠1then 22: continue ⊳Skip the place if it has more than one output arc or no output arcs 23: if ¬IsSilent(𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠[0])then ⊳If the transition is not silent 24: Add(𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑𝑇 𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠,𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠[0])⊳Register the transition as required 25: AddAll(𝑝𝑙𝑎𝑐𝑒𝑠,𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠[0]∙)⊳Queue each output place for exploration 26: end while 27: return 𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑𝑇 𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠 Fig. 5. Iterations of RequiredTransitions (Algorithm 3:8) for the initial state of the running example. For each iteration – row of the table – of the main while loop (Algorithm 3:15), the place being explored is highlighted on the left column and the state of the defined variables is shown on the right column. The 𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑𝑇 𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠,𝑝𝑙𝑎𝑐𝑒𝑠 and 𝑝𝑙𝑎𝑐𝑒𝑠𝑉 𝑖𝑠𝑖𝑡𝑒𝑑 variables show the values before the iteration, while the 𝑝𝑙𝑎𝑐𝑒 and 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠 variables show the values retrieved during the iteration. The initial marking only has one token on 𝑝0, which is added to 𝑝𝑙𝑎𝑐𝑒𝑠. The 𝑝𝑙𝑎𝑐𝑒 to visit in the first iteration (𝑝0) is extracted from 𝑝𝑙𝑎𝑐𝑒𝑠. This iteration checks that the successor of 𝑝0is only one transition. As this is true (|𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛𝑠|= 1), it marks the transition (𝐸𝑛𝑟𝑜𝑙𝑙) as required and adds all output places of the transition ([𝑝1]) to 𝑝𝑙𝑎𝑐𝑒𝑠. The second iteration processes 𝑝1as it is the first element of the 𝑝𝑙𝑎𝑐𝑒𝑠 queue. It has two successors, so it does not add any more places to 𝑝𝑙𝑎𝑐𝑒𝑠. It does not mark them as required as only one of them has to be executed so neither is mandatory. The 𝑝𝑙𝑎𝑐𝑒𝑠 queue is empty, so the algorithm stops. The only required transition found for this simple example is 𝐸𝑛𝑟𝑜𝑙𝑙. is added to the heuristic. These activities are required to be executed in order to reach the end of the model, so not having them in the remaining trace implies at least another move in the model in order to reach the end. For each of the unmatched trace activities remaining (Algorithm 3:6), the cost of a synchronous move is added, as another move with a minimum cost of a synchronous move has to be made for each of them in order to complete the alignment. In order for this heuristic to be valid, there must be only one reachable final marking of the model: one token in the end place. This condition, known as proper completion, guarantees that all transitions identified through the heuristic procedure will be necessary to reach the end of the model. Hence, this heuristic assumes that the model is a workflow net with proper completion — without the soundness requirement. This is a consistent heuristic that uses the standard cost function: assigns a positive value very close to 0 (𝑒𝑝𝑠𝑖𝑙𝑜𝑛) for synchronous moves and a cost of 1 to asynchronous moves. The number of unmatched required activities can only decrease by a maximum of 1 between parent and child states (𝑆𝑝𝑎𝑟𝑒𝑛𝑡 and 𝑆), and it may only decrease by 1 when the cost increases by 1 by performing an asynchronous move (𝑆.𝑐 −𝑆𝑝𝑎𝑟𝑒𝑛𝑡.𝑐), so the consistency condition (𝑆𝑝𝑎𝑟𝑒𝑛𝑡.ℎ ≤𝑆.𝑐 −𝑆𝑝𝑎𝑟𝑒𝑛𝑡.𝑐 + 𝑆.ℎ) is verified. Expert Systems With Applications 241 (2024) 122467 9 J. Casas-Ramos et al. Algorithm 4 Partial reachability graph: enabled transitions. Input: The current marking 𝑀. The single partially built reachability graph 𝑝for the workflow net is received as input even if the calling pseudocode does not specify it (𝑝is initialized as an empty map). Assumes that EnabledTransitions is called before ExecuteTransition for any marking. Output: The set of enabled transitions of the marking 𝑀. 1: procedure EnabledTransitions(𝑀,𝑝) 2: if 𝑀∈𝑝then ⊳If 𝑀had its enabled transitions listed previously 3: 𝑒𝑡𝑟𝑠 ←{𝑡∣ (𝑡, 𝑚) ∈ 𝑝[𝑀]} ⊳Retrieve the list of enabled transitions from 𝑝 4: else 5: 𝑒𝑡𝑟𝑠 ←{𝑡∣𝑀[𝑡⟩}⊳Compute the enabled transitions from 𝑀 6: 𝑝[𝑀]←{(𝑒𝑡𝑟, 𝑛𝑢𝑙𝑙) ∣ 𝑒𝑡𝑟 ∈𝑒𝑡𝑟𝑠}⊳Record the enabled transitions, mapped to 𝑛𝑢𝑙𝑙 7: return 𝑒𝑡𝑟𝑠 Algorithm 5 Partial reachability graph: execute transition. Input: The current marking 𝑀and the transition to execute 𝑡. The single partially built reachability graph 𝑝for the workflow net is received as input even if the calling pseudocode does not specify it (𝑝is initialized as an empty map). EnabledTransitions assumes that EnabledTransitions is called before ExecuteTransition for any marking. Output: The new marking 𝑀′after executing 𝑡on the marking 𝑀. 1: procedure ExecuteTransition(𝑀,𝑡,𝑝) 2: if 𝑝[𝑀][𝑡]≠𝑛𝑢𝑙𝑙 then ⊳If 𝑡was previously executed from 𝑀 3: 𝑀′←𝑝[𝑀][𝑡]⊳Retrieve the next marking from the partial reachability graph 4: else 5: 𝑀′←𝑀−∙𝑡+𝑡∙⊳Compute the new marking after executing the 𝑡transition 6: 𝑝[𝑀][𝑡]←𝑀′⊳Record the transition execution in the partial reachability graph 7: return 𝑀′ Fig. 6. Example of the partial reachability graph computed while executing the trace 〈Enroll, Class, Exam〉on the running example (Fig. 1). Before executing each transition of the example trace, all enabled transitions of the marking are computed. The nodes of the graph are markings. Known markings are circles and unexplored ones are diamonds. Final markings are represented with a double circle. The node contents show a unique identifier if explored and a question mark otherwise. Each arc between two nodes is labeled with the enabled transition whose execution generates the target marking from the source marking. 4.2. Optimizing the algorithm This section focuses on our contributions to the core A*-based alignments algorithm: (i) partial reachability graph, and (ii) several states reduction optimizations. 4.2.1. Partial reachability graph All state-of-the-art algorithms need to execute the workflow net to be able to compute optimal alignments. Thus, all algorithms perform operations over the workflow net for creating an initial marking (Algorithm 1:17), listing all enabled transitions for a marking (Algorithm 2:2), executing a transition (Algorithm 2:26) and checking if a marking is final (Algorithm 1:23). Those operations affect performance, as they are executed several times for each iteration of A*. Our approach introduces a significant difference from the state of the art. We propose the dynamic construction of a partial reachability graph (PRG) as new model markings are reached. This change is aimed at leveraging information from prior model operations to enhance the speed of future iterations. To make the execution of the workflow net faster, a directed graph is created that shows the different explored states of the system. This graph is stored in 𝑝, which is initially empty (Algorithm 4). When explored, each marking is stored as an entry in 𝑝and represents a vertex in the graph (Algorithm 4:5-6). When each marking 𝑀is explored, each enabled transition from 𝑀is represented by an entry in the 𝑝[𝑀] mapping, which maps to the new marking after executing the transition (Algorithm 5:5-6), or null if it was never executed (Algorithm 4:56). The enabled transitions serve as arcs connecting states within the graph. This builds at runtime a data structure similar to a reachability graph (Davidrajuh,2013). Nevertheless, only the explored states are generated. Hence, it avoids building the full reachability graph which would be a computationally intensive task, especially for models with lots of branching and concurrent transitions. Instead, it only stores information about states that are needed in the algorithm’s exploration. Once repeated model operations start occurring, e.g. due to loops in the model or to the beginning of the alignment computation over a new trace of the log, the partial reachability graph can quickly access enabled transitions and new markings (Algorithm 4:2-3and 5:2-3). This information is kept while aligning all the traces of the log to the model, which is the main reason for the speedup. Fig. 6 shows the partial reachability graph for the running example and a simple trace. The advantages of this PRG become evident as the algorithm progresses and repeated model operations become commonplace. For instance, when loops occur within the model or when aligning a new trace from the log, the PRG swiftly facilitates access to enabled transitions and the corresponding new markings. 4.2.2. State reduction-based optimizations The primary challenge in computing conformance checking alignments using the A* algorithm is the substantial number of generated states that must be stored and evaluated to ensure optimal results. To mitigate this problem, we propose new optimizations focused on states reduction that will alleviate the state explosion that occurs for complex datasets: (i) States Reduction forcing asynchronous Model moves (SRModel), (ii) States Reduction forcing asynchronous Log moves (SRLog), and (iii) an initial greedy search that finds a cost limit. Expert Systems With Applications 241 (2024) 122467 16 J. Casas-Ramos et al. Fig. 11. Solved problems of each algorithm with a time limit of 10 s. Table 5 Number of solved problems of the tested algorithms with a time limit of 10 s, splitting log-model pairs by fitness and precision. Algorithm Fitness Precision 0.0–0.25 0.25–0.5 0.5–0.75 0.75–1.0 0.0–0.5 0.5–0.75 0.75–1.0 REACH 0 22 64 121 1 32 62 ProMNoILP 016 45 102 121 55 ProMILP 015 44 99 126 52 ProMLP 016 42 100 124 53 AutoHybrid 04 35 85 116 40 AutoTRSComp 02 31 76 116 31 AutoSComp 015 42 82 119 49 AutoConf 09 42 100 128 53 eMEQ 016 43 105 127 60 PartialReplayer 014 19 51 110 36 RecomposingReplay 015 9 62 116 35 Number of problems 3 28 66 130 1 33 62 problems: a lower fitness means a higher cost of the optimal alignment, and alignments of higher cost – with more misalignments to repair – are much more difficult to compute. In terms of precision, reach also solves more problems than the state of the art, with the exception of precision values lower than 0.5, where there is only one example solved by all algorithms. Similarly to fitness, the precision level of input log-model pairs does not affect on the number of problems solved by reach. We have also compared the execution times that each algorithm needs to solve each of the 227 log-model pairs. To establish whether there are statistically significant differences between reach and the other tested algorithms, we performed a non-parametric test using the execution times. First, a Friedman’s Aligned Ranks test with a significance level of 0.05 has been applied. The ranking is calculated by ordering the execution times of all the algorithms for each log-model pair – the best algorithm obtains a rank of 1 –, and then averaging the ranking of each algorithm in all the log-model pairs. The results of this test are summarized in Table 6. The table clearly shows that reach achieves the top ranking. In the second position, we find a non-optimal algorithm, AutoSComp, followed by the second-best optimal algorithm, PromNoILP. As the p-value of the Friedman test is lower than 10−5, there are significant differences in performances among the algorithms. Thus, we applied Holm’s post hoc test to perform a pairwise comparison between reach and the tested algorithms. The results of this test confirm that there are statistically significant differences between reach and the other algorithms, with p-values consistently lower than 10−5. Therefore, we can conclude that reach is, on average, the fastest algorithm in our experiments over 227 diverse log-model pairs. 5.4.2. Results with a time limit of 300 s Fig. 12 depicts the results of the algorithms for a time limit of 300 s. reach computes 216 log-model pairs in less than 45 s, reaching the time limit in only 11 of them. Conversely, other fast algorithms require more time to compute alignments, delivering results progressively and nearing the 5-minute time limit — and cannot return optimal alignments for some log-model pairs for which our approach is successful. Concretely, after 45 s of execution, the second-best optimal algorithms —eMEQ and ProMNoILP— align 195 log-model pairs, and the next best optimal algorithm —ProMILP— solves 194 pairs, while reach aligns 9% more log-model pairs. When the time limit of 5 min is reached, the fastest algorithms after reach are eMEQ, ProMLP and ProMNoILP, with 214, 212, and 210 solved log-model pairs respectively — in the best case, they solve 2 log-model pairs less than reach solves in less than 45 s. For the 227 tested log-model pairs, reach is the fastest optimal algorithm in 125 pairs. In the remaining pairs, the computation time of reach is, at most, 3 s slower than the fastest algorithm for each pair, except for 3 log-model pairs from Noisy logs (Munoz-Gama,2013), for which only eMEQ is capable of finishing within the given timeout. These models are synthetic with extensive parallelism, leading to an excessive number of states that most algorithms cannot efficiently explore. As stated in van Dongen (2018), the logs for those models were built with vast amounts of swapped activities towards the end of the traces, which is a known weakness of A*-based methods. The ILP-based heuristic proposed in van Dongen (2018) is very effective in detecting swapped activities. However, this method spends more time computing the heuristic on each state, which makes it slower on average in the complete test dataset. Expert Systems With Applications 241 (2024) 122467 17 J. Casas-Ramos et al. Table 6 Performance ranking of the tested algorithms. Rank REACH 3.405 ProMNoILP 5.084 AutoSComp 5.132 AutoConf 5.460 eMEQ 5.518 AutoHybrid 5.597 ProMLP 5.888 ProMILP 6.081 AutoTRSComp 6.319 RecomposingReplay 8.566 PartialReplayer 8.949 Rank REACH 3.242 ProMNoILP 4.641 eMEQ 4.998 ProMLP 5.390 AutoSComp 5.399 AutoConf 5.678 ProMILP 5.797 AutoHybrid 5.945 AutoTRSComp 6.888 RecomposingReplay 8.980 PartialReplayer 9.042 Fig. 12. Solved problems of each algorithm with a time limit of 300 s. Table 7 Number of solved problems of the tested algorithms with a time limit of 300 s, splitting log-model pairs by fitness and precision. Algorithm Fitness Precision 0.0–0.25 0.25–0.5 0.5–0.75 0.75–1.0 0.0–0.5 0.5–0.75 0.75–1.0 REACH 322 65 126 1 33 62 ProMNoILP 322 64 119 130 60 ProMILP 2 22 64 122 1 33 61 ProMLP 3 23 63 123 132 61 AutoHybrid 0 4 37 101 125 43 AutoTRSComp 0 2 31 94 122 38 AutoSComp 0 19 45 101 127 55 AutoConf 39 45 105 129 55 eMEQ 322 62 127 1 33 62 PartialReplayer 0 21 60 119 132 61 RecomposingReplay 0 17 39 97 129 50 Number of problems 3 28 66 130 1 33 62 Our algorithm is the only one capable of computing alignments for the most complex models of the BPIC15 log. The primary contributor to the success of these log-model pairs is the SRLog optimization, which can prevent timeouts on its own. These examples have a large number of transitions (around 130), of which a considerable amount are silent transitions (around 60), leading to the generation of a large number of model moves needed from each state explored by the A* algorithm. The proposed optimization benefits from this situation, as it reduces the number of states when possible by forcing an asynchronous move in the log and avoiding all those unnecessary model moves. Table 7 displays the solved log-model pairs per algorithm within a timeout of 300 s, categorizing problems by fitness and precision levels. Focusing on fitness, eMEQ and ProMLP solve one more problem than reachin ranges 0.75-1.00 and 0.25–0.50, respectively, but overall, reach consistently matches the performance of the best state-of-the-art algorithms. We have observed no correlation between the fitness range of the input problem and the number of problems solved by reach. In terms of precision, reach is matched by eMEQ, while algorithms like ProMILP, PromLP or PartialReplayer exhibit very similar performance solving one or two less log-model pairs than reach. Again, we have observed no correlation between the precision range of the input problem and the number of solved problems of reach. As shown in Fig. 12 even though reach solves almost the same number of problems as some algorithms, it does so much faster than the state of the art. In the rankings (Table 6), reach holds a position with a score of 3.242, surpassing the next best algorithm from the state of the art (ProMNoILP) with a ranking of 4.641. This reinforces the confidence that reach is much faster, as this rank compares the time to compute alignments for each log-model pair. To confirm again that there are Expert Systems With Applications 241 (2024) 122467 18 J. Casas-Ramos et al. statistically significant differences between reach and the other algorithms for a time limit of 300 s, we have repeated the Friedman’s and Holm’s tests — based on the ranking from Table 6. Regarding Friedman’s test, reach has the best ranking with a p-value lower than 10−5, indicating again that there are statistically significant differences in the performances of the algorithms. Furthermore, Holm’s test allows the rejection of the null hypothesis in all the pairwise comparisons between reach and the other algorithms, since the p-values are lower than 10−5 in all cases. 5.5. Limitations Although reach achieves superior performance compared to stateof-the-art algorithms, it still presents certain limitations. reach does not succeed in solving 11 of the 227 tested log-model pairs due to the nature of the A* search: the number of states to explore explodes based on the complexity of the models and logs, as well as the cost of the optimal alignment. There are several factors that affect the performance of the algorithm in those cases, among which we highlight: •The parallelism allowed by the process model, i.e., the average number of enabled activities for each reachable marking. Each of those activities must generate a new neighboring state by performing a model move when that marking is reached. Each state added to the search space when exploring the neighbors of a state exponentially increases the time complexity, as each generated state is recursively explored if the search algorithm requests it. This is aggravated by the presence of silent transitions, which allow reaching different markings of the process model without increasing the cost, effectively raising the number of neighboring states. Loops also contribute to this by removing the length limit of paths through the model. •The length of each trace directly affects the number of moves required in the optimal alignment. As alignments are constructed from start to end, adding a move at each state transition, the depth of the solution in the search space increases with the addition of an event to the trace. Increasing the depth of the explored search space exponentially raises the time complexity of the algorithm. •The cost of the optimal alignment, i.e., the minimum number of errors that must be repaired for the trace to follow a valid path through the model, forces the A* search to explore more states. This is because the solution will include more asynchronous movements of cost 1, compelling the search algorithm to ensure that there are no complete alignments of lower cost than the optimal one. Among the 227 tested log-model pairs, reach was not the fastest optimal algorithm in 100 instances. Notably, these cases primarily correspond to the simplest problems in the experiment. This observation is visually supported by Fig. 11, where it can be seen that reach takes slightly longer to solve most of the problems that take less than one second. The median delay of reach with respect to the fastest optimal algorithm for each of these pairs is 204 ms, and the fastest algorithm is not always the same, varying among ProMNoILP, ProMILP, ProMLP, AutoConf, eMEQ and RecomposingReplay. The delay observed in simple log-model pairs for reach is primarily attributed to the extended initialization time required by the proposed optimizations. These optimizations have been designed with the aim of enhancing performance in the context of complex log-model pairs. Even with all optimizations applied, reach was unable to complete the alignments computation for 11 of the tested log-model pairs within less than five minutes. The only optimal algorithm capable of solving three of these pairs is eMEQ (van Dongen,2018). This algorithm uses a complex heuristic based on Integer Linear Programming (ILP), which proves more effective than reach at detecting misalignments toward the end of the trace. For each state, the ILP solver can estimate the minimum cost of a solution without overestimating it, thus suiting A* heuristics. Although this estimation is computationally expensive, it is more accurate than reach, making eMEQ capable of solving three log-model pairs that reach cannot finish within the given time limit. 6. Conclusions and future work We have presented reach, an A*-based algorithm that computes in a very efficient way optimal alignments. The main contributions of our proposal include techniques designed to minimize the number of states explored by the A* algorithm and the utilization of a partial reachability graph for faster execution of process models during alignment computation. We have tested our proposal with 227 logmodel pairs from different domains and discovered using different algorithms. We verified the performance of each contribution of our algorithm by partially enabling the proposed optimizations, and we have compared the performance of our proposal with 10 state-of-theart conformance-checking algorithms. Results show that reach aligns 95% of the tested log-model pairs in less than 45 s. Remarkably, our proposed optimizations empower reach to complete alignments in just 45 s for two log-model pairs that no other algorithm can solve within a 5-minute time frame. Moreover, for a 10-second time limit, it also aligns 26% more pairs than all the other optimal state-of-the-art algorithms. reach exhibits exceptional speed, outperforming all state-ofthe-art approaches by aligning 55% of the log-model pairs more rapidly than any other algorithm. Our performance improvements enable the efficient computation of optimal alignments, allowing users to perform more precise conformance checking. By eliminating the need to rely on fast but less accurate methods, our approach opens up new possibilities for the application of conformance checking in real-world scenarios. However, reach still presents some limitations that should be addressed in future work. It currently proposes a balanced heuristic between accuracy and computing time, but this may not return the fastest solution for some log-model pairs: (i) for some high-complexity pairs, Integer Linear Programming (ILP) can be used to define more accurate heuristics (although slower) than our heuristic, or (ii) very easy to compute optimal alignments, that could be solved faster by algorithms that compute simple heuristics very quickly, albeit inaccurately. The SRLog optimization also slightly increases the computation time for the simplest problems due to the relatively slow initialization phase. Therefore, as future work, we plan to develop a more advanced heuristic based on ILP, focusing on reducing the time spent on each state. Nevertheless, simpler problems are solved faster when using simpler heuristics and disabling the SRLog optimization. Hence, we will propose a new classification technique that, based on the characteristics of the input log and model, selects the heuristic and optimizations that best tackle the given problem. CRediT authorship contribution statement Jacobo Casas-Ramos: Conceptualization, Methodology, Software, Validation, Formal analysis, Investigation, Data curation, Writing – original draft, Visualization. Manuel Mucientes: Conceptualization, Methodology, Resources, Writing – review & editing, Supervision, Funding acquisition. Manuel Lama: Conceptualization, Methodology, Resources, Writing – review & editing, Supervision, Funding acquisition. Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. Expert Systems With Applications 241 (2024) 122467 19 J. Casas-Ramos et al. Data availability The evaluation logs and models are public/available on request. The source code, executable and the API are shared for academic purposes (CC BY-NC-ND license) on the link provided in the manuscript. Acknowledgments This research was partially funded by the Spanish Ministerio de Ciencia e Innovación (grant number PID2020-112623GB-I00), and the Galician Consellería de Cultura, Educación e Universidade (grant numbers ED431C 2018/29 and ED431G2019/04). These grants are cofunded by the European Regional Development Fund (ERDF). Jacobo Casas-Ramos is supported by the Spanish Ministerio de Universidades under the FPU national plan (grant number FPU19/06668). References Adriansyah, A. (2014). Aligning observed and modeled behavior (Ph.D. thesis), Technische Universiteit Eindhoven. Adriansyah, A., Munoz-Gama, J., Carmona, J., van Dongen, B. F., & van der Aalst, W. M. P. (2013). Alignment based precision checking. In Business process management 2012 international workshops (pp. 137–149). Springer. Berti, A., & van der Aalst, W. M. P. (2021). A novel token-based replay technique to speed up conformance checking and process enhancement. Transactions on Petri Nets and Other Models of Concurrency,15, 1–26. Carmona, J., van Dongen, B., Solti, A., & Weidlich, M. (2018). Conformance checking. Springer International Publishing. Davidrajuh, R. (2013). Extended reachability graph of Petri net for cost estimation. In 2013 8th EUROSIM congress on modelling and simulation (pp. 378–383). de Leoni, M., & van der Aalst, W. M. P. (2013). Aligning event logs and process models for multi-perspective conformance checking: An approach based on integer linear programming. In 11th international conference on business process management (pp. 113–129). Springer. de Leoni, M., Lanciano, G., & Marrella, A. (2018). Aligning partially-ordered processexecution traces and models using automated planning. In 28th international conference on automated planning and scheduling (pp. 321–329). de Leoni, M., & Mannhardt, F. (2015). Road traffic fine management process. de Leoni, M., & Marrella, A. (2017). Aligning real process executions and prescriptive process models through automated planning. Expert Systems with Applications,82, 162–183. Garcia-Banuelos, L., van Beest, N. R. T. P., Dumas, M., Rosa, M. L., & Mertens, W. (2018). Complete and interpretable conformance checking of business processes. IEEE Transactions on Software Engineering,44(3), 262–290. Hart, P., Nilsson, N., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. Lee, W. L. J., Verbeek, H., Munoz-Gama, J., van der Aalst, W. M., & Sepúlveda, M. (2018). Recomposing conformance: Closing the circle on decomposed alignmentbased conformance checking in process mining. Information Sciences,466, 55–91. Leemans, S. J. J., Fahland, D., & van der Aalst, W. M. P. (2014). Discovering blockstructured process models from event logs containing infrequent behaviour. In Business process management 2013 international workshops (pp. 66–78). Springer. Leemans, S. J. J., Fahland, D., & van der Aalst, W. M. P. (2018). Scalable process discovery and conformance checking. Software & Systems Modeling,17(2), 599–631. Leemans, S. J. J., van der Aalst, W. M. P., Brockhoff, T., & Polyvyanyy, A. (2021). Stochastic process mining: Earth movers’ stochastic conformance. Information Systems,102, Article 101724. Lu, X., Fahland, D., & van der Aalst, W. M. P. (2015). Conformance checking based on partially ordered event data. In Lecture notes in business information processing, Business process management 2014 workshops (pp. 75–88). Mannhardt, F. (2016). Sepsis cases - event log. Maruster, L., Weijters, A., van der Aalst, W., & van den Bosch, A. (2006). A rule-based approach for process discovery: Dealing with noise and imbalance in process logs. Data Mining and Knowledge Discovery,13(1), 67–87, Pagination: 21. Munoz-Gama, J. (2013). ’Conformance checking in the large’ (BPM 2013). Munoz-Gama, J. (2014). Single-entry single-exit decomposed conformance checking (IS 2014). Munoz-Gama, J., Carmona, J., & van der Aalst, W. M. P. (2013). Hierarchical conformance checking of process models based on event logs. In 34th international conference application and theory of petri nets and concurrency (pp. 291–310). Springer. Munoz-Gama, J., Carmona, J., & van der Aalst, W. M. P. (2014). Single-entry single-exit decomposed conformance checking. Information Systems,46, 102–122. Reißner, D., Armas-Cervantes, A., Conforti, R., Dumas, M., Fahland, D., & La Rosa, M. (2020). Scalable alignment of process models and event logs: An approach based on automata and S-components. Information Systems, Article 101561. Reißner, D., Armas-Cervantes, A., & La Rosa, M. (2020). Efficient conformance checking using alignment computation with tandem repeats. arXiv preprint arXiv:2004. 01781. Reißner, D., Conforti, R., Dumas, M., La Rosa, M., & Armas-Cervantes, A. (2017). Scalable conformance checking of business processes. In On the move to meaningful internet systems: OTM 2017 conferences (pp. 607–627). Rozinat, A., & Van der Aalst, W. M. (2008). Conformance checking of processes based on monitoring real behavior. Information Systems,33(1), 64–95. Sani, M. F., van Zelst, S. J., & van der Aalst, W. M. P. (2020). Conformance checking approximation using subset selection and edit distance. In 32nd international conference on advanced information systems engineering (pp. 234–251). Springer. Taymouri, F., & Carmona, J. (2016). A recursive paradigm for aligning observed behavior of large structured process models. In 14th international conference business process management (pp. 197–214). Springer. Taymouri, F., & Carmona, J. (2018). An evolutionary technique to approximate multiple optimal alignments. In 16th international conference business process management (pp. 215–232). Springer. Taymouri, F., & Carmona, J. (2020). Computing alignments of well-formed process models using local search. ACM Transactions on Software Engineering and Methodology,29(3), 1–41. van den Broucke, S. K., Munoz-Gama, J., Carmona, J., Baesens, B., & Vanthienen, J. (2014). Event-based real-time decomposed conformance analysis. In On the move to meaningful internet systems: OTM 2014 conferences (pp. 345–363). van der Aalst, W. M. P. (1996). Structural characterizations of sound workflow nets. Computing Science Reports,96(23), 18–22. van der Aalst, W. M. P. (2013). Decomposing Petri nets for process mining: A generic approach. Distributed and Parallel Databases,31(4), 471–507. van der Aalst, W. M. P., Adriansyah, A., de Medeiros, A. K. A., Arcieri, F., Baier, T., Blickle, T., et al. (2012). Process mining Manifesto. In Business process management 2011 international workshops (pp. 169–194). van Dongen, B. (2012). BPI Challenge 2012. van Dongen, B. F. (2018). Efficiently computing alignments. In Business process management (pp. 197–214). Cham: Springer International Publishing. van Dongen, B., Carmona, J., Chatain, T., & Taymouri, F. (2017). Aligning modeled and observed behavior: A compromise between computation complexity and quality. In 29th international conference on advanced information systems engineering (pp. 94–109). Springer.