Mathilde Boltenhagen
email: boltenhagen@lsv.fr

Thomas Chatain
email: chatain@lsv.fr

Josep Carmona
email: jcarmona@cs.upc.edu

Model-Based Trace Variant Analysis of Event Logs

Keywords: Conformance Checking, Trace Variant Analysis, SAT, Process Mining

The comparison of trace variants of business processes opens the door for a fine-grained analysis of the distinctive features inherent in the executions of a process in an organization. The current approaches for trace variant analysis do not consider the situation where a process model is present, and therefore, it can guide the derivation of the trace variants by considering high-level structures present in the process model. In this paper we propose a fresh alternative to trace variant analysis, which proposes a generalized notion of trace variant that incorporates concurrency and iteration. This way, the analyst may be relieved from analysing trace variants that are essentially the same, if these aspects are disregarded. We propose a general algorithm for model based trace variant analysis which is grounded in encoding the problem into SAT, and a family of heuristic alternatives including a very light sampling technique that represents a good trade-off between quality of the trace variants identified, and the complexity of the analysis. All the techniques of the paper are implemented in two open-source tools, and experiments with publicly available benchmarks are reported.

Introduction

One of the key factors that explain the success of current process mining technology is the ability to extract from an event log, which can contain millions of traces, these representative traces that embed a particular way of executing a process. These representatives, known as trace variants, denote unique control-flow complete trajectories of a process model, i.e., each trace variant is a unique string formed by the concatenation of the sequence of tasks representing a process instance (or case). Thus, the analyst can then drill-down the analysis to be performed per trace variant, e.g., extracting insights arising from the other data attributes existing in the event log, so that one can see general rules that explain the traces represented by a certain variant (e.g., see [START_REF] Poelmans | Combining business process and data discovery techniques for analyzing and improving integrated care pathways[END_REF]). Alternatively, other valuable information can be extracted by analyzing the differences between trace variants, a problem that has been considered recently both from the algorithmic perspective [START_REF] Nick | Log delta analysis: Interpretable differencing of business process event logs[END_REF][START_REF] Cordes | A generic approach for calculating and visualizing differences between process models in multidimensional process mining[END_REF][START_REF] Pai Ballambettu | Analyzing process variants to understand differences in key performance indices[END_REF][START_REF] Bolt | Process variant comparison: Using event logs to detect differences in behavior and business rules[END_REF][START_REF] Taymouri | Business process variant analysis: Survey and classification[END_REF], but also for its application in certain domains [START_REF] Swinnen | A process deviation analysis -a case study[END_REF][START_REF] Suriadi | Measuring patient flow variations: A crossorganisational process mining approach[END_REF].

The event log partition by trace variants facilitates the analysis of real process executions, specially when a human is involved: by structuring a complex behavior into clusters, she can then work at a different abstraction level. In the ideal case, where few trace variants are identified, this process is clearly alleviated. However, when the process represented contains repetitions of certain activity fragments, the current approaches for trace variant analysis will be very sensitive to this phenomena. For instance, imagine the process of purchasing a certain item in an online shop; the fragment of the process that considers filling the form for the credit card number needs sometimes to be executed once, twice, three, ... several times. But all these different executions are not semantically different, they somehow, encode the buyer's ability in typing correctly her correct credit card number. A similar situation arises when certain fragments of a process can be executed concurrently; in this case, the process does not impose a particular ordering of the activities affected, although each ordering will be regarded as a different trace variant by current process mining tools.

In this paper we propose a radically different approach for trace variant analysis. We assume that a process model exists. This assumption is realistic in many contexts, e.g., in Process-Aware Information Systems (PAIS), process models are often available [START_REF]Process-Aware Information Systems: Bridging People and Software Through Process Technology[END_REF]. The quality of a process model can be first analyzed with conformance checking techniques [START_REF] Carmona | Conformance Checking -Relating Processes and Models[END_REF], so that one can assume a certain validity and representativity of the process model used. The intuitive idea of our approach is to identify subnets of the process model that can serve as trace variant, so that different traces that are very distant when considered as words (like in the example of the credit card payment), will align similarly to the subnet representing a variant. Algorithmically, we compute the subnets corresponding the trace variants by encoding the problem as a SAT instance, following our previous work [START_REF] Chatain | Alignment-based trace clustering[END_REF][START_REF] Boltenhagen | Generalized alignment-based trace clustering of process behavior[END_REF]. Moreover, to enable the application of the technique for large problem instances, we present a sampling strategy. We provide some statistical guarantees that all traces sufficiently close to the model will be clustered after a certain number of trials.

The contributions of this paper are incorporated into two open-source tools, and the experiments provided both with synthetic and realistic benchmarks witness the ability in detecting meaningful trace variants corresponding to concurrent or repetitive process that can also be large and/or noisy.

A motivating example

Let us illustrate the main message of this paper with the process represented by the model shown in Figure 1. This is a synthetic process where, after some common activity is executed, 10 branches are possible, each one enabling at isolation concurrent and loop behavior. Once the executed branch terminates, a common activity is executed. Although this process has a very clear structure, it is very likely that an event log for this process models has a high number of trace variants. In fact, after simulating the model to obtain 500 traces, we obtained 411 trace variants in any of the commercial tools available. However, if our generalized notion of trace variants is used, which considers subnets of the process model instead of traces in the event log, 10 variants are considered (each for each subnet a i, for 0 ≤ i ≤ 9). This paper is organized as follows: next section provides an overview of the current state-of-the-art approaches for trace variant analysis but also related topics. In section 3 the necessary preliminaries for this paper are provided.

Then in section 4 we describe the different forms of trace variants proposed, whilst in section 6 it is formally shown how these can be computed. Strategies to fight the complexity of the problem are described in section 7. Section 8 reports experiments and section 9 concludes the paper.

Related work.

A complete and detailed review of trace variant analysis can be found in [START_REF] Taymouri | Business process variant analysis: Survey and classification[END_REF].

The work by van Beest et al. [START_REF] Nick | Log delta analysis: Interpretable differencing of business process event logs[END_REF] relies on the product automaton of two event structures to distill all the behavioral differences between two process variants y 0, a 0 0, a 0 1, a 0 2, a 0 3, z 0 y 0, a 0 1, a 0 0, a 0 2, a 0 3, z 0 y 0, a 1 2, a 1 0, a 1 3, a 1 1, z 0 y 0, a 1 3, a 1 1, a 1 2, a 1 0, z 0 y 0, a 0 1, a 0 0, a 0 2, a 0 3, a 0 1, a 0 0, a 0 2, a 0 3, z 0 y 0, a 9 0, a 9 1, a 9 3, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 y 0, a 9 0, a 9 3, a 9 1, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 y 0, a 0 1, a 0 1, a 0 2, a 0 2, a 0 3, z 0 from the respective event logs, and render these differences to end users via textual explanations. Cordes et al. [START_REF] Cordes | A generic approach for calculating and visualizing differences between process models in multidimensional process mining[END_REF] discover two process models and their differences are defined as the minimum number of operations that transform on model to the other. This work was extended in [START_REF] Pai Ballambettu | Analyzing process variants to understand differences in key performance indices[END_REF] to compare process variants using annotated transition systems. Pini et al. [START_REF] Pini | Process visualization techniques for multi-perspective process comparisons[END_REF] contribute a visualization technique that compares two discovered process models in terms of performance data. The work in [START_REF] Wynn | Processprofiler3d: A visualisation framework for log-based process performance comparison[END_REF] proposes an extension of this work, by considering a normative process model alongside with event logs as inputs, and adding more data preparation facilities. This work is the only one in the literature that like us, considers the process model as input, but it uses the process model merely to compute alignments with the aim of computing performance information.

The works by Bolt et al. and Nguyen et al. are grounded on statistical significance. Bolt et al. [START_REF] Bolt | A visual approach to spot statistically-significant differences in event logs based on process metrics[END_REF] use an annotated transition system to highlight the differences between process variants. The highlighted parts only show different dominant behaviors that are statistically significant with respect to edge frequencies. This work was later extended in [START_REF] Bolt | Process variant comparison: Using event logs to detect differences in behavior and business rules[END_REF], by inducting decision trees for performance data among process variants. Nguyen et al. [START_REF] Hoang Huy Nguyen | Multi-perspective comparison of business process variants based on event logs[END_REF] encode process variants into Perspective Graphs. The comparison of perspective graphs results in a Differential Graph, which is a graph that contains common nodes and edges, and also nodes and edges that appear in one perspective graph only.

An approach very related to trace variant analysis is trace clustering.

Several techniques have been proposed in the last decade for trace cluster-ing [START_REF] Greco | Discovering expressive process models by clustering log traces[END_REF][START_REF] Diogo | Approaching process mining with sequence clustering: Experiments and findings[END_REF][START_REF] Song | Trace clustering in process mining[END_REF][START_REF] Jagadeesh | Context aware trace clustering: Towards improving process mining results[END_REF][START_REF] Jagadeesh | Trace clustering based on conserved patterns: Towards achieving better process models[END_REF][START_REF] De Weerdt | Active trace clustering for improved process discovery[END_REF][START_REF] Hompes | Discovering deviating cases and process variants using trace clustering[END_REF][START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF]. They can be partitioned into vector space approaches [START_REF] Greco | Discovering expressive process models by clustering log traces[END_REF][START_REF] Song | Trace clustering in process mining[END_REF][START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF], context aware approaches [START_REF] Jagadeesh | Context aware trace clustering: Towards improving process mining results[END_REF][START_REF] Jagadeesh | Trace clustering based on conserved patterns: Towards achieving better process models[END_REF] and model-based approaches [START_REF] Diogo | Approaching process mining with sequence clustering: Experiments and findings[END_REF][START_REF] De Weerdt | Active trace clustering for improved process discovery[END_REF][START_REF] Hompes | Discovering deviating cases and process variants using trace clustering[END_REF]. All the aforementioned clustering algorithms consider only the event log as input, and use different internal representations for producing the clusters. In contrast, in a recent paper [START_REF] Chatain | Alignment-based trace clustering[END_REF], we presented a different view on clustering event log traces, by assuming that a process model exists.

