<figure><img src="image_1.png" /></figure>

HAL
open science

# Model and Event Log Reductions to Boost the Computation of Alignments

Farbod Taymouri, Josep Carmona

► To cite this version:

Farbod Taymouri, Josep Carmona. Model and Event Log Reductions to Boost the Computation of Alignments. 6th International Symposium on Data-Driven Process Discovery and Analysis (SIMPDA), Dec 2016, Graz, Austria. pp.1-21, 10.1007/978-3-319-74161-1_1 . hal-01769756

HAL Id: hal-01769756

https://inria.hal.science/hal-01769756

Submitted on 18 Apr 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Model and Event Log Reductions to Boost the Computation of Alignments

Farbod Taymouri and Josep Carmona

Universitat Politècnica de Catalunya, Barcelona (Spain)
{taymouri,jcarmona}@cs.upc.edu

**Abstract.** The alignment of observed and modeled behavior is a pivotal issue in process mining because it opens the door for assessing the quality of a process model, as well as the usage of the model as a precise predictor for the execution of a process. This paper presents a novel technique for reduction of a process model based on the notion of *indication*, by which, the occurrence of an event in the model reveals the occurrence of some other events, hence relegating the later set as less important information when model and log alignment is computed. Once indications relations are computed in the model, both model and log can be reduced accordingly, and then fed to the state of the art approaches for computing alignments. Finally, the (macro)-alignment derived is expanded in these parts containing high-level events that represent a set of indicated events, by using an efficient algorithm taken from bioinformatics that guarantees optimality in the local parts of the alignment. The implementation of the presented techniques shows a significant reduction both in computation time and in memory usage, the latter being a significant barrier to apply the alignment technology on large instances.

**Keywords:** Process Mining, Conformance Checking, Alignment, SESE, Model Abstraction

## 1 Introduction

Nowadays many systems generate *event logs*, which are footprints left by process executions. *Process mining* delves into this information and examines it to extract, analyze and enhance evidence-based process models [15]. One of the challenges in process mining is how to align a process model to a set of traces forming an event log. Given a trace representing a real process execution, an *optimal alignment* provides the best trace the process model can provide to imitate the observed trace [1]. Alignments are crucial for important metrics like fitness, precision and generalization [1,2].

This paper presents a model-based technique for reduction of a process model and observed behavior that both preserves the semantics of the process model and retains the information of the original observed behavior as much as possible. The technique is meant to fight the main problem current approaches for alignment computation have: the complexity both in space and time. In other
words the main goal of the reduction of a process model and event log presented in this paper is to alleviate the current computational challenge of computing an alignment rather than abstracting a process model to capture its essential fragments and hiding details [11]. Therefore given a process model a particular kind relation between transitions of the model which implies *causality* is of interest and the presented technique seeks corresponding fragments of the process model for this issue by which reduces the model. Also, other kinds of relation between transitions of the model for the aim of abstraction or consistency verification between process model are presented in [19] which are not suitable for the mentioned challenge. More specific, the overall idea of this paper relies on the notion of *indication* between activities of the process model when it is represented as a Petri net. An indication relation between a set of transitions (indicated set) and another transition (indicator) denotes a deterministic causal firing relation in the model, which expresses that the presence in any model's sequence of the indicator transition requires the presence of the indicated set as well. The notion of indication is inspired from the *reveals relation* from [3] and *co-occurrence relation* in [19]. We use a well-known technique to find logically independent parts of a graph (known as *fragment with entry-exit pair* in [12] or the so-called *Single Entry Single Exit (SESE)* in [6]), which are then used to gather indication relations efficiently. These relations dictate which parts of a process model are abstracted as a single, high-level node. Once the model is reduced, the observed trace to align is projected (hence, reduced as well) into the reduced model's alphabet. This way, not only the model but also the trace are reduced, which in turn makes the alignment techniques to be significantly alleviated, specially for well-structured process models where many indication relations may exist. Once alignments are computed, the final step is also an interesting contribution of this paper: to cast the well-known Needleman-Wunsch algorithm [9] to expand locally each high-level part of the alignment computed, using the indication relation.

## 2 Related Work

The seminal work in [1] proposed the notion of alignment, and developed a technique to compute optimal alignments for a particular class of process models. For each trace $\sigma$ in the log, the approach consists on exploring the synchronous product of model's state space and $\sigma$. In the exploration, the shortest path is computed using the $A^*$ algorithm, once costs for model and log moves are defined. The approach is implemented in ProM, and can be considered as the state-of-the-art technique for computing alignments. Several optimizations have been proposed to the basic approach to speed up and improve memory consumption. The recent work in [14] proposed a divide and conquer strategy based on Integer Linear Programming (ILP) approach to compute approximate alignments. Despite its memory and time efficiency, it cannot guarantee the obtention of an (optimal) alignment. The similar approach which combines the ideas of two mentioned techniques and can always guarantee a solution (not optimal) and
heavily uses the resolution of ILP and marking equation in combination with a
bounded backtracking is presented in [16].

The work in [7] presented a decomposition approach using SESEs for con-
formance checking of the model and observed behavior. The proposed approach
decomposes a given model to smaller parts via SESE and then applies confor-
mance checking for each part independently. This technique is very efficient, but
the result is decisional (a yes/no answer on the fitness of the trace). Recently
[18] proposed a new approach which provides an algorithm that is able to obtain
such an optimal alignment from the decomposed alignments if this is possible,
which is called proper optimal alignment. Otherwise, it produces a so-called
pseudo-alignment which as in the case of [14], may not be executable in the net.

The *Refined Process Structure Tree* (RPST), proposed by [17], is a graph parsing technique that provides well-structured parts of a graph. The resulting parse tree is unique and modular, i.e., local change in the local workflow graph results in a local change of the parse tree. It can be computed in linear time using the method proposed in [13] which is based on the triconnected components of a given biconnected graph. The proposed approach only works with single sink, single source workflow graphs which hampers its applicability to real world problems with many sink, source nodes. The work in [12] presents a more efficient way to compute RPST which can deal with multiple source, sink workflow graphs.

Abstraction of business process models is presented in [11]. The core idea
is to replace the process fragments inside a given process model with the pro-
cess tasks of higher abstraction levels to simplify the given process models for
non-technical stakeholders. The key property of the presented approach is *order
preservation*, by which the abstraction mechanism ensures that neither new task
execution order constraints are produced nor existing ones gone after abstrac-
tion. Stated differently the mentioned property secures the overall process logic
to be reflected in the abstracted model. To identify process fragments, the paper
uses the notion of *process component* i.e., a process fragment which is connected
to the rest of the model by only two nodes namely fragment entry and fragment
exit. Identifying process components in a given process model amounts to finding
*triconnected* components of a graph. To this end the presented approach lies on
*SPQR-tree* decomposition, by which triconnected components can be obtained.
Afterwards, the proposed abstraction rules utilize these components. Four ab-
straction rules are presented which depend on the structure types returned from
the decomposition stage. Since the proposed approach relays on identifying tri-
connected components of a process model therefore it must have some structural
characteristics like being free of self-loop structural patterns and must contain no
places with multiple incoming and multiple outgoing arcs. Similarly the work in
[19] presents *causal behavioural profile* notion for consistency verification between
a normative model and its workflow implementation, i.e., to what degree the be-
havior of the later is captured by the former. The mentioned notion represents a
behavioural abstraction that includes dependencies in terms of *order*, *exclusive-*
*ness* and *causality* between pairs of activities of a process model. The general
idea of consistency measure is as follows, given the correspondence relation be-
tween the sets of transitions of two WF-nets, all respective transitions of two
models are aligned and for each pair of aligned transitions it is checked whether
those transitions show the same constraints as defined by the causal behavioural
profile. To compute causal behavioural profile efficiently, the presented approach
concretises RPST fragments by annotating them with behavioural characteris-
tics. Stated differently, an explicit relation between structural and behavioural
characteristics is established.

The seminal work [5] first introduced the notion of *reveals relation*, which
determines that whenever an action *a* happens, then the occurrence of another
action *b* is inevitable. The notion of indication in this paper on the one side
is inspired on the *reveals relation* and on the other side is an extension over
co-occurrence relation between two transitions of the process model defined in
[19].

3 Preliminaries

3.1 Petri Nets, Structural Deadlock

A Petri Net is a 3-tuple $N = (P, T, \mathcal{F})$, where $P$ is the set of places, $T$ is the set of transitions, $P \cap T = \emptyset$, $\mathcal{F} : (P \times T) \cup (T \times P) \to \{0,1\}$ is the flow relation. Marking of a Petri net represents the number of tokens each place has. Given a node $x \in P \cup T$, its pre-set and post-set (in graph adjacency terms) are denoted by $\bullet x$ and $x^\bullet$ respectively. A transition $t$ is enabled in a marking $m$ when all places in $\bullet t$ are marked. When a transition $t$ is enabled, it can fire or execute by removing a token from each place in $\bullet t$ and putting a token to each place in $t^\bullet$. A marking $m'$ is reachable from $m$ if there is a sequence of firings $t_1t_2\dots t_n \in T^*$ that transforms $m$ into $m'$, denoted by $m[t_1t_2\dots t_n]m'$. For a given model $N$ and initial marking $m_0$, the set $RS(N, m_0) = \{m \mid \exists w \in T^* . m_0[w]m\}$ is the reachability set [8].

A structural deadlock or simply deadlock in a Petri net is a set of places
such that every transition which outputs to one of the places in the deadlock
also inputs from one of these places. Formally, a nonempty subset of places $P_d$
of a net $N$ is a deadlock if $\bullet P_d \subseteq P_d^\bullet$, See Fig. 2. Deadlocks have the following
properties [10], [4]:

- If marking $m \in RS(N, m_0)$ is a deadlock state then $P_d = \{p|m[p] = 0\}$, is an unmarked set of places.

- Once all of the places in the deadlock become unmarked, the entire set of places will always be unmarked; no transition can place a token in the deadlock because there is no token in the deadlock to enable a transition which outputs to a place in the deadlock.

WF-net is a Petri net where there is a place *start* (denoting the initial state
of the system) with no incoming arcs and a place *end* (denoting the final state
of the system) with no outgoing arcs, and every other node is within a path
between *start* and *end*. Fig. 1(a) represents a WF-net.
<figure><img src="image_3.png" /><figcaption>Fig. 1: (a) WF-net, (b) Workflow graph, (c) RPST, (d) Reduced WF-net</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2: $P_d = \{P_1, P_2, P_3\}$, $\bullet P_d = \{t_2\}$, $P_d^\bullet = \{t_1, t_2\}$</figcaption></figure>

## 3.2 Trace, Event Log, Alignment

Given an alphabet of events $T = \{t_1, \dots, t_n\}$, a trace is a word $\sigma \in T^*$ that represents a finite sequence of events. An *event log* $L \in \mathcal{B}(T^*)$ is a multiset of traces<fnref n="1" />. An *alignment* is represented by a two-row matrix where the top and bottom rows represent moves on log and the model respectively. Such an alignment reveals how the given trace can be replayed on the process model. The classical notion of aligning event log and process model was introduced by [1].

<footnote n="1">¹ $\mathcal{B}(A)$ denotes the set of all multisets of the set $A$.</footnote>
To achieve an alignment between a process model and an event log, we need to relate *moves* in the trace to *moves* in the model. It may be the case that some of the moves in the trace can not be mimicked by the model and vice versa, i.e., it is impossible to have synchronous moves by both of them. For example given trace $t_1t_4t_2t_5t_8$ and the model in Fig. 1(a), an example of alignment is:

$$ \alpha = \frac{|t_1| \perp |t_4| |t_2| |t_5| \perp |t_8|}{|t_1| |t_2| |t_4| \perp |t_5| |t_7| |t_8|} $$

where the model is able to mimic $t_1$, $t_4$, $t_5$ and $t_8$ hence they are called *syn-chronous* moves and the rest are *asynchronous* moves. If weight is assigned to each move such that synchronous moves get less weight than asynchronous moves then an *optimal* alignment which is of interest is the one with minimum cost.

### 3.3 Interior and Boundary Nodes, SESE