All the aforementioned techniques do not allow concurrency or loop behavior.

Perhaps the closest work is [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF], which extracts, together with the clusters, Super-Instances that are representatives of the discovered groups of traces. The method creates n-grams, i.e., sub-sequences of size n, which are considered as features in their vector-shape approach. They use a Principal Component Analysis (PCA) technique combined with the K-means algorithm, thus using the Euclidean distance. The Super-Instances are then mean of the input log, and can be used as representative, e.g., variants. In the experimental evaluation, we provide a detailed comparison with this closest work.

The use of an explicit characterization of concurrency has been considered

recently in process discovery: the works in [START_REF] Ponce De León | Unfolding-based process discovery[END_REF][START_REF] Ponce De León | POD -A tool for process discovery using partial orders and independence information[END_REF] show how to improve the discovery of a process model by folding the initial unfolding that satisfies the independence relations given as inputs. In the area of conformance checking, the same phenomena has been observed: the work in [START_REF] Lu | Conformance checking based on partially ordered event data[END_REF] assumes traces are represented as partial order, thus allowing again an explicit characterization of concurrency in the problem formalization.

The trace clustering works also very similar to the one of this paper are [START_REF] De | Mining structured Petri nets for the visualization of process behavior[END_REF][START_REF] Mokhov | Process windows[END_REF], where a transition system representing the event log is clustered, so that a set of simpler process models is generated. Tailored state-based properties that guarantee certain Petri net classes are used to guide the clustering, whereas in this work the computation of subnets is unrestricted. Our work is also related to [START_REF] Lu | Detecting deviating behaviors without models[END_REF] which clusters events and detects deviation. However, our work focuses on an existing model and the results may consider different directions like repairs while [START_REF] Lu | Detecting deviating behaviors without models[END_REF] gives a pre-processing of data.

Complexity of our works is related to [START_REF] Benedikt | Regular repair of specifications[END_REF] which demonstrates several methods for distance between automata. Even for dynamic functions, the complexity have been proved PSPACE-complete and is even more complex for Petri nets which is formalism used in this paper.

Preliminaries

In this section, we introduce the main definitions required to understand the content of this paper from trace variants to model-based clustering.

Log Traces, Process Models, Alignment-based Clustering

Definition 1 (Log Trace). A log trace over an alphabet of activity names Σ is a finite word σ ∈ Σ * that corresponds to an event sequence.

A log is a collection of log traces. Fig. 2 shows an example of log traces of recorded behaviors.

Classically, some log traces appear many times in the log: this simply means that they correspond to frequent behavior. For this reason, one usually groups equivalent log traces together and consider them as several instances of the same log trace, called a trace variant [START_REF] Taymouri | Business process variant analysis: Survey and classification[END_REF]. In this paper we will propose richer notions of trace variants, obtained by clustering methods. The aim is to present to stakeholders a reduced number of trace variants, in order to make them easier to interpret. Definition 2 (Trace Clustering). Given a log L, a trace clustering over L is a partition over a (possibly proper) subset of the traces in L.

Alignment-based trace clustering is a particular form of trace clustering: it relies on a model N of the observed system. We assume process models are described as Petri nets [START_REF] Murata | Petri nets: Properties, analysis and applications[END_REF]. Formally: Definition 3 (Process Model (Labeled Petri Net)). A Process Model defined by a labeled Petri net system (or simply Petri net) is a tuple N = P, T, F, m 0 , m f , Σ, λ , where P is the set of places, T is the set of transitions (with P ∩ T = ∅), F ⊆ (P × T ) ∪ (T × P ) is the flow relation, m 0 is the initial marking, m f is the final marking, Σ is an alphabet of actions and λ : T → Σ ∪ {τ } labels every transition by an action or as silent.

The semantics of Petri nets is given in term of firing sequences. Given a node

x ∈ P ∪ T , we define its pre-set • x def = {y ∈ P ∪ T | (y, x) ∈ F } and its post-set Examples for the model of Fig. 1 are y 0, a 0 2, a 0 0, a 0 3, a 0 1, z 0 , y 0, a 1 3, a 1 0, a 1 2, a 1 1, z 0 , y 0, a 9 2, a 9 0, a 9 3, a 9 1, a 9 1, a 9 0, a 9 3, a 9 2, z 0 .

x • def = {y ∈ P ∪ T | (x, y) ∈ F }. A
Definition 5 (Alignment-based Trace Clustering (ATC) [START_REF] Chatain | Alignment-based trace clustering[END_REF]). Traces y 0, a 0 0, a 0 1, a 0 2, a 0 3, z 0 y 0, a 0 0, a 0 1, a 0 2, a 0 3, z 0 y 0, a 0 1, a 0 0, a 0 2, a 0 3, z 0 y 0, a 1 2, a 1 0, a 1 3, a 1 1, z 0 y 0, a 1 2, a 1 0, a 1 3, a 1 1, z 0 y 0, a 1 3, a 1 1, a 1 2, a 1 0, z 0 y 0, a 1 3, a 1 1, a 1 2, a 1 0, z 0 y 0, a 0 1, a 0 0, a 0 2, a 0 3, a 0 1, a 0 0, a 0 2, a 0 3, z 0 y 0, a 0 1, a 0 0, a 0 2, a 0 3, a 0 1, a 0 0, a 0 2, a 0 3, z 0 y 0, a 9 0, a 9 1, a 9 3, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 y 0, a 9 0, a 9 1, a 9 3, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 y 0, a 9 0, a 9 3, a 9 1, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 nc y 0, a 0 1, a 0 1, a 0 2, a 0 2, a 0 3, z 0 χ : L → {nc, u 1 . . . u m } maps log traces either to the centroid of its cluster χ(σ), or to none of the clusters, denoted by nc.

Each set χ -1 (u i ), for i ∈ {1 . . . m}, defines the cluster whose centroid is u i . The

Quality of an ATC

To get a good clustering as presented in Tab. 1, there exist several criteria that have been introduced in [START_REF] Boltenhagen | Generalized alignment-based trace clustering of process behavior[END_REF]. Obviously, a first criterion is the number of clustered traces: a good ATC should cluster as many traces as possible. A second criterion is the quality of the alignment between every log trace σ ∈ L and the centroid of its cluster u = χ(σ) as we use them as model-based trace variants. This criterion can be quantified as:

max σ∈L,χ(σ) =nc dist(σ, λ(χ(σ))) (1)
where dist is a distance function between words. A good ATC minimizes this quantity. In this paper, we use Levenshtein's edit distance, which is usually considered appropriate in Process Mining.