Let $F \subseteq E$ represents a set of edges of a directed graph $\langle V, E, \ell \rangle$, $G_F = \langle V_F, F \rangle$ is the subgraph formed by $F$ if $V_F$ is the smallest set of nodes such that $G_F$ is a subgraph. A node in $V_F$ is *boundary* with respect to $G_F$ if it is connected to nodes in $V_F$ and in $V - V_F$, otherwise it is *interior*. A boundary node $u$ of $G_F$ is an *entry* node if no incoming edge of $u$ belongs to $F$ or if all outgoing edges of $u$ belong to $F$. A boundary node $v$ of $G_F$ is an *exit* node of $G_F$ if no outgoing edge of $v$ belongs to $F$ or if all incoming edges of $v$ belong to $F$. $G_F$ with one entry and one exit node is called *Single Entry Single Exit (SESE)*. If a SESE contains only one edge it is called trivial. A SESE of $G$ is called *canonical* if it does not overlap with any other SESEs of $G$, but it can be nested or disjoint with other SESEs. For example in Fig. 1(b) all SESEs are canonical, $S_2$ and $S_4$ are nested, $S_3$ and $S_2$ are disjoint. A WF-net can be viewed as a Workflow graph if no distinctions are made between its nodes. WF-graph of Fig. 1(a) is presented in Fig. 1(b). Let $G$ be a graph, then its *Refined Process Structure Tree (RPST)* is the set of all canonical SESEs of $G$. Because canonical fragments are either nested or disjoint, they form a hierarchy. In a typical RPST, the leaves are trivial SESE and the root is the whole graph. Fig. 1(c) is the RPST of WF-graph in Fig. 1(b), $S_1$ which is the entire graph is at root and leaves are trivial SESEs which only contain one edge.

## 4 Overall Framework

Given a process model $N$, represented by a Petri net, and $\sigma$ as observed behavior, the strategy of this paper is sketched in Fig. 3. We now provide descriptions of each stage.
<figure><img src="image_5.png" /><figcaption>Fig. 3: Overall framework for boosting the computation of alignments</figcaption></figure>

- *Model Reduction*: *N* will be reduced based on the notion of *indication* relation which results in *N*<sub>r</sub>. It contains some abstract events representing the indicators of certain indicated sets of transitions. Section 5.1 explains it in detail.

- *Log Reduction:* Using the indication relations computed in the model, $\sigma$ is projected into the remaining labels in $N_r$, resulting in $\sigma_r$. Section 5.2 describes this step.

- *Computing Alignment:* Given $N_r$ and $\sigma_r$, approaches like [1] and [14] can be applied to compute alignments. At this point because both $N_r$ and $\sigma_r$ contain abstract events, the computed alignment will have them as well. We call it *macro-alignment*.

- *Alignment Expansion:* For each abstract element of a macro-alignment, the modeled and observed indications are confronted. Needleman-Wunsch algorithm [9] is adapted to compute optimal alignments for these abstracted elements. Section 6 will be centered on this.

It must be stressed that for the proposed framework, obtaining an optimal align-
ment is not guaranteed due to expansion and reduction issues but the experi-
mental outcomes which are presented in Sec. 7 revealed the results are closed to
optimal solutions.

5 Reduction of Model and Observed Behavior

**5.1 The Indication Relation**

Let us consider the model in Fig. 1(a). For any sequence of the model, whenever
transition $t_4$ fires it is clear that transitions $t_1, t_3$, and $t_2$ have fired as well or
firing of $t_8$ indicates that $t_1, t_5$ and $t_7$ must be happened already. Formally:

**Definition 1 (Universal-Indication Relation).** Let $N = \langle P, T, \mathcal{F} \rangle$, $\forall t \in T$, indication is defined as a function, $I(t)$ where, $I: T \rightarrow [P(T)^+]^2$ such that for any sequence $\sigma \in \mathcal{L}(N)$, if $t \in \sigma$ then $I(T) \in \sigma$. If $I(t) = \omega_1\omega_2\dots\omega_n$, then elements of $\omega_m$ precede the elements of $\omega_n$ in $\sigma$ for $1 \le m < n$. It is called linear if it contains only singleton sets, i.e. $\forall \omega_i \in I(t), |\omega_i| = 1$ otherwise it is non-linear.

<footnote n="2">² *P*(*T*) is powerset of the set of transitions of the model.</footnote>
Model reduction can be done through the subclass of universal-indication relation, which is called *flow-indication* relation. Stated formally:

**Definition 2 (Flow-Indication Relation).** Given Def. 1, If $I(t) = \omega_1\omega_2\dots\omega_n$, it represents a flow-indication if and only if, for all consecutive elements $\omega_i$, $\omega_{i+1}$, firing the whole elements of the former enable all elements in the later, exclusively, for $1 \le i < n$.

For example in Fig. 1(a), $I(t_4) = \{t_1\}\{\{t_2\}, \{t_3\}\}\{t_4\}$ (non-linear), which is a flow-indication as well, and $I(t_8) = \{t_1\}\{t_5\}\{t_7\}\{t_8\}$ (linear), but it is not a flow-indication because firing of $t_1$ will not enable $t_5$ exclusively. From now on, because the flow-indication relation is our concern for the remaining parts of the paper, for the sake of simplicity, by indication we mean flow-indication relation, unless otherwise stated explicitly.

<figure><img src="image_6.png" /><figcaption>Fig. 4: Linear SESEs and corresponding reductions.</figcaption></figure>

### 5.1.1 Detecting Flow-Indication Relation through SESE.
SESEs are potential candidates for identifying indication relations inside a WF-net: the exit node of a SESE is the potential indicator of the nodes inside the SESE. Since entry/exit nodes of a SESE can be either place or transitions, SESEs are categorized as $(P, P)$, $(P, T)$, $(T, P)$ or $(T, T)$. In case the SESE is linear, indication relations can be extracted easily and the corresponding SESE is reduced (see Fig. 4).

Non-linear cases are decomposed into linear ones such that indication relations can be computed directly on the linear components extracted. After that, the indication relation of the corresponding linear SESEs are computed and they are reduced as well. This procedure should be done with caution to avoid reaching a deadlock situation. Hence a *deadlock-free post-verification* must be done after reduction of these linear parts. Informally, the verification is only needed for particular type of linear SESEs (($T$, $T$)), and consists on validating the property of the SESE after the reduction. Notice the verification is necessary in these cases because, non-linear SESEs may contain linear universal-indications at nested level, which cannot be extracted as flow-indication relations due to choice or loop constructs. For example in Fig. 5 (a), (b) $t_5$ can not be the indicator of transitions in the corresponding SESEs due to choice and loop structures.
<figure><img src="image_7.png" /><figcaption>Fig. 5: (a) Non-Linear (T,T), (b) Non-Linear (P,T)</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 6: Incorrect indication-based reduction: a deadlock is introduced.</figcaption></figure>

Stated differently, the reduction of non-linear SESEs must be done alongside
by a deadlock-free post-verification; for instance, Fig. 6 shows that in spite of the
indication arising from SESE $S_2$, the net cannot be reduced without changing
the language. To put it another way, this reduction will cause a deadlock in the
reduced model, and hence must be avoided. Looking at the reduced result in
Fig. 6 (b), transition $t_5(\mathit{New})$ never fires because after the reduction it won't
be enabled since $P_4$ never gets marked. To shed more light on the examination
of the deadlock-free post-verification, more details are stated in the following
theorem.

**Theorem 1.** Let $S$ be a reduced linear SESE or the combination of other reduced linear SESEs with entry, exit nodes ($t_u, t_v$) of the (T,T) category. If $\mathit{OUT}(t_u)$ and $\mathit{IN}(t_v)$ represent the set outgoing and incoming arcs of $t_u$ and $t_v$ respectively, then the reduction is deadlock-free if and only if:

$$
a) \forall e \in \mathit{OUT}(t_u), \text{ then } e \in S \qquad b) \forall e \in \mathit{IN}(t_v), \text{ then } e \in S
$$

*Proof.* First of all, assume that the original model before the reduction does not have any deadlock and $T_S$ and $t_{v(New)}$ represent internal transitions of $S$ and the reduced SESE respectively. The proof is presented by contradiction as follows:
Suppose that conditions in Theorem 1 hold and the reduction of *S* causes deadlock in the system. Namely, there is a set of places, *P*<sub>*d*</sub>, which attributes deadlock or in other words *t*<sub>*v(New)*</sub> outputs to one of places in *P*<sub>*d*</sub> and inputs from one of them. Due to the fact that all transitions in *T*<sub>*S*</sub> are internal and do not have direct access to any places in *P*<sub>*d*</sub>, the only incoming and outgoing arcs of *t*<sub>*v(New)*</sub> belong to *t*<sub>*u*</sub> and *t*<sub>*v*</sub> respectively. So it can be concluded that once the places in *P*<sub>*d*</sub> become unmarked they will always be unmarked and neither *t*<sub>*u*</sub> nor *t*<sub>*v*</sub> can place a token in the deadlock, but this contradicts with the assumption that the original model does not have deadlock due to the fact that *IN*(*t*<sub>*u*</sub>) and *OUT*(*t*<sub>*v*</sub>) remain unchanged before and after reduction. Thus the theorem is true. □

<figure><img src="image_9.png" /><figcaption>Fig. 7: Schema for reduction of a WF-net.</figcaption></figure>

The reduction schema is depicted in Fig. 7. From the RPST, a top-down approach is applied that searches for indication-based reductions that do preserve the language of the initial model, once the net is expanded back, i.e., the language of the model must be preserved after reduction.

Notice that the reduction can be applied more than once till saturation (hence the arc back from the node "Reduced WF-net" to the node "WF-net" in Fig. 7).
<figure><img src="image_10.png" /><figcaption>(a)</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(b)</figcaption></figure>

<caption>Fig. 8: (a) Process model, (b) One-time reduced (c) Two-times reduced.</caption>

Fig. 8 shows an example (for the sake of simplicity only linear SESEs are shown). Obviously, SESE $S_2$ is inherently a linear SESE but the rest come from the decomposition of non-linear SESEs. The reduction schema is as follows: Since $S_2$ is inherently a linear SESE, hence it can be reduced easily according to Fig. 4 without any deadlock-free post-verification. The rest of linear SESEs also will be reduced accordingly and the deadlock-free post-verification will be done after each reduction to check that no deadlock arises. One can see all reductions will pass the verification, except for $S_7$, whose reduction induces a deadlock hence must be excluded from abstraction. Applying the reduction once, results in Fig. 8(b). As mentioned earlier, the reduction can be applied more than once until
no reduction can be made. Fig. 8(c) is the reduction of the model in Fig. 8(b) and it is clear that no more reduction can be made from this model.

## 5.2 Reduction of Observed Behavior

Given a reduced model $N_r$ and $\sigma$, we show how to produce $\sigma_r$. We will use the reduced model in Fig. 8(b) and the trace $\sigma_1 = t_1t_5t_3t_{11}t_{10}t_{21}t_6t_2t_7t_{16}t_{25}t_{19}t_{20}t_{26}$. The indication of $t_{5(New)}$ in Fig. 8(b) which is linear, equals to $\{t_5\}\{t_{15}\}$. So the observed indication for this abstract node is $\sigma_{1_{\downarrow I(t_{5(New)})}} = t_5$. After computing the observed indication the reduced trace is $t_1t_{5(New)}t_3t_{11}t_{10}t_{21}t_6t_2t_7t_{16}t_{25}t_{19}t_{20}t_{26}$. For $t_{17(New)}$, $I(t_{17(New)}) = \{t_3\}\{\{t_{10}\}, \{t_{11}\}\}\{t_{17}\}$, which is non-linear and merged of two linear indications, $I_1(t_{17(New)})=\{t_3\}\{t_{10}\}\{t_{17}\}$ and $I_2(t_{17(New)}) = \{t_3\}\{t_{11}\}\{t_{17}\}$. So the projection must be done for each linear indication separately, $\sigma_{1_{\downarrow I_1(t_{17(New)})}} = t_3t_{10}$ and $\sigma_{1_{\downarrow I_2(t_{17(New)})}} = t_3t_{11}$, removing transitions $t_3$, $t_{10}$, $t_{11}$ and $t_{17}$ from the current trace (notice that $t_{17}$ does not appear originally, hence it is not projected). Finally, we need to insert $t_{17(New)}$ into the reduced trace; it will be inserted at the position of $t_{10}$, because the end transition of the abstract node, i.e. $t_{17}$ did not happen in $\sigma$, and $t_{10}$ happened last in $\sigma$. Therefore the reduced trace so far is $t_1t_{5(New)}t_{17(New)}t_{21}t_6t_2t_7t_{16}t_{25}t_{19}t_{20}t_{26}$. By applying this process for the rest of abstract nodes ($t_{16(New)}$, $t_{22(New)}$), we reach $\sigma_r = t_1t_{5(New)}t_{17(New)}t_{21}t_{16(New)}t_{22(New)}t_{26}$.

# 6 Expansion Through Local Optimal Indication Alignments

After reducing a given process model and corresponding observed behavior, we can use current methods for computing alignments [1,14] to align $N_r$ and $\sigma_r$, deriving $\alpha_r$. For example the following is the macro alignment of $\sigma_{1r} = t_1t_{5(New)}t_{17(New)}t_{21}t_{16(New)}t_{22(New)}t_{26}$ and the model in Fig. 8(b) obtained by the approach in [1].