Definition 6 (Levenshtein's edit distance). Levenshtein's edit distance dist L (w1, w2) between two words w 1 and w 2 ∈ Σ * is the minimal number of edits needed to transform w 1 to w 2 . Editions can be substitutions to a letter by another one, deletions or additions of a letter in words.

We will abuse notations, and write dist L (σ, u) for dist L (σ, λ(u)),

and dist L (u 1 , u 2 ) for dist L (λ(u 1 ), λ(u 2 )).
For example, the full run y 0, a 0 0, a 0 1, a 0 2, z 0 and the log trace y 0, a 0 0, a 0 1, a 0 2, a 0 3, z 0 have only one difference: the addition of a 0 3. They are at distance 1.

Partial-Order Semantics

In full runs of a process model, transition occurrences are totally ordered. However transitions can be handled in different orders for the same process in case of concurrency.

In the model of Fig. 2 traces y 0, a 1 3, a 1 1, a 1 2, a 1 0, z 0 and y 0, a 1 2, a 1 1, a 1 3, a 1 0, z 0 follow the same process but differ by the order of the transitions.

They can however be seen as two linearizations of a common representation based on partial-order runs which represents a process.

Definition 7 (Partial-Order Representation of Runs: Process [START_REF] Engelfriet | Branching processes of Petri nets[END_REF]).

A (non-branching) process P of a Petri Net N = P, T, F, m 0 , m f , Σ, λ is a tuple P = B, E, G, B 0 , B f , h where:

• (B, E, G, B 0 , B f ) is a non-branching, i.e.
, each place has a unique incoming and outgoing arc, finite, acyclic Petri Net,

• h is a function that relates P to N by mapping the elements of B (called conditions) to the places P of N and the elements of E (called events) to the transitions T of N . This function h is required to map bijectively preand post-sets of events to pre-and post-sets of transitions, which ensures that P simulates N .

See e.g. [START_REF] Engelfriet | Branching processes of Petri nets[END_REF] for a more detailed definition.

We write Runs(P) for the set of full runs of the process P. For every full run e 1 . . . e n of a process P of a Petri net N , the sequence

u def = h(e 1 ) . . . h(e n ) ∈
T * is called a linearization of P. Every linearization of P is a full run of N .

Fig. 3 shows a process of the Petri net in Fig. 1. This process represents both full runs y 0, a 9 0, a 9 1, a 9 3, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 and y 0, a 9 0, a 9 3, a 9 1, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 which differ only by the order of concurrent transitions. Similarly, y 0, a 1 3, a 1 1, a 1 2, a 1 0, z 0 and y 0, a 1 2, a 1 1, a 1 3, a 1 0, z 0 are also represented by a single process.

Hence, processes appear as a good representation for trace variants aware of concurrency.

Generalized Model-based Trace Variants

As presented above, full runs of process models can be extracted to represent log traces by using Alignment-based Trace Clustering (ATC). In this section, we want to go further and allow one to extract model-based trace variants aware of concurrent and loop behaviors contained in the process model.

Concurrency Aware Variants

By using processes as model-based trace variants, traces that only differ by the order of concurrent activities can be grouped and represented by the same variant. The process presented in Fig. 3 is then a unique variant for the log traces y 0, a 9 0, a 9 1, a 9 3, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 and y 0, a 9 0, a 9 3, a 9 1, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 . Similarly to ATC,

Processes as Model-based Trace Variants

Traces

y 0 a 0 2 a 0 1 a 0 3 a 0 0 z 0 y 0, a 0 0, a 0 1, a 0 2, a 0 3, z 0 y 0, a 0 1, a 0 0, a 0 2, a 0 3, z 0 y 0 a 1 2 a 1 1 a 1 3 a 1 0 z 0 y 0, a 1 2, a 1 0, a 1 3, a 1 1, z 0 y 0, a 1 3, a 1 1, a 1 2, a 1 0, z 0 process of Figure 3
y 0, a 9 0, a 9 1, a 9 3, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 y 0, a 9 0, a 9 3, a 9 1, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 process similar to Figure 3, not represented y 0, a 0 1, a 0 0, a 0 2, a 0 3, a 0 1, a 0 0, a 0 2, a 0 3, z 0

nc y 0, a 0 1, a 0 1, a 0 2, a 0 2, a 0 3, z 0 Table 2:
Example of APOTC of traces contained in the log of Fig. 2. Maximum distance between clustered traces and their centroids is 0.

those process representatives can be found with a clustering method which gives process centroids that serve as model-based trace variants. Like in the ATC method, the distance between traces and model-based trace variants, is minimized. The distance between a trace σ and a process P is defined by dist P (σ, P) def = min u∈Runs(P) dist L (σ, u). Then distances of APOTC minimize the following.

max σ∈L,χ(σ) =nc dist P (σ, χ(σ)) (2)
Tab. 2 shows an APOTC of log traces of Fig. 2 based on the model of Fig. 1.

By using processes as model-based trace variants, one merges clusters which were separated in the ATC of Tab. 1 and identify richer variants.

Concurrency and Loop Aware Variants

APOTC separates process arising from traces corresponding to different number of loop iterations, e.g., the traces y 0, a 0 1, a 0 0, a 0 2, a 0 3, z 0 and y 0, a 0 1, a 0 0, a 0 2, a 0 3, a 0 1, a 0 0, a 0 2, a 0 3, z 0 . The issue is due of the fixed size of runs of processes, which do not represent loops. To overcome this limitation, we introduce subnets of models.

Definition 9 (Subnet of Petri net). A subnet of a Petri net N = P, T, F, m 0 , m f , Σ, λ is a Petri net P, T , F |T , m 0 , m f , Σ |T , λ with T ⊆ T ,
and y 0, a 0 0, a 0 1, a 2, a 0 3, z 0 y 0, a 0 1, a 0 0, a 2, a 0 3, z 0 y 0, a 0 1, a 0 0, a 0 2, a 0 3, a 0 1, a 0 0, a 0 2, a 0 3, z 0

F T def = F ∩ (P × T ∪ T × P ).
y 0 a 1 2 a 1 1 a 1 3 a 1 0 z 0 y 0, a 1 2, a 1 0, a 3, a 1 1, z 0 y 0, a 1 3, a 1 1, a 2, a 1 0, z 0 y 0 a 9 2
a 9 1 a 9 3 a 9 0 z 0 y 0, a 9 0, a 9 1, a 9 3, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 y 0, a 9 0, a 9 3, a 9 1, a 9 2, a 9 0, a 9 1, a 9 3, a 9 2, z 0 nc y 0, a 0 1, a 0 1, a 0 2, a 0 2, a 0 3, z 0 Distances between a clustered trace σ and its centroid N , used as modelbased trace variants, is defined as

dist N (σ, N ) def = min u∈Runs(N ) dist L (σ, u).
Computing this distance corresponds to align traces to model. Alignment criterion of an AMSTC minimizes equation [START_REF] Bauer | How much event data is enough? a statistical framework for process discovery[END_REF].

max σ∈L,χ(σ) =nc dist N (σ, χ(σ)) (3)
Tab. 3 shows an AMSTC of log traces of Fig. 2 based on the model of Fig. 1.

The novel variant forms allow traces that only differ on concurrency and loops according to the model to be grouped together. Business analysis is sometimes too complicated due to the number of variants. With this approach, we help one to reduce the number of variants the stakeholder has to understand.

Complexity of Alignment-based Trace Clusterings

The search of model-based trace variants depends on the alignment-based trace clustering algorithms. Due to the constraints on the quality, i.e., dist, |nc|, m . . . , the complexity lies already in the existence of a clustering, and the specification of many quality constraints does not change the complexity.

For a non-empty log L and a model N , there exists an ATC C of L w.r.t.

N having at least one clustered trace, iff N has a full run. Indeed, when no constraint is given about the quality criteria dist, m . . . , any full run of N can serve as centroid, and any log trace can be assigned to any cluster. So, it is possible to guess a clustering C in polynomial time. For APOTC and AMSTC, one can also guess in P time the full run u ∈ Runs(χ(σ)), for every clustered trace σ, which will achieve the dist(σ, χ(σ)). Now, checking that C satisfies the constraints, only requires to compute Levenshtein's edit distances and minima over sets of polynomial size. This can be done in P time.

SAT Encoding of Model-Based Trace Variants

In this section we show how we approach AMSTC definition with a SAT encoding to get model-based trace variants.

We encode the existence of an AMSTC of m clusters, to get m model-based trace variants, for net N and log L with maximal distance d, as a SAT formula of the equation ( 4). Formally, we check the existence of C = {N 1 . . . N m }, χ such as :

σ∈L χ(σ) = nc ⇒ dist N (σ, χ(σ)) ≤ d (4)
and optimizes several quality criteria like the number of clustered traces. We develop them in Subsection 6.4.

Distance dist N in (4) is the minimal Levenshtein distance between a trace and a model-based trace variant as subnet. This induces equation [START_REF] Berti | Process mining for python (pm4py): bridging the gap between process-and data science[END_REF].

σ∈L χ(σ) = nc ⇒ min uσ∈Runs(χ(σ)) dist L (σ, u σ ) ≤ d (5)
We can now express Levenshtein distance with Hamming distance (dist H ) and skip actions ( m for model moves and l for log moves), as :

dist L (σ, u) = min σ m ,u l σ |σ m |=|u l σ | dist H (σ m , u l σ )
where σ m ranges over all the words of (Σ ∪ { m }) * obtained by inserting letters m in σ and respectively u l σ ranges over all the words of (Σ ∪ { l }) * . Letters m and l represent deletions and insertions. Technically, we obtain the words σ m for a log trace σ as runs of a Petri net ((N σ ) m ), built from σ as illustrated in Fig. 5, which contains a transition m for model moves. Similarly, the words u l σ are obtained as runs of a modified subnet, χ(σ) l , which has an additional transition l for log moves.

Hence, finding C = {N 1 . . . N m }, χ satisfying (5) amounts to finding C = {N 1 . . . N m }, χ, (σ m ) σ∈L , (u l σ ) σ∈L satisfying σ∈L              σ m ∈ Runs((N σ ) m ) (Φ 1 ) u l σ ∈ Runs(χ(σ) l ) (Φ 2 ) χ(σ) = nc ⇒ dist H (σ m , u l σ ) ≤ d (Φ 3 ) (6)
The SAT encoding of ( 6) is a conjunction of three building blocks that are detailed in the next subsections. SAT encoding of Petri nets has been presented in [START_REF] Chatain | Anti-alignments in conformance checking -the dark side of process models[END_REF] and require two kinds of boolean variables : transition firing and marking representations. We then declare τ L and m L variables for the nets of log traces containing in |L| and defined over alphabet Σ :

• τ L σ,i,a , f or σ ∈ L, i = 1, . . . , n and a ∈ Σ with n the limited size of run.

Those boolean variables indicate that a transition of net of trace σ labeled by a fires at instant i. L allows one to differentiate net of log trace and the initial process model that also have τ variables.

• m L σ,i,p , f or σ ∈ L, i = 0, . . . , n and p ∈ P σ where P σ is the set of places of net of trace σ. Those boolean variables represent the marking of the net of trace at instant i.

Then, any net of trace N σ = P σ , T σ , F σ , m σ0 , m σ f , Σ, Λ has the following SAT clauses where n is the size of run:

• Initial marking of each net of trace:

σ∈L ( p∈mσ 0 m L σ,0,p ) ∧ ( p∈Pσ\mσ 0 ¬m L σ,0,p ) (7)
• Final marking of each net of trace:

σ∈L ( p∈mσ f m L σ,n,p ) ∧ ( p∈Pσ\mσ f ¬m L σ,n,p ) (8)
• One and only one t i per net of trace j for each instant i:

σ∈L n i=1 a∈Σ (τ L σ,i,a ∧ a ∈Σ\t ¬τ L i,a ) (9)
• The transitions are enabled when they fire:

σ∈L n i=1 a∈Σ (τ L σ,i,a =⇒ p∈ • t m L σ,i-1,p ) (10)
• Token game (for safe Petri nets):

σ∈L n i=1 a∈Σ p∈Pσ p∈t • Λ(t)=a (τ L σ,i,a =⇒ m L σ,i,p ) (11)
σ∈L n i=1 a∈Σ p∈Pσ p∈ • t\t • Λ(t)=a (τ L σ,i,a =⇒ ¬m L σ,i,p ) ( 12
) σ∈L n i=1 a∈Σ p∈Pσ p ∈ • t p ∈t • Λ(t)=a (τ L σ,i,a ⇒ (m L σ,i,p ⇔ m L σ,i-1,p )) (13)
Then (Φ 1 ) is a conjunction of formulas ( 7) to (13).

(Φ 2 ): SAT encoding of Model Runs

Now that nets of traces are encoded, we want to encode alignment between them and the process model which is also a Petri net. Any trace σ is aligned to the model and requires its own run of the model noted u σ . We then encode in formula (Φ 2 ) |L| times the process model with the following boolean variables :

• τ M σ,i,a , f or σ ∈ L, i = 1, . . . , n and a ∈ Σ with n the limited size of run.

Those variables indicate that model run of trace σ fires transition labeled by a at instant i.

• m M σ,i,p , f or σ ∈ L, i = 0, . . . , n and p ∈ P where P is the set of places of the process model. Those variables represent the required marking of the process model to get run u σ .

The runs of the model follow the exact same Petri net encoding as the net of traces. Moreover, similarly to nets of traces, we added an isolated transition l to represent log moves and a wait transition to deal with different sizes of traces.

Notice that due to the use of the SAT encoding of Petri nets, the modelbased trace variants are forced to be sound and reach the final marking of the initial process model. traces σ of L. This is defined with the conjunction (Φ 3 ) of ( 6) that we recall:

(Φ 3 ) : σ∈L χ(σ) = nc ⇒ dist H (σ m , u l σ ) ≤ d
In this subsection, we first present how the distances are encoded. Then, we detail the implication that incorporate clustered traces.

SAT Encoding of Distances

Aligning nets of traces and runs is obtained by computing the number of differences between fired transitions. We introduce δ M σ,i and δ L σ,i with σ ∈ L and i = 1, . . . , n boolean variables that represents model and log moves.

σ∈L n i=1 a∈Σ a = l a = m (τ L σ,i,a ∧ ¬τ M σ,i,a ) ⇔ (δ M σ,i ∧ δ L σ,i ) ( 14
) σ∈L n i=1 τ M σ,i, l ⇔ δ L σ,i (15)
σ∈L n i=1 a∈Σ τ L σ,i, m ⇔ δ M σ,i (16)
Axiom 14 forces two δ σ,i variables to be True when two different activities are aligned which implies a distance to 2, this is equivalent of alignment cost.

Indeed, in term of alignment, this situation is represented by a model and a log moves and costs 2.

The maximal distance d given in Equation ( 4) is implemented as at most k constraints, i.e., the number of variables δ to True is limited by d :

σ∈L at most k( n i=1 ∆∈{L,M} δ ∆ σ,i , d) (17)

SAT Encoding of Clustered Traces

Every trace is either clustered in one of the m clusters and attached to a model-based trace variants either associated to the group entitled nc, for nonclustered traces. This is encoded with the following variables.

• InC σ , for σ ∈ L boolean variables that are True where trace σ is clustered.

• χ σ,k for σ ∈ L and k = 0, . . . , m boolean variables that encode which trace is in which cluster.

We then describe trace-cluster associations with the next SAT constraint : σ∈L

σ∈L InC σ ⇔ m k1=0 (χ σ,k1 m k2=0 k2 =k1 ¬χ σ,k2 ) (18)
InC σ ⇒ ( n i=0 a∈Σ τ M σ,i,a ⇒ t∈T Λ(t)=a m k=0 (χ σ,k ⇒ c k,t )) (19)
Conjunction of expressions (14 to 19) forms (Φ 3 ).

Optimization criteria for AMSTC

The presented SAT formula accepts a large set of solutions. However, to get optimal model-based trace variants, we add three optimization criteria:

• Number of clustered traces should be maximized, i.e., number of nonclustered traces should be minimized.

• Inter-cluster distance, i.e., the distance between model-based trace variant, should be maximized.

• Distances between the traces and the model-based trace variant should be minimized.

This problem of maximizations is then a MaxSAT problem that uses weighted clauses.

Minimization of Non-Clustered Traces

First, we optimize the number of clustered traces by maximizing InC variables to True with the following MaxSAT formula :

σ∈L InC σ * W 1
where W 1 is a weight (20)

Inter-cluster Distance Maximization

To maximize the inter-cluster distance defined in [START_REF] Boltenhagen | Generalized alignment-based trace clustering of process behavior[END_REF] we use the heuristic that inter-cluster distance is optimal when the number of common transitions between two model-based trace variants is minimized. We then introduce new boolean variables:

• Common k1,k2,t for k1, k2 ∈ {0, . . . , m}, k1 = k2 and t ∈ T , are boolean variables describing common transitions between centroids of two clusters.

The minimization is found with the following MaxSAT problem where the idea is to set as many as possible Common k1,k2,t variables to False which reduces the number of common transitions between model-based trace variants.

Weights and Peculiarities in Implementation

This large MaxSAT formula is implemented in DarkSider2 an Ocaml command line tool and da4py3 a Python library. The two softwares use MaxSAT solvers to get optimal solutions and return centroids and associated traces.

In the implementations, the number of transitions per cluster is limited by a parameter, entitled maxCSize. Similarly to d, this threshold is encoded as at most k constraints [START_REF] Ignatiev | Pysat: A python toolkit for prototyping with sat oracles[END_REF].

We define the following priorities and the implications on the weights:

1. First, traces should be clustered: W 1 = maxD * W 3 + maxCSize * W 2 2. Then, number of common transitions should be limited: W 2 = maxD * W 3

3. Finally, distances should be reduced: W 3

A Sampling Algorithm to Deal with Large Logs

We propose a sampling algorithm that helps one to deal with large logs.

Main Sampling Idea

In practice, formulas produced by our encoding for AMSTC are too large for casual machines in term of memory space. To reduce the formula, we propose Algorithm 1, a sampling method that calls AMSTC only on samples. AMSTC returns a set of subnets which are the model-based trace variants N i and their list of clustered traces. Then every trace of the entire log is aligned to each of the discovered variants and added to corresponding cluster if the alignment is sufficiently good. Then we iterate over the remaining traces to cluster with new model-based trace variants.

Reducing Alignment Use with Casual Edit Distance between Traces

Alignment is much more expensive than Edit Distance between words. To limit the use of alignment, we propose another version that first uses edit distance between the clustered traces and the rest of the log. This heuristic allows one to considerably reduce the log before doing alignments. As any trace is a maximal distance maxD to its model-based trace variant, novel clustered trace is then at maximal distance to its centroid to 2 * maxD as the maximal distance between clustered traces and unclustered traces is also maxD. One can also consider to introduce another input for this purpose, thus raising the number of clustered traces.

Memoization of the calls to alignmentCost

Typically, in real life logs, traces corresponding to frequent behaviors occur many times in the log. This suggests an easy way to improve the efficiency of Algorithm 1: it suffices to memoize the calls to the function alignmentCost which takes most of the computation time. Tab. 5e in the experiments section 8

shows the spectacular improvement obtained with this technique.

A Statistical Confidence for Sampling

Probability of Missing Clusterizable Traces

We focus on the situations where Algorithm 7 stops before clustering all the log traces which are sufficiently close to a run of the model (i.e. at distance ≤ maxD), that we call clusterizable traces.

We quantify this probability as a function of the proportion of unclustered traces which are clusterizable. Let p be this proportion when the algorithm starts a series of iterations in order to find a nonempty clustering. As long as the clusterings fail, the unclustered traces remain the same and the proportion p does not change. Now, a clustering fails precisely when no clusterizable trace is selected in the sample. The probability of this is (1 -p) sampleSize (the sampled traces are selected independently one from the other).

Finally, if the algorithm starts a series of clusterings from a state where the proportion of unclustered traces which are clusterizable is p, the probability that it fails maxT rials times to cluster traces (and then stops), is

(1 -p) sampleSize×maxT rials .

For example, assume 5% of the unclustered traces are clusterizable, the probability that the algorithm fails to detect them after 2 trials with sampleSize = 10, is 0.95 2×10 ≈ 0, 36. Alter 10 trials, the probability drops to 0.95 10×10 ≈ 0, 006.

If no clusterizable trace remains, i.e. p = 0, the trials fail (and then the algorithm terminates) with probability 1.

Wilson score interval

Equivalently to [START_REF] Bauer | How much event data is enough? a statistical framework for process discovery[END_REF], the number of trials in the sampling method can be assessed with a statistical method. Wilson score interval [START_REF] Edwin B Wilson | Probable inference, the law of succession, and statistical inference[END_REF] gives a lower bound L b and a upper bound U b of probability δ to get a probability p of success on a sample of size n with a confidence α:

p + z 2 2n -z * p * (1-p) n + z 2 4n 2 1 + z 2 n ≤ δ ≤ p + z 2 2n + z * p * (1-p) n + z 2 4n 2 1 + z 2 n ( 23
)
where z is the 1 -α 2 quantile of a standard normal distribution corresponding to the target error rate α.

In our sampling method, we are looking for the number of trials n such as the probability p to get success with our AM ST C function, i.e., the sample provide new model-based trace variants, is bounded by δ with a confidence α. In other words, the probability to get new model-based trace variants with a maximal bound δ corresponds to the null hypothesis, i.e., p = 0, of the statistical interval.

In our approach, we are looking for the minimal number of sample N min that is sufficient for a given maximal bound δ and a confidence α. From the right side of Wilson score intervals [START_REF] Greco | Discovering expressive process models by clustering log traces[END_REF], we obtain:

N min ≥ z 2 * (1 -δ) δ (24)
To illustrate this inequality we give an example inspired from [START_REF] Bauer | How much event data is enough? a statistical framework for process discovery[END_REF]. We want to find the minimum sample size required to be confident at 0.99 that a novel trial of AM ST C would not give new model-based trace variants with a lower bound probability of 0.95. Then, we set the confidence α to 0.01 which implies z = 2.58 from the 1 -α 2 one-side quantile of the standard normal distribution. The lower bound probability that the novel trial of getting new clusters will fail corresponds to the upper bound to get a success, i.e., to get clusters. Then δ = 0.05. From equation ( 24), we found that the minimal sample size is 127 with Wilson score interval.

Experimental Results

In this section, we present our different AMSTC implementations and show a set of experiments from small artificial logs to large real-life logs. As usual, some traces corresponding to frequent behavior occur many times in the log.

We write "number of classical trace variants" for the number of different log traces in a log, in reference to previous works on trace variants like [START_REF] Taymouri | Business process variant analysis: Survey and classification[END_REF]. The aim of the present paper is precisely to reduce this number of trace variants using our richer notion of trace variants obtained as centroids of trace clusters.

Tools

Implementation of the AMSTC method exists in two tools : DarkSider and da4py. DarkSider is an ocaml command line tool while da4py is a Python library. Thanks to [START_REF] Ignatiev | Pysat: A python toolkit for prototyping with sat oracles[END_REF], the most recent and effecient version of the clustering method is da4py and uses state-of-the-art SAT and MaxSAT solver. da4py also uses objects and functions like alignment computation from pm4py library [START_REF] Berti | Process mining for python (pm4py): bridging the gap between process-and data science[END_REF].

As presented in [START_REF] Boltenhagen | Generalized alignment-based trace clustering of process behavior[END_REF], the tools use a heuristic on the length of the run to deal with long traces. The parameter sizeOf Run alleviates the complexity of the problem when traces are long by computing only a prefix of the traces. In this paper, most of the traces can be fully computed (see the sizes of runs of Tab. 6).

The sampling methods and additive heuristics have been developed in da4py

only. Then all the experiments of this paper have been run with da4py on a virtual machine with 12 CPU Intel Xeon 2.67GHz and 50GB RAM.

Event Logs

Experiments have been done on a set of 7 different logs shown in Tab. 4 from 9 to 41353 traces. First log has been presented in [START_REF] Boltenhagen | Generalized alignment-based trace clustering of process behavior[END_REF] to show how modelbased clustering helps one to group traces and extracts deviated behaviors. Log presented in section 1.1 is also an artificial log for this purpose. All the other logs have been introduced in other context. We used 3 real-life logs of BPI challenges.

AMSTC algorithm extracts model-based variants that required a model as input. To show a large variety of different cases, we have done our experiments on models of literature that have been created in different ways for the respective logs. Tab. [START_REF] Benedikt | Regular repair of specifications[END_REF] AMSTC depends on the size of the event logs and size of the models which are detailed in the table.

Notice that models with choices, loops and concurrency have been preferred

than linear models or mostly concurrent patterns. As our method extracts sound subnets, fully concurrent models cannot be divided in several subnets. s, c This section aims at comparing complete AMSTC and the sampling method outputs with different parameters. We used the log L 1 of [START_REF] Boltenhagen | Generalized alignment-based trace clustering of process behavior[END_REF] and its hand written process model which is small enough to be fully computed by the entire algorithm. The log contains 9 traces of maximal length to 7 and the model has 14 nodes (see Fig. 6).

Qualitative Experiments

Experiments have been done with a size of run to 7 and a maximal of trials to We can see that our running example presented in Sec 1.1 perfectly associates every trace of the log to a model-based trace variants. For 500 traces and 411 classical trace variants, the AMSTC method finds 12 model-based trace variants.

Those subnet instances are then a good way to analyze the log traces separately.

We see that for more noisy logs containing in real-life data and a small distance between trace and variants, we are able to cluster a good number of traces in a very small number of clusters. We see from the number of classical trace variants in the second column that the method is indeed able to group them in our more general model-based trace variants.

Discussion: in those experiments, we highlight how our method is able to extract a small number of model-based trace variants of real-life logs compared to the number of classical trace variants. We see that still a lot of traces remain unclustered but this is due to the distance between variants and traces which is intentionally small. The extracted model-based trace variants are well fitting to the clustered traces (maximal distance is always lower than 4 in Tab. 6).

Case Study

To present the value of our model-based variants, we present a case study on a real-life log and different process models. Then, we compare our work to the Super-instances from [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF] which also aims at representing group of traces and are also found by using a clustering approach.

Event Log

We employed the real-life log from the Business Process Management Challenge of 2013 about the closed problems of Volvo management system. The event log contains 1487 log traces, 183 classical trace varitants, 7 activity steps (taking in account activity name and progress) and 4 main activity names. Tab. 7

shows the frequency traces containing the activity names. We see that some activities, like Unmatched, are much less frequent than other, like Completed.

We also notice that activity Queued appears in many classical trace variants but those trace variants are not very frequent in the log. This simple table will help to get good intuition in the understanding of the results of the model-based variants and the super-instances from [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF].

How Model Quality Impacts Model-based Trace Variants

By using the classical trace variants, i.e, the number of unique sequences, one obtains 183 instances for BPIC 2013 closed problems event log. For human analysis and business aspect, this number of instances is too large to be understood. Our AMSTC method helps one to get more representative variants. Our method extracts Model-based Trace Variants along with clustered traces. This aspect motivates us to compare our method to the Super-Instances of [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF]. In this work, it also finds clusters from the log traces, and work with the centroids of them which they call Super-Instances. We see that both methods claims to get representatives of groups of traces. Moreover, they also use a clustering method, i.e., the K-means algorithm. The algorithm is based on the Euclidean distance between vectors of activities occurrence containing in the traces. The main differences between our approach and [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF] are: first, our approach does not need as input the number of clusters, whilst [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF] does. Second, [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF] tries to obtain a balanced clustering, i.e., a clustering where the size of the computed clusters are as much similar as possible. In contrast, our method only focuses on finding good representatives of each cluster, regardless of its size. These differences are corroborated in the case study found below.

First, we used the Jaccard index [START_REF] Wagner | Comparing clusterings: an overview[END_REF] to compare two clusterings, C and C , In our study, the Jaccard index relates pairs of traces in the two clustering results, we also report how many pairs of traces have been clustered together in both clusterings (column n 11 in Tab. 9), and how many traces were clustered together in a clustering but not in the other one (columns n 01 and n 10 in Tab. 9). A high value (≤ 1) of the Jaccard index indicates that the clustering are similar. The main of this study is then to study our clustering results of Tab.8 and the corresponding outputs of [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF]. .

First, we want to justify about the use of clustered traces only when instructing [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF]: in order to compare the clusterings, which aim at grouping traces for their similarities, we claim that considering as a cluster the sets traces not clustered by our method would not give an appropriate comparison, since these unclustered traces are not related. So, to compare the clusters given by the two methods, we ran method of [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF] only on the traces that have been clustered in Tab. 8.

In opposite of AMSTC, method of [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF] requires, as input, the number of clusters. For each ASMTC presented in Tab. 8, we launched the method on the clustered traces and used the same number of clusters. For instance, for the first line, we ran the Super-Instance method on the 1002 clustered traces and set the number of clusters to 4. We give in Tab.9 an overview of the cluster sizes and the Jaccard Index. The two last rows of the table are not informative as their is only 1 cluster. For the first line, in which 4 clusters have been discovered, we see that the Jaccard Index is under 0.5, meaning that there are more pairs of traces clustered in different clusters by the clustering methods.

For the other rows, we see that, the Jaccard index varies from 0.501 to 0.577 which is better than hazard for those lines which have only 2 clusters (see Tab. 8

for the number of clusters). Indeed, for 2 clusters, the probability of n 11 , a pair of traces to be clustered together by both methods, is 1/4, while the addition of the probabilities of n 10 and n 01 is 1/2. We see that the Jaccard Index tells us that our method have some similarities. To conclude this section, we present in Fig. 7 the model-based trace variants of our approach and the super-instances of [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF] of the first line of Tab.9. We remark that two of our representatives contain activity Queued and Unmatched while the super-instances only have once the activity Queued. This is due to the fact that method of [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF] uses K-means that tries to get centroids which are means of the occurrences of activities and n-grams of activities. In our method, the model-based trace variants are subnets which can contain choices, thus allowing activities that are not used in all the traces of a cluster. The variant is then more general than a sequence. However, our method can also get sequential net (see Fig. 7). Model-based trace variants are a good balance to represent the traces, especially when the distance to the traces is zero, i.e., the variants can replay the traces. This last aspect cannot be induced by using the super-instances.

Discussion: in this comparison, we aimed at showing the differences between the super-instances, which are sequences, and the model-based trace variants.

We have seen that the present activities differ from a method to another. The AMSTC gives more complex structures, but the resulted representatives provide more information in terms of activity labels. Moreover, the semantics of Petri nets also provide information about the represented log traces. In addition to different structures, the two approaches have completely different underlying search algorithms. Our method tries to get subnets by using alignment between the model and the log traces. In [START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF], the distance is the Euclidean distance between vectors of occurrences and n-grams, i.e., sub-sequences of traces, and a balanced clustering is obtained if possible. Finally, we want to point out that our method does not require the number of clusters apriori, i.e., our method searches good representatives.

Conclusion and Future Work

This paper builds upon our previous work to propose a generalized version of trace variant. Our notion is based on the assumption that a normative process model exists, and then a trace variant, which represents a subset of log traces, can be created from the perspective of the process model (i.e., they can be processes or subnets of the initial process model), to describe better concurrency and iterative aspects that are blured when only looking at the event log. This generalization may alleviate the requirements for understanding the main behaviors in an event log, one of the first actions that is performed in a process mining project. Remarkably, we use different forms of alignments to compute these generalized trace variants, and encode the problems into SAT to operationalize the techniques. Since for large instances the SAT problems to solve may be prohibitive, we propose a novel family of sampling techniques together with certain statistical guarantees on the number of trials to get a sound set of trace variants. Our experimental evaluation shows promising results in several aspects, included the capability to deal with larger problem instances, but also certain robustness in the presence of noise in the event log.

As future work, we see three main interesting directions to follow: first, studying the characteristics behind a certain clustering solution may help us to find better (SAT) encodings. Second, to explore different representations of the subnets found (e.g., regular expressions) may facilitate the interpretation by a human. Third, to investigate other applications of the clustering algorithm presented in this paper could be already envisioned; for instance, the repair of an imperative process model, by detecting those parts that are more declarative, thus transforming the initial model into a hybrid process model [START_REF] Wil | Learning hybrid process models from events -process discovery without faking confidence[END_REF]: we believe our generalized approach for trace variants can be naturally suited for tackling this problem.

Figure 1 :

 1 Figure 1: Petri Net of Motivation Example

Figure 2 :

 2 Figure 2: Example of Artificial Log

  For a log L and a Petri net N = P, T, F, m 0 , m f , Σ, λ , an alignment-based trace clustering of L w.r.t. N is a tuple C = {u 1 . . . u m }, χ where u 1 . . . u m (m ∈ N) are full runs of N which serve as centroids for the clusters and Full Runs as Model-based Trace Variants

set χ - 1 Fig. 1 .

 11 (nc) contains the traces which are left non-clustered. Tab. 1 shows a clustering of the traces of the log of Fig. 2 based on the model of Centroids of clustering is then a way to represent several log traces for a given distance. This novel idea relates to trace variants where variants are found in the model, introduced in this paper as Model-based Trace Variants.

Figure 3 :

 3 Figure 3: Example of a process of the Petri net in Fig. 1

Definition 8 (

 8 Alignment and Partial Order based Trace Clustering (APOTC)). An alignment and partial order based trace clustering (APOTC) of a log L w.r.t. a Petri net N = P, T, F, m 0 , m f , Σ, λ , is a tuple C = {P 1 . . . P m }, χ where P 1 . . . P m (m ∈ N) are processes of N which serve as centroids for the clusters and χ : L → {nc, P 1 . . . P m } maps log traces either to the centroid of its cluster χ(σ), or to none of the clusters, denoted by nc.

Figure 4 :

 4 Figure 4: A subnet of the Petri Net in Fig. 1.

Fig. 4

 4 Fig. 4 presents a subnet of the model of Fig. 1. Observe that our definition of subnets, based on selecting transitions, restricts the semantics of the net and cannot produce new behaviors. Formally:

Figure 5 :

 5 Figure 5: The net ((Nσ) m ) used to produce the words σ m for a log trace σ = s, g, c .

6. 1 .

 1 (Φ 1 ): SAT Encoding of Log Traces Log traces are encoded as sequential Petri nets noted N σ to deal with model moves. The nets of traces contain an isolated m transition that can fire at any instant. Moreover, a w transition, for "wait", is added at the end of the sequential nets to adapt the different sizes of traces. Fig. 5 shows the net of trace s, g, c .

6. 3 .

 3 (Φ 3 ): SAT Encoding of Variants By using AMSTC, model-based trace variants are subnets N 1 . . . N m (m ∈ N). They are defined by transitions of model runs u σ used to align clustered

If a trace is

  clustered, i.e. InC variable is True, transitions of its corresponding runs belong to the model-based trace variant of its cluster. We declare boolean variables that encode which transition belongs to which model-based trace variant. • c k,t for t ∈ T and k = 0, . . . , m with m the number of clusters. Those variables are True if transition t is in model-based trace variant k. Equation 19 then describes model-based trace variant-transition associations.

6 . 4 . 3 .

 643 ¬Common k1,k2,t * W 2 where W 2 is a weight (21) Minimization of Distances Finally the minimization of differences can be encoded by the following MaxSAT clauses:n i=1 σ∈L ∆∈{L,M} ¬δ ∆ σ,i * W 3where W 3 is a weight[START_REF] Diogo | Approaching process mining with sequence clustering: Experiments and findings[END_REF]

Algorithm 1 : 6 if clustering is ∅ then 7 counter = counter + 1 8 else 9 10 counter = 0 11 if L > 0 then 12 Clusters 14 foreach cluster in clustering do 15 modelBasedT 16 foreach l in L do 17 if 18 Clusters[cluster].add(l) 19 L

 1678910012141516171819 AMSTC Sampling Algorithm Input : N , L, sampleSize, m, maxCSize, maxD, maxT rials 1 Clusters = {} 2 counter = 0 3 while |L| > 0 and counter < maxT rials do 4 sublog = randomSampling(L, sampleSize) 5 clustering = AM ST C(N, sublog, m, maxCSize, maxD) LogAlignT oCluster(clustering, L, maxD, Clusters) below [nc] = L non-clustered traces Output: Clusters : {modelBasedTraceVariant : clusteredTraces} 13 Function LogAlignToCluster(clustering, L, maxD, Clusters): raceV ariant = cluster.getV ariant() alignmentCost(l, modelBasedT raceV ariant) < maxD then .remove(l) One can limit the number of model-based trace variants per loop, which also reduces the size of the SAT formula. Algorithm 1 takes as input a model N , a log L, a sample size sampleSize to randomly select a sample of the entire log, a counter to stop the research of model-based trace variants when samples cannot be aligned anymore and parameters of the AMSTC algorithm, i.e. the number of model-based trace variants m, the maximal number of transitions per cluster maxCSize and the maximal distance between the traces and their variants.

Algorithm 2 : 5 foreach l in L do 6 foreach trace in clusteredT races do 7 if 9 L.remove(l) 10 if l is still unclustered then 11 if

 256791011 Reducing Alignment Use of Algorithm 1 (lines 13 to 19) 1 Function LogAlignToCluster(clustering, L, maxD, Clusters): 2 foreach cluster in clustering do 3 clusteredT races = cluster.getClusterT races() 4 modelBasedT raceV ariant = cluster.getV ariants() editDistance(l, trace) < maxD then 8 Clusters[cluster].add(l) alignmentCost(l, modelBasedT raceV ariant) < maxD then 12 Clusters[cluster].add(l) 13 L.remove(l)

Figure 6 :

 6 Figure 6: Motivation Example of[START_REF] Boltenhagen | Generalized alignment-based trace clustering of process behavior[END_REF]

  defined by: J (C, C ) = n 11 n 11 + n 01 + n 10 where: n11 is the number of pairs of items clustered together in C and in C n10 is the number of pairs of items clustered together in C but in different clusters in C n01 is the number of pairs of items in different cluster in C but in same clusters in C

  , Accepted, Completed Accepted, Accepted, Accepted, Accepted, Accepted, Completed (b) Super-Instances

Figure 7 :

 7 Figure 7: Representatives of Clusters

  marking is an assignment of a non-negative integer to each place. A transition t is enabled in a marking m when all places in • t are marked. When a transition t is enabled, it can fire by removing a token from each place in • t and putting a token to each place in t • . A marking m is reachable from m if there is a sequence of firings t 1 . . . t n that transforms m into m , denoted by m[t 1 . . . t n m . The set of reachable markings from m 0 is denoted by [m 0 . A Petri net is k-bounded if no marking in [m 0 assigns more than k tokens to any place. A Petri net is safe if it is 1-bounded. In this paper we assume safe Petri nets.

	The idea of alignment-based trace clustering is to explicit the relation be-
	tween log traces and full runs of N . Concretely, each cluster of log traces will
	be assigned a full run u of N , presented as the centroid of the cluster.
	Definition 4 (Full Run). A firing sequence u = t 1 . . . t n such that m 0 [u m f
	is called a full run of N . We denote by Runs(N ) the set of full runs of N .
	Given a full run u = t 1 . . . t n ∈ Runs(N ), the sequence of ac-
	tions λ(u)	def = λ(t 1 ) . . . λ(t n ) is called a (model) trace of N .	When
	the labeling function λ is injective, like in the model of Fig. 1, we
	sometimes identify the transition t with its label λ(t).	Then, full
	runs coincide with model traces.

Table 1 :

 1 Example of Alignment-based Trace Clustering (ATC) of log traces containing in log of Fig. 2 for a maximum distance to 2

Table 3 :

 3 Example of Alignment and Model Subnet-based Trace Clustering (AMSTC) of traces containing in log of Fig. 2 for a maximum distance to 0

  The same holds for APOTC, where centroids are processes of N , since N has a process iff N has a full run; it holds again for AMSTC, taking into account the constraint that any subnet used as centroid should have a full run.

Now, deciding if a model has a full run u, corresponds to checking reachability of the final marking. The problem of reachability in Petri nets is known to be decidable, but non-elementary

[START_REF] Czerwinski | The reachability problem for Petri nets is not elementary[END_REF]

, and still PSPACE-complete for safe Petri nets. But the complexity trivially drops to NP-complete 1 if a bound l is given (with l an integer coded in unary) on the length of u.

In practice, relevant clusterings will not use very long full runs (or processes for APOTC) as centroids. Typically, a bound l on the length of the full runs can be assumed, for instance 2 times the length of the longer log trace. Let us call l-bounded a trace clustering satisfying this constraint.

Theorem 1. The problem of deciding, for a log L, a model N , an integer bound l, integers m max , d max , and a rational number nc max , the existence of a lbounded ATC (respectively APOTC, AMSTC) C of L w.r.t. N , having at most m max clusters, a distance between the traces and their centroids lower or equal to d max and a maximal number nc max of unclustered traces is NP-complete.

Proof. As observed earlier, the problem is NP-hard even with the only constraint that at least one trace is clustered. It remains to show that it is in NP: indeed, if there exists a (l-bounded) clustering, there exists one with no more that |L| clusters (forgetting empty clusters cannot weaken the quality criteria); and, by assumption, the size of centroids (defined as |σ| for ATC, |P| for APOTC, number of transitions in the subnet for AMSTC) is bounded by l.

Table 4 :

 4 indicates which design method have been used. Complexity of Event Logs Statistics and Used Discovered Models

	Log	|L|	Number	|Σ|	∀ σ∈L max(|σ|)	Model Discovery	|T |	|P |
			of			Method
			Classical
			Trace
			Variants
	Artificial L 1 of	9	9	7	7	Hand written	8	6
	[8]					model 1
	Artificial L vrts	500	411	40	36	Hand written	90	92
	presented in					model 1
	Sec 1.1
	Artificial L1 of	500	453	37	36	PLG2 tool	39	40
	[39]
	LoanA of [43]	500	100	16	37	Hand written	17	14
						model 2
	BP I 2013 cp	1487	183	7	35	Heuristic Miner 3	25	18
	BP I 2013 inc	7554	1511	13	123	Split Miner 3	15	11
	BP I 2014 f	41353	14948	9	167	Split Miner 3	24	16

  2. Tab. 5 gives the results of the experiments. Each sub-table is an improvement of the previous one except table 5f which aims at showing consequence of the number of classical trace variants. Every line is an experiment of a specific setting and has been run 10 times. For descriptive results, like the number of clusters and traces, the most returned results are shown. Runtimes are means for the experiments of the selected results. We now give an analysis of the tables.In sub-table 5a, we see that, given different distances and number of clusters, results differ. Raising the distance between the traces and the centroids allows to cluster more traces. However, a good distance threshold aims at partitioning the traces in more specific clusters and then get specific model-based trace variants.Discussion: from this experiments, we see that the AMSTC method helps the traces and the models, assessing the minimal size of the run depending on the traces and loop behaviors and counting an approximate maximal number of transitions per cluster. The sampling size have been chosen in a way that runtime is optimized. The number of clusters per loop was set to 2 to reduce the formula size. Finally, we set the number of trials of the sampling algorithm to 5 sequential fails. Each experiment have been run 10 times except the last one because of long runtimes. Due to trace variants and the use of causal edit distance between traces, outputs of the same experiment are different. In Tab. 6 we show examples of clustering results that have returned the least unclustered traces. Notice that the runtimes are much larger because of the number of activities and trace variants in logs. Moreover, the models are also much larger than in the previous experiments.

	Log	Number	Sample	Size	Maximal	Maximal	Number	Number of		Unclus-	Runtime	Alignment
		of Clas-	Size	of	Number of	Distance	of	Traces Per		tered	(secs)	Runtime
		sical		run	Transition	(Number	Clusters		Cluster		Traces		(secs)
		Trace			per	of Moves)
		Variants			Cluster
								Min Max Avg
	In sub-table 5b, sampling method outputs are presented. For the exact Artificial L1 9 5 5 5 0 3 2 2 2 3 4.02 0.13 of [8]
	Artificial Lvrts same distribution of the traces, we proportionally get the same results of the 411 5 15 9 0 12 22 54 42 0 2135.84 27.96 presented in
	Sec 1.1
	complete AMSTC method. Then the exact same model-based trace variants Artificial L1 453 5 15 15 4 4 19 145 62 252 6681.47 666.23 of [39]
	are extracted. LoanA of [11] 100	10	20	14	1	10	10	60	25	250	409.32	64.31
	BP I 2013cp	183	10	20	9	1	3	32 1121 451	134	245.29	42.33
	Sub-table 5c aims at showing that our method can deal with strange trace BP I 2013inc 1511 5 20 11 2 2 204 5981 3092 1369 4091.79 3646.47
	BP I 2014f	14948	5	20	15	2	6	257 21909 4344 15289	66709.70 66130.29
	variant frequency. In this experiment, the second trace of L 1 have been du-
	plicated 82000 times while the other traces appear 1000 times each. We can
	see that the size of the clusters are indeed very different. However, notice that
	the number of clusters corresponds to the previous experiments. The same
	model-based trace variants have been extracted.
	Sub-tables 5d and 5e contain heuristic improvements in term of runtimes.
	Finally, we have added noise in log to raise the number of trace variants
	which is used by the heuristics. The number of clusters is then different which
	is expected.

Table 6 :

 6 Examples of AMSTC Outputs on a Set of 7 Logs

Table 7 :

 7 Frequency of Traces and Classical Variants Containing the Different ActivitiesHowever, our method is based on an existing model. In Tab. 8, we show different clustering results for different model qualities.

	Activity Label Frequency of Traces Containing the	Frequency of Classical Trace Variants
			Activity Label		Containing the Activity Label
	Accepted		1.00			0.99
	Completed		1.00			1.00
	Queued		0.36			0.84
	Unmatched		0.01			0.04
	Model	Fitness	Maximal	Maximal	Number	Number of	Unclus-
			Number of	Distance	of	Traces Per	tered
			Transition	(Number	Clusters	Cluster	Traces
			per Cluster	of Moves)
						Min Max Avg
	Split Miner	0.98	10	0 2	4 2	1 59 1377 718 917 251	485 51
	Heuristic Miner	0.94	12	0 2	2 2	3 17 1391 704 917 460	567 79
	Inductive Miner 0.82	7	0 2	1 1	574 574 574 1367 1367 1367	913 120
	Models from [1], available at https://doi.org/10.6084/m9.figshare.6376592.v1

Table 8 :

 8 AMSTC on BPIC 2013cp Log and Different Models. Sample size is set to 15 and run size to 20.We observe that the fitness of the model impacts the number unclustered traces. Moreover, we see that results of the last model of Tab. 8 do not give useful information in term of representatives. In fact, this model, learned with the inductive miner, is very simple and contains only a choice and a loop, making hard to split the model in model-based trace variants. Finally, we note that our clusters are very heterogeneous. This aspect can help one to understand the structure of the model by analyzing the model-based trace variants.

	Discussion: in this experiment, we show how fitness impacts results of the
	ASMTC methods, thus giving different model-based trace variants. For larger
	distances to the centroids, one gets less variants but can cluster more traces
	from the event log. In opposite, for a distance to zero, the number of model-
	based variants raises but many traces are left unclustered, i.e, do not have a

Table 9 :

 9 Cluster Comparison between AMSTC and[START_REF] De | Scalable mixed-paradigm trace clustering using super-instances[END_REF] results for the same traces and number of clusters. All the rows of this table have been produced based on the rows of Tab.8

	Cluster Sizes of AMSTC	Jaccard Comparison		Cluster Sizes by using
		(see Tab. 8)					method of [18]
	Min	Max	Median	n 11	n 10	n 01	Index	Min	Max	Median
	1	917	42	169577 253652 1560	0.399	82	496	212
	59	1377	718	550325 398762 32081	0.561	458	978	718
	3	917	470	210957 209032 1479	0.501	424	496	460
	17	1391	704	562403 404478 7038	0.577	431	977	704
	574	574	574	164451	0	0	1.000	574	574	574
	1367	1367	1367	933661	0	0	1.000	1367	1367	1367

NP-hardness can be obtained by reduction from the problem of reachability in a safe acyclic Petri net, known to be NP-complete[START_REF] Stewart | Reachability in some classes of acyclic Petri nets[END_REF][START_REF] Cheng | Complexity results for 1-safe nets[END_REF].

http://www.lsv.fr/ chatain/darksider

https://github.com/BoltMaud/da4py

Available at https://github.com/BoltMaud/da4py/examples

Available at doi:10.4121/uuid:c1d1fdbb-72df-470d-9315-d6f97e1d7c7c

From[START_REF] Augusto | Abstract-and-compare: A family of scalable precision measures for automated process discovery[END_REF], available at https://doi.org/10.6084/m9.figshare.6376592.v1

Acknowledgments.

This work has been supported by Farman institute at ENS Paris-Saclay and by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R.

Quantitative Experiments

In this section, we present experimentation of the set of different logs presented in section 8.2. Settings presented in the table have been chosen by the author after some tests. The tests consisted on evaluating the distance between


Anne-Laure Gancel

Adeline Vignault

Etienne Pilard

Michaël Jourdes

Marc Fermaud

Jean Roudet

Fernando Zamora

Pierre-Louis Teissèdre
email: pierre-louis.teissedre@u-bordeaux.fr

Functionality of commercial tannins: anti-Botrytis effect, antioxidant capacity and organoleptic impact

. Therefore, we studied here commercial tannins as a possible alternative to SO 2 at the vatting.

Five tannins were chosen from different vegetal sources: procyanidins from seed (TPA) (low mPD) and skin (IE) (high mPD) of grape berries, profisetinidins from quebracho tropical tree (T), ellagitannins from oak tree (Q) and gallotannins from nutgall (G). Musts with 20 % and 50% botrytization rates were obtained from healthy and botrytized grapes (strain 213) from Merlot cultivar. High contamination degrees were chosen to reveal contrasted effects. The impact of commercial tannins addition at the vatting (100 g/hL) on musts and wines protection against laccase damages was studied with regards to the laccase activity, antioxidant capacity, phenolic compounds composition and CieLab color parameters. Sensory analyses were also performed on 3 month-wines to evaluate visual, olfactory and gustative impacts of tannins additions.

Results showed that at 50% botrytisation rate, the addition of any type of commercial tannins at 100 g/hL seemed to be ineffective on laccase activity and phenolic compounds protection. Laccase activities > 5 U/mL were found in 3 month wines leading inevitably to oxidasic casse. Despite this high botrytisation rate, calculated color differences (E) and sensory analyses showed differences between tannins: wines obtained with IE and G tannins were darker than the control wine whereas wine with Q tannins was lighter. At a 20% botrytisation rate, differences between tannins addition were more evident. Procyanidic tannins from IE or TPA showed an inhibitory effect on laccase activity and protected color against complete degradation. Moreover, wine with IE tannins appeared to be darker and perhaps more qualitative with regards to olfactory and gustative aspect than the control wine.

Fonctionnalité des tanins oenologiques: effet anti-Botrytis, capacité anti-oxydante et impact organoleptique

Anne-laure Gancel 1 , Adeline Vignault 1,2,3 , Etienne Pilard 1 , Michaël Jourdes ,1 , Marc Fermaud 4 , Jean Roudet 4 , Fernando Zamora 2 , Pierre-Louis Teissèdre La pourriture grise sur les baies de raisin, liée au développement de Botrytis cinerea, est à l'origine d'importantes pertes lors des vendanges. Ce champignon produit des laccases capables d'oxyder les composés phénoliques du raisin et ainsi dégrader la couleur et les propriétés organoleptiques des moûts et vins jusqu'à la casse oxydasique, inacceptable. Un taux de contamination de 5% peut déjà entraîner une baisse perceptible de la qualité sensorielle du vin [1]. Excepté le tri des baies contaminées, peu d'alternatives éco-responsables à l'ajout de SO 2 existent pour traiter ces laccases. Les tanins commerciaux, autorisés par l'OIV pour le collage, possèdent également des propriétés antioxydantes et anti-oxydasiques qui en font des candidats potentiels pour lutter contre les laccases. Néanmoins, très peu de travaux sont disponibles sur le sujet [START_REF] Dumeau | The effect of tannin addition on laccase activity of Botrytis cinerea during fermentation[END_REF]. Cette étude envisage donc d'évaluer l'impact de l'ajout à la cuvaison de tanins oenologiques pour inhiber l'activité laccase et préserver les qualités organoleptiques des vins produits.

Cinq tanins ont été choisis parmi différentes sources végétales: procyanidines de graines (TPA) (DPm faible) et de pellicules (IE) (DPm élevé) de raisin, profisetinidines de quebracho (T), ellagitannins du chêne (Q) et gallotannins de noix de galle (G). Les moûts botrytisés à des taux de 20% et 50% ont été obtenus à partir de raisins sains et contaminés (souche 213) de cépage Merlot. Des degrés de contamination élevés ont été choisis pour mettre en évidence des effets marqués. L'impact de l'addition de tanins commerciaux à la cuvaison (100 g/hL) a été étudié du point de vue l'activité laccase, la capacité anti-oxydante, la composition des composés phénoliques et les paramètres de couleur CieLab. Des analyses sensorielles ont également été réalisées sur des vins de 3 mois pour évaluer les impacts visuels, olfactifs et gustatifs de l'ajout de tanins.

Les premiers résultats ont montré qu'à un taux de botrytisation de 50%, l'addition des tanins oenologiques semble avoir un impact limité sur l'activité laccase et la protection des composés phénoliques. Des activités de laccase > 5 U / mL ont été trouvées dans les vins de 3 mois conduisant inévitablement à une casse oxydasique. En revanche, à des taux de 20%, l'ajout de tanins de type procyanidiques IE et TPA conduit à un effet inhibiteur sur la laccase et protège en partie la couleur et les teneurs en procyanidines mono et oligomériques des vins obtenus. De plus, les calculs de différence de couleur (E) et les analyses sensorielles montrent également que le vin avec tanins IE serait de couleur plus intense que le témoin sans tanin et même plus qualitatif des points de vue olfactif et gustatif.

Funcionalidad de los taninos enológicos: efecto anti-Botrytis, capacidad antioxidante e impacto organoléptico

Anne-laure Gancel 1 , Adeline Vignault La pudrición del moho gris en uvas, con el desarrollo de Botrytis cinerea, es responsable de pérdidas significativas durante la cosecha. Este hongo produce lacasas capaces de oxidar compuestos fenólicos de la uva y, también de degradar el color y las propiedades organolépticas de mostos y vinos hasta la quiebra oxidásica. Un bajo nivel de contaminación (5%) es suficiente para observar una disminución perceptible de la calidad sensorial del vino [1]. Aparte de la selección de bayas sanas, existen pocas alternativas eco-responsables al SO 2 para el tratamiento de las lacasas. Los taninos comerciales, ya autorizados por la OIV para el pegado, también tienen propiedades antioxidantes y antioxidásicas que los hacen candidatos potenciales para inhibir las lacasas. Sin embargo, hay muy poco trabajo disponible sobre el tema [START_REF] Dumeau | The effect of tannin addition on laccase activity of Botrytis cinerea during fermentation[END_REF]. Por lo tanto, este estudio propone evaluar el impacto de la adición en los mostos de taninos comerciales para inhibir la actividad lacasa y preservar las cualidades organolépticas de los vinos producidos.

Cinco taninos diferentes fueron seleccionados a partir de diferentes fuentes de origen vegetal: procianidinas de semillas (TPA) (mDP baja) y pieles (IE) (mDP alto) de uva, profisetinidinas de quebracho (T), elagitaninos de roble (Q) y galotaninos de agallas (G). Los mostos botritizados al 20% y 50% se obtuvieron de uvas sanas y contaminadas (cepa 213) de uvas Merlot. Se eligieron altos niveles de contaminación para resaltar los efectos significativos. El impacto de la adición de taninos comerciales antes de la fermentación alcohólica (100 g/hL) se ha estudiado desde el punto de vista de la actividad de la lacasa, la capacidad antioxidante, la composición de los compuestos fenólicos y los parámetros CieLab. También se realizaron análisis sensoriales en vinos de 3 meses para evaluar los impactos visuales, olfativos y gustativos de la adición de taninos.

Los primeros resultados mostraron que con 50% de uvas botritizadas, la adición de taninos enológicos parece tener un impacto limitado en la actividad de la lacasa y la protección de compuestos fenólicos. Se encontraron actividades de lacasas > 5 U / mL en vinos de 3 meses que inevitablemente llevan a la quiebra oxidásica. En contraste, con 20% de uvas botritizadas, la adición de taninos de tipo procianidinas IE y TPA conduce a un efecto inhibidor sobre la lacasa y parcialmente protege el color y el contenido de procianidinas mono-y oligómericas de los vinos obtenidos. Además, los cálculos de diferencia de color (E) y los análisis sensoriales también muestran que el vino con taninos IE sería de color más intenso que el control sin tanino y más cualitativo desde el punto de vista olfativo y gustativo.

2 F

 2 . Dumeau, M.-L. Murat, M.-L. Marquette, F. Daviaud The effect of tannin addition on laccase activity of Botrytis cinerea during fermentation. (2004) Australian and New Zealand Grapegrower and Winemaker. 78-86.

I. Ky, B. Lorrain, M. Jourdes, G. Pasquier, M. Fermaud, L. Gény, et al. Assessment of grey mould (Botrytis cinerea) impact on phenolic and sensory quality of Bordeaux grapes, musts and wines for two consecutive vintages. (2012) Australian Journal of Grape and Wine Research. 18,

215-226.

I. Ky, B. Lorrain, M. Jourdes, G. Pasquier, M. Fermaud, L. Gény, et al. Assessment of grey mould (Botrytis cinerea) impact on phenolic and sensory quality of Bordeaux grapes, musts and wines for two consecutive vintages. (2012) Australian Journal of Grape and Wine Research. 18,

215-226. 2 F. Dumeau, M.-L. Murat, M.-L. Marquette, F. Daviaud The effect of tannin addition on laccase activity of Botrytis cinerea during fermentation. (2004) Australian and New Zealand Grapegrower and Winemaker. 78-86.