$$ \alpha_r = \frac{\begin{vmatrix} t_1 & t_{5(New)} & t_{17(New)} & t_{21} & \perp & \perp & t_{16(New)} & t_{22(New)} & t_{26} \\ t_1 & \perp & t_{17(New)} & t_{21} & t_{24} & t_{5(New)} & t_{16(New)} & t_{22(New)} & t_{26} \end{vmatrix}}{\begin{vmatrix} t_1 & t_{5(New)} & t_{17(New)} & t_{21} & \perp & \perp & t_{16(New)} & t_{22(New)} & t_{26} \end{vmatrix}} $$

When mapped to linear indications, indication of an abstract node and the corresponding observed indication are both sequence of events; hence for each linear combination of modeled/observed indication, we can adapt the dynamic programming approach from [9] (used in bioinformatics) to align two sequences. As an example, we use indication of $t_{17(New)}$ and its observed indication computed in the previous section.
<figure><img src="image_12.png" /><figcaption>Table 1: Aligning modeled and observed indications</figcaption></figure>

To achieve this goal, we create a table for each linear indication, where the first row and column are filled by observed and abstract node indications respectively, as depicted in Table 1(a), 1(b). The second row and second column are initialized with numbers starting from 0,-1,-2,..., they are depicted in yellow color. The task then is to fill the remaining cells as follows:

$SIM(t_i, t_j) = MAX(SIM(t_{i-1}, t_{j-1}) + s(t_i, t_j), SIM(t_{i-1}, t_j) - 1, SIM(t_i, t_{j-1}) - 1)$
Where $SIM(t_i, t_j)$ represents the similarity score between $t_i$ and $t_j$. $s(t_i, t_j)$ is the substitution score for aligning $t_i$ and $t_j$, it is 0 when they are equal and -1 otherwise.

The final step in the algorithm is the trace back for the best alignment. In the above mentioned example, one can see the bottom right hand corner in for example Table 1, score as -1. The important point to be noted here is that there may be two or more alignments possible between the two example sequences. The current cell with value -1 has immediate predecessor, where the maximum score obtained is diagonally located and its value is 0. If there are two or more values which points back, suggests that there can be two or more possible alignments. By continuing the trace back step by the above defined method, one would reach to the 0th row, 0th column. Following the above described steps, alignment of two sequences can be found.

Alignments can be represented by a sequence of paired elements, for example $\alpha_1 = (t_3, t_3)(t_{11}, t_{11})(\perp, t_{17})$, $\alpha_2 = (t_3, t_3)(t_{10}, t_{10})(\perp, t_{17})$ and final alignment which represent the non-linear indication is $\alpha = (t_3, t_3)\{(t_{11}, t_{11}), (t_{10}, t_{10})\}(\perp, t_{17})$. This information is booked for each abstract node.

After computing local alignments for abstract nodes, we can use them to expand corresponding abstract nodes in a given $\alpha_r$. The policy of expansion depends on whether the abstract node is in synchronous or asynchronous move.

In $\alpha_r$, $t_{17(New)}$ is in a synchronous move so we can expand it by its local alignment, which results in:

$$ \alpha = \begin{vmatrix} t_1 & t_{5(New)} \\ t_1 & \perp \end{vmatrix} = \begin{vmatrix} t_3 & t_{11} & t_{10} & \perp & t_{21} & \perp & \perp & t_{16(New)} & t_{22(New)} & t_{26} \\ t_3 & t_{11} & t_{10} & t_{17} & t_{21} & t_{24} & t_{5(New)} & t_{16(New)} & t_{22(New)} & t_{26} \end{vmatrix} $$

The same story also happens for $t_{16(New)}$ and $t_{22(New)}$, which results in: $\alpha =$

$$ \begin{vmatrix} t_1 & t_{5(New)} & t_3 & t_{11} & t_{10} & \perp & t_{21} & \perp & \perp & t_6 & t_2 & t_7 & \perp & \perp & t_{16} & t_{25} & t_{19} & t_{20} & \perp & t_{26} \\ t_1 & \perp & t_3 & t_{11} & t_{10} & t_{17} & t_{21} & t_{24} & t_{5(New)} & \perp & t_2 & t_7 & t_6 & t_8 & t_{16} & t_{25} & t_{19} & t_{20} & t_{22} & t_{26} \end{vmatrix} $$
On the other hand $t_{5(\text{New})}$ in $\alpha_r$ is a asynchronous move both on the model and observed trace. The policy of expansion is to expand move on log and move on model independently. To put it in another way, move on log will be expanded using observed indication and move on model will be expanded using the abstract node' indication, which results:

$$ \alpha = \frac{\begin{array}{ccccccccccccccccc} t_1 & \textcolor{yellow}{t_5} & t_3 & t_{11} & t_{10} & \bot & t_{21} & \bot & \bot & \bot & t_6 & t_2 & t_7 & \bot & \bot & t_{16} & t_{25} & t_{19} & t_{20} & \bot & t_{26} \\ t_1 & \bot & t_3 & t_{11} & t_{10} & t_{17} & t_{21} & t_{24} & \textcolor{yellow}{t_{15}} & \textcolor{yellow}{t_5} & \bot & t_2 & t_7 & t_6 & t_8 & t_{16} & t_{25} & t_{19} & t_{20} & t_{22} & t_{26} \end{array}}{\begin{array}{ccccccccccccccccc} t_1 & \textcolor{yellow}{t_5} & t_3 & t_{11} & t_{10} & \bot & t_{21} & \bot & \bot & \bot & t_6 & t_2 & t_7 & \bot & \bot & t_{16} & t_{25} & t_{19} & t_{20} & \bot & t_{26} \\ t_1 & \bot & t_3 & t_{11} & t_{10} & t_{17} & t_{21} & t_{24} & \textcolor{yellow}{t_{15}} & \textcolor{yellow}{t_5} & \bot & t_2 & t_7 & t_6 & t_8 & t_{16} & t_{25} & t_{19} & t_{20} & t_{22} & t_{26} \end{array}} $$

# 7 Experiments

The technique presented in this paper has been implemented in Python as a prototype tool. The tool has been evaluated over different family of examples with variety of difficulties, alongside with the state of the art techniques for computing alignments [14] (ILP.R), [1] ($A^*$). We used benchmark datasets from [14], [7], and new generated datasets.

**Reduction of Models.** Table 2 provides the results of one-time reduction by applying the proposed method to benchmark datasets. Significant reductions are found often. Obviously one can see that the results of reduction are more representative for models without loops like (prAm6,...,prGm6) or for models that contain small loops, like (Banktransfer).

<table><caption>Table 2: Reduced benchmark datasets</caption><thead><tr><th>Model</th><th>|P|<br>(Before)</th><th>|T|<br>(Before)</th><th>|Arc|<br>(Before)</th><th>|σ<sub>avg</sub>|<br>(Before)</th><th>|P|<br>(After)</th><th>|T|<br>(After)</th><th>|Arc|<br>(After)</th><th>|σ<sub>avg</sub>|<br>(After)</th></tr></thead><tbody><tr><td>prAm6</td><td>363</td><td>347</td><td>846</td><td>31</td><td>175(52%)</td><td>235(32%)</td><td>498</td><td>22(29%)</td></tr><tr><td>prBm6</td><td>317</td><td>317</td><td>752</td><td>43</td><td>188(40%)</td><td>225(29%)</td><td>490</td><td>33(23%)</td></tr><tr><td>prCm6</td><td>317</td><td>317</td><td>752</td><td>42</td><td>188(40%)</td><td>225(29%)</td><td>490</td><td>33(21%)</td></tr><tr><td>prDm6</td><td>529</td><td>429</td><td>1140</td><td>248</td><td>270(49%)</td><td>248(42%)</td><td>618</td><td>148(40%)</td></tr><tr><td>prEm6</td><td>277</td><td>275</td><td>652</td><td>98</td><td>180(35%)</td><td>205(26%)</td><td>454</td><td>75(23%)</td></tr><tr><td>prFm6</td><td>362</td><td>299</td><td>772</td><td>240</td><td>181(50%)</td><td>172(42%)</td><td>406</td><td>137(42%)</td></tr><tr><td>prGm6</td><td>357</td><td>335</td><td>826</td><td>143</td><td>195(45%)</td><td>221(34%)</td><td>498</td><td>94(34%)</td></tr><tr><td>M<sub>1</sub></td><td>40</td><td>39</td><td>92</td><td>13</td><td>25(37%)</td><td>28(28%)</td><td>62</td><td>9(30%)</td></tr><tr><td>M<sub>2</sub></td><td>34</td><td>34</td><td>80</td><td>17</td><td>26(23%)</td><td>28(18%)</td><td>64</td><td>13(23%)</td></tr><tr><td>M<sub>3</sub></td><td>108</td><td>123</td><td>276</td><td>37</td><td>76(30%)</td><td>98(20%)</td><td>212</td><td>29(21%)</td></tr><tr><td>M<sub>4</sub></td><td>36</td><td>52</td><td>106</td><td>26</td><td>31(14%)</td><td>48(8%)</td><td>96</td><td>23(11%)</td></tr><tr><td>M<sub>5</sub></td><td>35</td><td>33</td><td>78</td><td>34</td><td>27(23%)</td><td>27(18%)</td><td>62</td><td>28(18%)</td></tr><tr><td>M<sub>6</sub></td><td>69</td><td>72</td><td>168</td><td>53</td><td>51(26%)</td><td>59(18%)</td><td>132</td><td>43(19%)</td></tr><tr><td>M<sub>7</sub></td><td>65</td><td>62</td><td>148</td><td>37</td><td>43(34%)</td><td>46(26%)</td><td>104</td><td>28(24%)</td></tr><tr><td>M<sub>8</sub></td><td>17</td><td>15</td><td>36</td><td>17</td><td>6(65%)</td><td>7(53%)</td><td>14</td><td>9(47%)</td></tr><tr><td>M<sub>9</sub></td><td>47</td><td>55</td><td>120</td><td>44</td><td>26(45%)</td><td>39(29%)</td><td>78</td><td>34(23%)</td></tr><tr><td>M<sub>10</sub></td><td>150</td><td>146</td><td>354</td><td>58</td><td>91(39%)</td><td>105(28%)</td><td>236</td><td>42(28%)</td></tr><tr><td>Bank-transfer</td><td>121</td><td>114</td><td>272</td><td>58</td><td>61(46%)</td><td>72(37%)</td><td>152</td><td>38(34%)</td></tr></tbody></table>

**Executable Property of Alignments.** Since the alignment technique ILP.R may be approximate or the results contain spurious elements, Table 3 provides an overview of how many of the computed alignments can be replayed for ILP.R method when combined with the technique of this paper. Also the correspond-
<table><caption>Table 3: Replaying of Computed Step-Sequences</caption><thead><tr><th>Model</th><th>Cases</th><th>Replay<br>%<br>(Before)<br>ILP.R</th><th>Replay<br>%<br>(After)<br>ILP.R</th><th>Replay<br>%<br>(Before)<br>A*</th><th>Replay<br>%<br>(After)<br>A*</th></tr></thead><tbody><tr><td>prAm6</td><td>1200</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>prBm6</td><td>1200</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>prCm6</td><td>500</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>prDm6</td><td>1200</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>prEm6</td><td>1200</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>prFm6</td><td>1200</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>prGm6</td><td>1200</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>M<sub>1</sub></td><td>500</td><td>94.2%</td><td>86%</td><td>100%</td><td>100%</td></tr><tr><td>M<sub>2</sub></td><td>500</td><td>95.4%</td><td>86.2%</td><td>100%</td><td>100%</td></tr><tr><td>M<sub>3</sub></td><td>500</td><td>98%</td><td>88.8%</td><td>100%</td><td>100%</td></tr><tr><td>M<sub>4</sub></td><td>500</td><td>90%</td><td>81%</td><td>100%</td><td>100%</td></tr><tr><td>M<sub>5</sub></td><td>500</td><td>94.8%</td><td>95.2%</td><td>100%</td><td>100%</td></tr><tr><td>M<sub>6</sub></td><td>500</td><td>98.6%</td><td>90.8%</td><td>100%</td><td>100%</td></tr><tr><td>M<sub>7</sub></td><td>500</td><td>97.2%</td><td>96%</td><td>100%</td><td>100%</td></tr><tr><td>M<sub>8</sub></td><td>500</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>M<sub>9</sub></td><td>500</td><td>100%</td><td>98.8%</td><td>100%</td><td>100%</td></tr><tr><td>M<sub>10</sub></td><td>500</td><td>100%</td><td>99.8%</td><td>100%</td><td>100%</td></tr><tr><td>Bank-<br>transfer</td><td>2000</td><td>97.25%</td><td>88.9%</td><td>100%</td><td>100%</td></tr></tbody></table>

ing results for the technique in [1] are presented as well. One can see that the expanded alignments provided by A* were replayed 100% for all datasets.

<table><caption>Table 4: Quality of Computed Step-Sequences</caption><thead><tr><th>Model</th><th>ED<br>(A*vs<br>EXP.R.A*)</th><th>Jaccard<br>(A*vs<br>EXP.R.A*)</th><th>MSE<br>(A*vs<br>EXP.R.A*)</th><th>ED<br>(ILP.R vs<br>EXP.R.ILP.R)</th><th>Jaccard<br>(ILP.R vs<br>EXP.R.ILP.R)</th><th>MSE<br>(ILP.R vs<br>EXP.R.ILP.R)</th></tr></thead><tbody><tr><td>prAm6</td><td>7.49</td><td>0</td><td>0.065</td><td>9.25</td><td>0.017</td><td>0.00081</td></tr><tr><td>prBm6</td><td>7.87</td><td>0</td><td>0</td><td>18.31</td><td>0</td><td>0</td></tr><tr><td>prCm6</td><td>8.65</td><td>0.016</td><td>0.005</td><td>11.60</td><td>0.0019</td><td>0.00646</td></tr><tr><td>prDm6</td><td>NA</td><td>NA</td><td>NA</td><td>93.28</td><td>0.0101</td><td>0.00041</td></tr><tr><td>prEm6</td><td>37.14</td><td>0</td><td>0.02</td><td>37</td><td>0</td><td>0</td></tr><tr><td>prFm6</td><td>NA</td><td>NA</td><td>NA</td><td>67</td><td>0.013</td><td>0.0074</td></tr><tr><td>prGm6</td><td>NA</td><td>NA</td><td>NA</td><td>77</td><td>0.011</td><td>0.00064</td></tr><tr><td>M<sub>1</sub></td><td>4</td><td>0.085</td><td>0.021</td><td>4</td><td>0.025</td><td>0.0165</td></tr><tr><td>M<sub>2</sub></td><td>6</td><td>0.012</td><td>0.0193</td><td>6</td><td>0</td><td>0.018</td></tr><tr><td>M<sub>3</sub></td><td>8</td><td>0.046</td><td>0.021</td><td>5</td><td>0.011</td><td>0.016</td></tr><tr><td>M<sub>4</sub></td><td>4</td><td>.12</td><td>0.028</td><td>2</td><td>0.015</td><td>0.025</td></tr><tr><td>M<sub>5</sub></td><td>11</td><td>0.0022</td><td>0.0045</td><td>15</td><td>0.00024</td><td>0.0103</td></tr><tr><td>M<sub>6</sub></td><td>NA</td><td>NA</td><td>NA</td><td>12</td><td>0.0012</td><td>0.0088</td></tr><tr><td>M<sub>7</sub></td><td>NA</td><td>NA</td><td>NA</td><td>15</td><td>0.0027</td><td>0.019</td></tr><tr><td>M<sub>8</sub></td><td>4</td><td>0.073</td><td>0.039</td><td>4</td><td>0.0078</td><td>0.035</td></tr><tr><td>M<sub>9</sub></td><td>NA</td><td>NA</td><td>NA</td><td>3</td><td>0.0044</td><td>0.0085</td></tr><tr><td>M<sub>10</sub></td><td>NA</td><td>NA</td><td>NA</td><td>13</td><td>0.00038</td><td>0.012</td></tr><tr><td>Bank-<br>transfer</td><td>18</td><td>0.031</td><td>0.025</td><td>13</td><td>0.0118</td><td>0.0067</td></tr></tbody></table>
*Comparing with Original Alignments.* Table 4 reports the evaluation of the quality of the results for both approaches [1], [14] with and without applying the technique of this paper. Columns ED/Jaccard report the edit/Jaccard distances between the sequences computed, while (Mean Square Error) MSE columns report the mean square error between the corresponding fitness values. Edit distances are often large, but interestingly this has no impact on the fitness, since when expanding abstract nodes although the final position may differ, the model still can replay the obtained sequences very often.

<table><caption>Table 5: The Average of Required Variables for ILP.R</caption><thead><tr><th>Model</th><th>Var<sub>avg</sub><br>(Before)</th><th>Var<sub>avg</sub><br>(After)</th><th>Model</th><th>Var<sub>avg</sub><br>(Before)</th><th>Var<sub>avg</sub><br>(After)</th></tr></thead><tbody><tr><td>prAm6</td><td>10757</td><td>5170 (52%)</td><td>M<sub>2</sub></td><td>578</td><td>364 (37%)</td></tr><tr><td>prBm6</td><td>13631</td><td>7425 (45%)</td><td>M<sub>3</sub></td><td>4551</td><td>2842 (37%)</td></tr><tr><td>prCm6</td><td>13314</td><td>7425 (44%)</td><td>M<sub>4</sub></td><td>1352</td><td>1104 (18%)</td></tr><tr><td>prDm6</td><td>106392</td><td>36704 (65%)</td><td>M<sub>5</sub></td><td>1122</td><td>756 (32%)</td></tr><tr><td>prEm6</td><td>26950</td><td>15375 (43%)</td><td>M<sub>6</sub></td><td>3816</td><td>2537 (33%)</td></tr><tr><td>prFm6</td><td>71760</td><td>23564 (67%)</td><td>M<sub>7</sub></td><td>2294</td><td>1288 (44%)</td></tr><tr><td>prGm6</td><td>47905</td><td>20774 (56%)</td><td>M<sub>8</sub></td><td>255</td><td>63 (75%)</td></tr><tr><td>banktransfer</td><td>6612</td><td>2736 (58%)</td><td>M<sub>9</sub></td><td>2420</td><td>1326 (45%)</td></tr><tr><td>M<sub>1</sub></td><td>507</td><td>252 (50%)</td><td>M<sub>10</sub></td><td>8468</td><td>4410 (48%)</td></tr></tbody></table>

*Memory Usage.* By one-time reduction, the memory usage<fnref n="3" /> of computing alignments using [1], is reduced significantly. See Fig. 9(a)-(b) which represents the required memory for [1] without and with using the proposed framework respectively. For large models, *prDm6*, *prFm6*, *prGm6*, it can only compute alignments if applied in combination with the technique of this paper otherwise it runs out of memory for the machine by which the experiment are done, denoted by (> 5500 MB) in Fig. 9 (a), (b). For the approach in [14], due to the fact that it is based on Integer Linear Programming (ILP), to accentuate the effect of reduction, the evaluation was done based on number of required variables for computing alignments with and without the proposed approach. The results in Table 5⁴ represent, in average, significant reduction to the number of variables when an ILP instance needs to be solved a given problem.

<footnote n="3">³ Each dataset during its execution was monitored every 0.15 seconds, and the portion of memory occupied by the corresponding process that is held in main memory (RSS) was booked. Based on the gathered data 95% CI was computed.</footnote>

<footnote n="4">⁴ For a given model with $|T|$ transitions and an event log $\sigma$, the required number of variables for the ILP based technique in [14] is $\Theta(|\sigma| \times |T|)$, totally.</footnote>
<figure><img src="image_13.png" /><figcaption>Fig. 9: Memory Usage for [1] (a) Before Reduction and (b) After Reduction</figcaption></figure>

*Computation Time Comparison.* Fig. 10, 11 (a)-(b) report execution times for BPM-2013 and other benchmark datasets for the computation of alignments by techniques in [1] and [14] with and without using the presented technique in this paper (denoted by *EXP.R.*) respectively. It is evident that *A*\* approach combined with the proposed method is significantly faster than the other approach in nearly all datasets except (*prGm6*, *prDm6*, *M*<sub>6</sub>, *M*<sub>10</sub>). Still *A*\* approach cannot compute alignments for models *M*<sub>6</sub> and *M*<sub>10</sub> even after applying the presented technique, which are denoted by (N/A), and in that case the combination of *ILP.R* with the presented technique is the best choice.
<figure><img src="image_14.png" /><figcaption>Fig. 10: (a) BPM-2013 datasets [7], (b) Synthetic datasets</figcaption></figure>
<figure><img src="image_15.png" /><figcaption>Fig. 11: (a) BPM-2013 datasets [7], (b) Synthetic datasets</figcaption></figure>

# 8 Conclusion and Future Work

We have presented a technique that can be used to significantly alleviate the complexity of computing alignments. The technique uses the indication relation to abstract unimportant parts of a process model so that global computation of alignments focus on a reduced instance. The reduced part of computed alignments then will be expanded to represent local deviations as well. Experiments
are provided that witness the capability of the technique when used in combi-
nation with state-of-the-art approaches for alignment computation. Future work
will be devoted to apply the technique on more unstructured inputs and exam-
ining other methods to extract indication relations more efficiently.

**Acknowledgments.** This work was supported by the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant COMMAS (ref. TIN2013-46181-C2-1-R).

References

1. Arya Adriansyah. *Aligning observed and modeled behavior*. PhD thesis, Technische Universiteit Eindhoven, 2014.

2. Arya Adriansyah, Jorge Munoz-Gama, Josep Carmona, Boudewijn F. van Dongen, and Wil M. P. van der Aalst. Measuring precision of modeled behavior. *Inf. Syst. E-Business Management*, 13(1):37–67, 2015.

3. Sandie Balaguer, Thomas Chatain, and Stefan Haar. Building occurrence nets from reveals relations. *Fundam. Inform.*, 123(3):245–272, 2013.

4. J. M. Colom, E. Teruel, M. Silva, and S. Haddad. *Structural Methods*, pages 277–316. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003.

5. Stefan Haar. Unfold and Cover: Qualitative Diagnosability for Petri Nets. In *Proceedings of the 46th IEEE Conference on Decision and Control (CDC'07)*, pages 1886–1891, New Orleans, LA, USA, United States, 2007. IEEE Control System Society.

6. Richard Johnson, David Pearson, and Keshav Pingali. The program structure tree: Computing control regions in linear time. *SIGPLAN Not.*, 29(6):171–185, June 1994.

7. Jorge Munoz-Gama, Josep Carmona, and Wil M. P. Van Der Aalst. Single-entry single-exit decomposed conformance checking. *Inf. Syst.*, 46:102–122, December 2014.

8. T. Murata. Petri nets: Properties, analysis and applications. *Proceedings of the IEEE*, 77(4):541–574, April 1989.

9. Saul B. Needleman and Christian D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. *Journal of Molecular Biology*, 48(3):443–453, 1970.

10. James Lyle Peterson. *Petri Net Theory and the Modeling of Systems*. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1981.

11. Artem Polyvyanyy, Sergey Smirnov, and Mathias Weske. *The Triconnected Abstraction of Process Models*, pages 229–244. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.

12. Artem Polyvyanyy, Jussi Vanhatalo, and Hagen Völzer. Simplified computation and generalization of the refined process structure tree. In *7th International Conference on Web Services and Formal Methods*, WS-FM'10, pages 25–41, Berlin, Heidelberg, 2011.

13. Robert E. Tarjan and Jacobo Valdes. Prime subprogram parsing of a program. In *Proceedings of the 7th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages*, POPL '80, pages 95–105, New York, NY, USA, 1980. ACM.
14. Farbod Taymouri and Josep Carmona. A recursive paradigm for aligning observed behavior of large structured process models. In *14th International Conference of Business Process Management (BPM), Rio de Janeiro, Brazil, September 18 - 22, 2016*.

15. Wil M. P. van der Aalst. *Process Mining - Discovery, Conformance and Enhancement of Business Processes*. Springer, 2011.

16. Boudewijn van Dongen, Josep Carmona, Thomas Chatain, and Farbod Taymouri. Aligning modeled and observed behavior: A compromise between complexity and quality. In Eric Dubois and Klaus Pohl, editors, *Proceedings of the 29th International Conference on Advanced Information Systems Engineering (CAiSE'17)*, volume 10253 of *Lecture Notes in Computer Science*, Essen, Germany, June 2017. Springer. To appear.

17. Jussi Vanhatalo, Hagen Völzer, and Jana Koehler. The refined process structure tree. In *Proceedings of the 6th International Conference on Business Process Management, BPM '08*, pages 100–115, Berlin, Heidelberg, 2008. Springer-Verlag.

18. H. M. W. Verbeek and W. M. P. van der Aalst. *Merging Alignments for Decomposed Replay*, pages 219–239. Springer International Publishing, Cham, 2016.

19. Matthias Weidlich, Artem Polyvyanyy, Jan Mendling, and Mathias Weske. Causal behavioural profiles - efficient computation, applications, and evaluation. *Fundam. Inf.*, 113(3-4):399–435, August 2011.