# Process discovery on deviant traces and
other stranger things

Federico Chesani1, Chiara Di Francescomarino2, Chiara Ghidini2, Daniela
Loreti1,
Fabrizio Maria Maggi3, Paola Mello1, Marco Montali3, Sergio Tessaris3
1 DISI - University of Bologna, Bologna, Italy
2 Fondazione Bruno Kessler (FBK), Trento, Italy
3 Free University of Bozen-Bolzano, Bolzano, Italy
E-mail<EMAIL_ADDRESS>
###### Abstract

As the need to understand and formalise business processes into a model has
grown over the last years, the process discovery research field has gained
more and more importance, developing two different classes of approaches to
model representation: procedural and declarative. Orthogonally to this
classification, the vast majority of works envisage the discovery task as a
one-class supervised learning process guided by the traces that are recorded
into an input log.

In this work instead, we focus on declarative processes and embrace the less-
popular view of process discovery as a binary supervised learning task, where
the input log reports both examples of the normal system execution, and traces
representing “stranger” behaviours according to the domain semantics. We
therefore deepen how the valuable information brought by both these two sets
can be extracted and formalised into a model that is “optimal” according to
user-defined goals. Our approach, namely NegDis, is evaluated w.r.t. other
relevant works in this field, and shows promising results as regards both the
performance and the quality of the obtained solution.

##  1 Introduction

The modelling of business processes is an important task to support decision-
making in complex industrial and corporate domains. Recent years have seen the
birth of the BPM (BPM) research area, focused on the analysis and control of
process execution quality, and in particular, the rise in popularity of
_process mining_ [van12], which encompasses a set of techniques to extract
valuable information from event logs. _Process discovery_ is one of the most
investigated process mining techniques. It deals with the automatic learning
of a process model from a given set of logged traces, each one representing
the digital footprint of the execution of a case. Process discovery algorithms
are usually classified into two categories according to the language they
employ to represent the output model: procedural and declarative. Procedural
techniques envisage the process model as a synthetic description of all
possible sequences of actions that the process accepts from an initial to an
ending state. Declarative discovery algorithms—which represent the context of
this work—return the model as a set of constraints equipped with a
declarative, logic-based semantics, and that must be fulfilled by the traces
at hand. Both approaches have their strengths and weaknesses depending on the
characteristics of the considered process. For example, procedural techniques
often produce intuitive models, but may sometimes lead to “spaghetti”-like
outputs [FLM+09, MMCA18]: in these cases declarative-based approaches might be
preferable.

Declarative techniques rely on shared metrics to establish the quality of the
extracted model, for example in terms of _fitness_ , _precision_ ,
_generality_ , and _simplicity_ [AMC+15, vBWVB14, dLNCvB18]. In particular,
fitness and precision focus on the quality of the model w.r.t. the log, i.e.,
its ability to accept desired traces and reject unlikely ones, respectively;
generality measures the model’s capability to abstract from the input by
reproducing the desired behaviours, which are not assumed to be part of the
log in the first place; finally, simplicity is connected to the clarity and
understandability of the result for the final user.

Besides the declarative-procedural classification, process discovery
approaches can be also divided into two categories according to their vision
on the model-extraction task. As also pointed out by Ponce-de-Leòn et al.
[dLNCvB18], the vast majority of works in the process discovery spectrum (e.g.
[vdAWM04, WvdA03, GvdA07, vdARV+10]) can be seen as one-class supervised
learning technique, while fewer works (e.g. [MWvdAvdB06, GMVB09, CLM+09])
intend model-extraction as a two-class supervised task—which is driven by the
possibility of partitioning the log traces into two sets according to some
business or domain-related criterion. Usually these sets are referred to as
_positive_ and _negative_ examples [dLNCvB18], and the goal is to learn a
model that characterises one set w.r.t. the other.

A further consideration stems from the _completeness_ of the log. Generally, a
log contains and represents only a subset of the possible process executions.
Other executions might be accepted or rejected from the viewpoint of the
process, but this can be known only when a process model is learned or made
available. This territory of _unknown traces_ will be “shaped” by the learned
model, and more precisely by the choice of the discovery technique, and
possibly by its configuration parameters. Approaches that consider positive
examples only provide a number of heuristics, thus allowing the user to decide
to which extent the yet-to-be-seen traces will be accepted or rejected by the
discovered model—ranging from the extremity of accepting them all, to the
opposite of rejecting them all. The use of a second class of examples,
identified on the basis of some domain-related criterion, allows to introduce
some business-related criterion besides the heuristics.

In this work, we focus on declarative process models expressed in the Declare
language [Pes08], and embrace the view of process discovery as a binary
supervised learning task. Hence, our starting point is a classification of
business traces into two sets, which can be driven by various motivations. For
example, in order to avoid underfitting and overfitting [vdARV+10], many
authors, as well as the majority of tools, suggest to ignore less-frequent
traces (sometimes referred as _deviances_ from the usual behaviour [NDR+16]),
thus implicitly splitting the log according to a frequency criterion. Another
motivation for log partitioning could be related to the domain-specific need
to identify “stranger” execution traces, e.g., traces asking for more (or
less) time than expected to terminate, or undesirable traces that the user
might want to avoid in future executions.

Independently of the chosen criteria for splitting the log, we adopt the terms
negative and positive example sets to identify the resulting partitioning,
keeping in mind that the “negative” adjective is not necessarily connected to
unwanted traces, but rather connected to a sort of “upside-down world” of
“stranger” behaviours. The information carried by the negative example set
diverges from that containing the positive examples but—coupled with it—can be
used to understand the reasons why differences occur, ultimately providing a
more accurate insight of the business process.

For this reason, we hereby focus on learning a set of constraints that is able
to reconstruct which traces belong to which set, while—whenever
possible—reflecting the user expectations on the quality of the extracted
model according to predefined metrics. In particular our approach, namely
NegDis, aims to discover a minimal set of constraints that allow to
distinguish between the two classes of examples: in this sense, it can enrich
existing approaches that instead provide richer descriptions of the positive
example set only. Indeed, our exploitation of the “upside-down world” is
useful not only to better clarify what should be deemed compliant with the
model and what should not, but also to better control the degree of
generalisation of the resulting model, as well as to improve its simplicity.

The contributions of our work can be listed as follows.

  * •

A novel discovery approach, NegDis, based on the underlying logic semantics of
Declare, which makes use of the information brought by the positive and
negative example sets to produce declarative models.

  * •

The adoption of a satisfiability-based technique to identify the models.

  * •

A heuristic to select the preferred models according to input parameters
dealing with generalisation or simplicity.

  * •

An evaluation of the performance of NegDis w.r.t. other relevant works in the
same field.

##  2 Background

Our technique relies on the key concept of _event log_ , intending it as a
_set_ of observed process executions, logged into a file in terms of all the
occurred events. In this work, we adopt the XES (XES) storing standard
[VBvDvdA10] for the input log. According to this standard, each _event_ is
related to a specific process _instance_ , and describes the occurrence of a
well-defined step in the process, namely an _activity_ , at a specific
timestamp. The logged set of events composing a process instance is addressed
as _trace_ or _case_. From the analysis of the _event log_ , we want to
extract a Declare [Pes08, vdAPS09] _model_ of the process. Declare is one of
the most used languages for declarative process modeling. Thanks to its
declarative nature, it does not represent the process as a sequence of
activities from a start to an end, but through a set of constraints, which can
be mapped into LTL (LTL) formulae over finite traces [MPvdA+10, GV13]. These
constraints must all hold true when a trace complete.

Declare specifies a set of templates that can be used to model the process. A
constraint is a concrete instantiation of a template involving one ore more
process activities. For example, the constraint EXISTENCE(a) is an
instantiation of the template EXISTENCE(X), and is used to specify that
activity a must occur in every trace; INIT(a) specifies that all traces must
start with a. RESPONSE(a,b) imposes that if the a occurs, then b must follow,
possibly with other activities in between. For a description of the most
common Declare templates see [Pes08].

We assume that the log contains both _positive_ traces—i.e., satisfying all
the constraints in the business model—and _negative_ traces—i.e., diverging
from the expected behaviour by violating at least one constraint in the
(intended) model.

Language bias. Given a set of Declare templates $D$ and a set of activities
$A$, we identify with $D[A]$ the set of all possible grounding of templates in
$D$ w.r.t. $A$, i.e. all the constraints that can be built using the given
activities.

Traces and Logs. We assume that a _Trace_ $t$ is a _finite_ word over the set
of activities (i.e., $t\in A^{*}$, where $A^{*}$ is the set of all the words
that can be build on the alphabet defined by $A$). Usually a log is defined as
a multi-set of traces, thus allowing multiple occurrences of the same trace:
the frequency of a certain trace is then considered as an indicator, for
example, of the importance of that trace within the process. Since our goal is
to learn a (possibly _minimal_) set of constraints able to discriminate
between two example classes, we rather opt to consider a _Log_ as a _finite
set_ of traces. As a consequence, multiple occurrences of the same trace will
not affect our discovery process.

Declare constraints satisfaction and violation. Recalling the $LTL_{f}$
semantics [MPvdA+10, GV13], and referring to the standard Declare semantics as
in [Pes08], we say that a constraint $c$ _accepts_ a trace $t$, or
equivalently that $t$ _satisfies_ $c$, if $t\models c$. Similarly, a
constraint $c$ rejects a trace $t$, or equivalently $t$ _violates_ $c$, if
$t\not\models c$. Given that a Declare model $M$ is a conjunction of
constraints, it follows that $M$ _accepts_ a trace $t$ ($t$ _satisfies_ $M$)
if $\forall c\in M,t\models c$. Analogously, a model $M$ _rejects_ a trace $t$
($t$ _violates_ $M$) if $\exists c\in M,t\not\models c$. In the following, we
will write $t\models M$ meaning that M accepts t.

Positive and negative examples. Finally, we respectively denote with $L^{+}$
and $L^{-}$ the sets of positive and negative examples (traces), reported in
the input event log. We assume that:  (i) $L^{+}\cap L^{-}=\varnothing$, and
(ii) for each trace $t\in L^{-}$ there exists at least one grounded Declare
constraint $c\in D[A]$ that accepts all the positive traces and excludes $t$.
In other words, we assume that the problem is feasible111Notice that sometimes
real cases might not fulfill these assumptions. We will discuss this issue in
section 3.3.

##  3 The approach

NegDis aims to extract a model which correctly classifies the log traces by
accepting all cases in $L^{+}$ and rejecting those in $L^{-}$222The conditions
on accepting all the positives and none of the negatives can be relaxed by
requiring only a percentage of them.. Besides that, it is required to perform
an abstraction step in order to be able to classify also unknown traces, which
are not in the input log.

###  3.1 Definitions

Before introducing our approach, we hereby provide some preliminary
definitions that are relevant for the following explanation.

Model generality.. The notion of a model accepting a trace, often referred as
the compliance of a trace w.r.t. the model, naturally introduces the relation
of _generality_ (or the converse _specificity_) between models. Intuitively, a
model $M$ is more general than another $M^{\prime}$ if $M$ accepts a superset
of the traces accepted by $M^{\prime}$. That is, denoting with $T_{M}$ the set
of all traces compliant with a model $M$, $M$ is more general than another
model $M^{\prime}$—and symmetrically $M^{\prime}$ is more specific than $M$—if
and only if $T_{M^{\prime}}\subseteq T_{M}$. More precisely, we say that

######  Definition 3.1.

a model $M\subseteq D[A]$ is _more general_ than $M^{\prime}\subseteq D[A]$
(written as $M\succeq M^{\prime}$) when for any $t\in A^{*}$, $t\models
M^{\prime}\Rightarrow t\models M$ , and _strictly more general_ (written as
$M\succ M^{\prime}$) if $M$ is more general than $M^{\prime}$ and there exists
a $t^{\prime}\in A^{*}$ s.t. $t^{\prime}\not\models M^{\prime}$ and
$t^{\prime}\models M$.

Note that this definition is consistent with that of subsumption between
Declare templates provided in Di Ciccio et al. [CMMM17]. Indeed, Declare
templates can be organised into a subsumption hierarchy according to the
logical implications that can be derived from their semantics.

######  Example 3.1.

The constraint INIT(a) accepts only traces that start with a. Hence, a exists
in each one of those accepted traces. In other words, all those traces satisfy
also the constraint EXISTENCE(a). However, the latter constraint accepts also
traces that contains a even if they do not start with a. This relation is
valid irrespectively of the involved activity. In a sense, we could say that
the template EXISTENCE(X) is _more general_ than INIT(X).

This idea is frequently expressed through the subsumption operator
$\sqsupseteq$. Given two templates $d,d^{\prime}\in D$, we say that $d$
_subsumes_ $d^{\prime}$, i.e. $d$ _is more general than_ $d^{\prime}$ (written
$d\sqsupseteq d^{\prime}$), if for any grounding of the involved parameters
w.r.t. the activities in $A$, whenever a trace $t\in A^{*}$ is compliant with
$d^{\prime}$, it is also compliant with $d$ [CMMM17] .

######  Remark 3.1.

For any pair of models $M,M^{\prime}\subseteq D[A]$, $M\subseteq M^{\prime}$
implies that $M$ is more general than $M^{\prime}$ ($M\succeq M^{\prime}$).
This stems from the Declare semantics [Pes08] on $LTL_{f}$ [GV13].

Unfortunately, the opposite implication does not hold, i.e. if we have
$M,M^{\prime}\subseteq D[A]$ such that $M\succeq M^{\prime}$, we cannot
guarantee that $M\subseteq M^{\prime}$. A clear example is
$M=\\{\textsf{EXISTENCE(a)}\\}$ and $M^{\prime}=\\{\textsf{INIT(a)}\\}$.

Initial model. A wide body of research has been devoted to techniques to mine
declarative process models that characterise a given event log (our positive
traces). Our approach can leverage these techniques and refine their results
by taking into account the negative examples as well. To this end, we consider
a—possibly empty— _initial model_ $P$, i.e. a set of Declare constraints that
are known to characterise the positive traces. For example, such set can be
the expression of domain knowledge or the result of a state-of-the-art
discovery algorithm previously applied to $L^{+}$. To apply our technique we
only require that all the positive traces are compliant with all the
constraints in $P$. We are aware that often state-of-the-art approaches do not
emit a model compliant with all the traces in the input log. In these cases,
we consider as positive only the traces that are allowed by $P$.

Candidate solution. As the goal of our technique is to refine the initial
model $P$ taking into account both positive and negative traces, we can define
which are the necessary conditions for a set of constraints $S$ to be a
candidate solution for our discovery task.

######  Definition 3.2.

Given the initial model $P$, a _candidate solution_ for the discovery task is
any $S\subseteq D[A]$ s.t.

  1. (i)

$P\subseteq S$;

  2. (ii)

$\forall t\in L^{+}$ we have $t\models S$;

  3. (iii)

$\forall t\in L^{-}$ we have $t\not\models S$.

Optimality criterion. Clearly, there can be several sets satisfying these
conditions. They differ from the way they classify the unknown traces, which
are not in $L^{+}$, nor in $L^{-}$. Therefore, we need to introduce some way
to compare the multiple output models in order to identify the preferable
ones. In some context, _generality_ can be a measure of the quality of the
solution, i.e. we want to identify the set that is less committing in terms of
restricting the admitted traces. In some other context on the contrary, we
might be interested in the identification of a more specific model. So besides
allowing all traces in $L^{+}$ and forbidding all traces in $L^{-}$, the
choice between a general or specific model, obviously affects the
classification of the unknown traces. Alternatively, _simplicity_ is another
criterion: one can be interested in the most _simple_ solution, i.e. the one
that is presumed to be easier to understand irrespectively from the degree of
generality/specificity it accomplishes.

Let us focus on _generality_ for the moment. In this case, we are interested
in the candidate solution $S$ (i.e., satisfying the properties of Definition
3.2) such that there is no other candidate solution $S^{\prime}\subseteq D[A]$
strictly more general than $S$ (i.e., $\nexists~{}S^{\prime}$ s.t. $S\prec
S^{\prime}$).

Although testing for strict generality between two set of constraints is a
decidable problem, its worst case complexity makes an exact algorithm
unfeasible because, recalling definition 3.1, it would require to asses the
compliance of any trace $t\in A^{*}$ with the two models going to be compared.
For this reason, we propose an alternative method based on comparing the
logical consequences that can be deducted from the models.

The method makes use of a set of deduction rules which account for the
_subsumption_ between Declare templates. Our work integrates the rules
introduced in [CMMM17], into a function, namely the _deductive closure
operator_ , which satisfies the properties of extensivity, monotonicity, and
idempotence.

######  Definition 3.3.

Given a set $R$ of subsumption rules, a _deductive closure operator_ is a
function $cl_{R}:\mathcal{P}(D[A])\rightarrow\mathcal{P}(D[A])$ that
associates any set $M\in D[A]$ with all the constraints that can be logically
derived from $M$ by applying one or more deduction rules in $R$.

######  Example 3.2.

Let be:

  * •

$R=\\{\ \textsf{EXISTENCE(X)}\sqsupseteq\textsf{INIT(X)}\ \\}$

  * •

$M^{\prime}=\\{\textsf{INIT(a)}\ \\}$

If we apply the deductive closure operator $cl_{R}$ to $M^{\prime}$, we get:

$cl_{R}(M^{\prime})=\\{\ \textsf{INIT(a), EXISTENCE(a)}\ \\}$

Obviously, we are interested in sets $R$ of _correct_ subsumption rules, that
is for any $M\subseteq D[A]$ and $t\in A^{*}$, $t\models M$ iff $t\models
cl_{R}(M)$. In the rest of the paper, for the easy of understanding, we will
omit the set $R$ and we will simply write $cl(M)$. The complete set of
employed rules is available333The repository is freely available at
https://zenodo.org/record/5158528, and the experiments can be run through a
Jupyter Notebook at https://mybinder.org/v2/zenodo/10.5281/zenodo.5158528/.

As the closure of a model is again a subset of $D[A]$, Remark 3.1 is also
applicable, i.e. for any $M,M^{\prime}\subseteq D[A]$, $cl(M)\subseteq
cl(M^{\prime})$ implies that $M$ is more general than $M^{\prime}$ ($M\succeq
M^{\prime}$). Thanks to this property, the deductive closure operator can be
used to compare Declare models w.r.t. generality. To provide an intuition, let
us consider the following example:

######  Example 3.3.

Let be:

  * •

$R=\\{\ \textsf{EXISTENCE(X)}\sqsupseteq\textsf{INIT(X)}\ \\}$

  * •

$M=\\{\ \mathsf{EXISTENCE(a)}\ \\}$

  * •

$M^{\prime}=\\{\ \mathsf{INIT(a)}\ \\}$

We cannot express any subset relation between $M$ and $M^{\prime}$, thus
making Remark 3.1 inapplicable. Nonetheless, if we take into account their
closure, we have:

$\displaystyle cl(M)=\\{\mathsf{EXISTENCE(a)}\\}\quad\textnormal{and}$
$\displaystyle cl(M^{\prime})=\\{\textsf{INIT(a)},\textsf{EXISTENCE(a)}\\}$

As $cl(M)$ is a subset of $cl(M^{\prime})$, we conclude that $M$ is more
general than $M^{\prime}$.

In other words, the closure operator (being based on the subsumption rules)
captures the logical consequences deriving from the Declare semantics. Due to
the nature of the Declare language we cannot provide a complete calculus for
the language of conjunctions of Declare constraints. For this reason, we
cannot guarantee the strictness, nor the opposite implication (i.e.
$M^{\prime}\preceq M$ does not implies $cl(M)\subseteq cl(M^{\prime})$).
Anyway, the closure operator provide us a powerful tool for confronting
candidate solutions w.r.t. the generality criterion.

###  3.2 Two-step procedure

In this section we introduce the theoretical basis of our NegDis approach. The
parameters of the problem are the following.

  * •

$D$ set of Declare templates (language bias)

  * •

$A$ set of activities

  * •

$cl$ closure operator equipped with a set $R$ of subsumption rules.
$cl:\mathcal{P}(D[A])\rightarrow\mathcal{P}(D[A])$

  * •

$L^{+}$ log traces labelled as positive. $L^{+}\subseteq A^{*}$

  * •

$L^{-}$ log traces labelled as negative. $L^{-}\subseteq A^{*}$

  * •

$P$ initial model. $P\subseteq\\{c\in D[A]\quad|\quad\forall t\in
L^{+},\,t\models c\\}$

For the sake of modularity and easiness of experimenting with different
hypotheses and parameters, we divide our approach into two clearly separate
stages: the first which identifies the candidate constraints, and a second
optimisation stage which selects the solutions. However, these two steps are
merged into a single monolithic search-based approach.

Starting from the set of all constraints $D[A]$, the first stage aims at
identifying all the constraints of $D[A]$ which accept all positive traces and
reject at least a negative one. To this end, it first computes the set of
constraints that accepts all traces in $L^{+}$, namely the set _compatibles_.

${compatibles(D[A],L^{+})}=\\{c\in D[A]~{}|~{}\forall t\in L^{+},~{}t\models
c\\}\\\ $ (1)

For simplicity of the notation, since the set of constraints $D[A]$ and the
log $L^{+}$ are given, we will omit them in the following. The _compatibles_
set is then used to build a sheriffs function that associates to any trace $t$
in $L^{-}$ the constraints of compatibles that rejects $t$. The result is
therefore a function with domain $L^{-}$ and co-domain
$\mathcal{P}({compatibles})$ s.t.:

${\textit{sheriffs}}(t)=\\{c\in{compatibles}~{}|~{}t\not\models c\\}\\\ $ (2)

The second stage aims at finding the optimal solution according to some
criterion. Therefore, it starts by computing two sets $\mathcal{C}$ and
$\mathcal{Z}$. Let $\mathcal{C}$ be the set of those constraints in $D[A]$
that accept all positive traces and reject at least one negative trace. Such
set can be derived from the sheriffs function as: $\mathcal{C}=\bigcup_{t\in
L^{-}}\textit{sheriffs}(t)$. Let $\mathcal{Z}$ be all the subsets of
$\mathcal{C}$ excluding all negative traces444As we will discuss in section
3.3, the implementation must take into account that it might not be always
possible to find models fulfilling Eq.3, i.e.,

$\mathcal{Z}=\\{M\in\mathcal{P}(\mathcal{C})\mid\forall t\in
L^{-}~{}t\not\models M\\}$ (3)

######  Example 3.4.

Let $L^{+}=\\{\mathsf{ab}\\}$, $L^{-}=\\{\mathsf{a,b,ba}\\}$, and
$D=\\{\mathsf{EXISTENCE(X)},\mathsf{RESPONSE(Y,Z)}\\}$. The set of activities
is $A=\\{\ \mathsf{a},\mathsf{b}\ \\}$. The grounded set of constraints is
then $D[A]=\\{$ $\mathsf{EXISTENCE(a)}$, $\mathsf{EXISTENCE(b)}$,
$\mathsf{RESPONSE(a,b)}$, $\mathsf{RESPONSE(b,a)}\ \\}$.

The compatibles set would be:

$\displaystyle compatibles(D[A],L^{+})=\\{\ $
$\displaystyle\mathsf{EXISTENCE(a)},\ \mathsf{EXISTENCE(b)},$
$\displaystyle\mathsf{RESPONSE(a,b)}\ \\}$

and the computation of the sheriffs function finds:

$\displaystyle\textit{sheriffs}(\mathsf{a})=\\{\mathsf{EXISTENCE(b)},\
\mathsf{RESPONSE(a,b)}\\}$
$\displaystyle\textit{sheriffs}(\mathsf{b})=\\{\mathsf{EXISTENCE(a)}\\}$
$\displaystyle\textit{sheriff}(\mathsf{ba})=\\{\mathsf{RESPONSE(a,b)}\\}$

In this case, there are two subsets of $\mathcal{C}$ excluding all traces in
$L^{-}$, i.e., $\mathcal{Z}=\\{M_{1},M_{2}\\}$, where

$\displaystyle M_{1}=\\{\ \mathsf{EXISTENCE(b)},\ \mathsf{EXISTENCE(a)},\
\mathsf{RESPONSE(a,b)}\ \\}$ $\displaystyle M_{2}=\\{\
\mathsf{RESPONSE(a,b)},\ \mathsf{EXISTENCE(a)}\ \\}$

Once $\mathcal{C}$ and $\mathcal{Z}$ are computed, the goal of the
optimisation step is to select the “best” model in $\mathcal{Z}$ which can be
either devoted to _generality/specificity_ , or _simplicity_. When the most
general model is desired, the procedure selects as solution the model
$S\in\mathcal{Z}$ such that

$\displaystyle\text{there is no $S^{\prime}\in\mathcal{Z}$ s.t.
}cl(S^{\prime}\cup P)\subset cl(S\cup P)$ (6a) $\displaystyle\text{there is no
$S^{\prime}\subset S$ s.t. }cl(S^{\prime}\cup P)=cl(S\cup P)$ (6b)

The first condition, Eq. (6a), ensures generality by selecting the model $S$
for which the logical consequences of $S\cup P$ are the less restricting. In
this way, the initial model $P$ (containing a set of Declare constraints that
are known to characterise $L^{+}$) is enriched taking into account the
information derived by $L^{-}$. Furthermore, since from the point of view of
generality we are not interested in the content of the selected model, but
rather in its logical consequences, the closure operator $cl$ ensures that no
other model in $\mathcal{Z}$ is more general than the chosen $S$. The second
condition, Eq. (6b), allows to exclude redundancy inside the selected model
$S$ by ensuring that it does not contain constraints that are logical
consequence of others in $S$. Considering the previous example, this
optimisation step allows to chose model $M_{2}$ as solution because
$\mathsf{EXISTENCE(b)}$ is a logical consequence of
$\mathsf{EXISTENCE(a)}\land\mathsf{RESPONSE(a,b)}$.

If we were interested in the less general model, condition (6a) would be

$\text{there is no $S^{\prime}\in\mathcal{Z}$ s.t. }cl(S^{\prime}\cup
P)\supset cl(S\cup P)$ (7)

whereas the redundancy constraint would be ensured through the same Eq. (6b)
because, even when we look for the most specific model, redundancy compromises
its readability, without adding any value.

Generality/specificity is not the only desirable optimality criterion. If we
are interested in the _simplest_ model instead, a solution composed of a
limited number of constraints is certainly preferable. So, we also
experimented with an alternative optimisation formulation based on the set
cardinality. The procedure selects the $S\in\mathcal{Z}$ such that:

$\displaystyle\text{there is no }S^{\prime}\in\mathcal{Z}\text{ s.t. }$
$\displaystyle|cl(S^{\prime}\cup P)|<|cl(S\cup P)|$ (8a)
$\displaystyle\begin{split}\text{there is no }S^{\prime}\in\mathcal{Z}\text{
s.t. }&|cl(S^{\prime}\cup P)|=|cl(S\cup P)|\text{ and}\\\
&|S^{\prime}|<|S|\end{split}$ (8b)

where the first equation selects the set with the smaller closure, whereas the
second allows to choose the solution with less constraints among those with
closure of equal cardinality.

######  Theorem 3.1.

The models that are solution according to the simplicity criterion are also
solutions for the generality criterion.

###### Proof.

Suppose ad absurdum that there is a model $S\in\mathcal{Z}$ that is optimal
according to the simplicity criterion of Eq. (8a) and (8b) but it is not the
most general, i.e. either Eq. (6a) or Eq. (6b) are violated for $S$. If $S$
violated Eq. (6a), it would exists an $S^{\prime}\in\mathcal{Z}$ s.t.
$cl(S^{\prime}\cup P)\subset cl(S\cup P)$. But clearly, this implies that
$|cl(S^{\prime}\cup P)|<|cl(S\cup P)|$, which contradicts Eq. (8a). On the
other hand, if $S$ violated Eq. (6b), it would exists an $S^{\prime}\subset S$
s.t. $cl(S^{\prime}\cup P)=cl(S\cup P)$. Obviously we would also have
$|S^{\prime}|<|S|$ and $|cl(S^{\prime}\cup P)|=|cl(S\cup P)|$, which
contradict Eq. (8b). ∎

Conversely, the opposite implication in Theorem 3.2 does not necessarily hold.
Indeed, let assume that $P$ is empty and $cl$ is the identity function555This
may also be the case when the constraints selected in the first stage are
logically independent.; consider two negative traces $t_{1},t_{2}$ and a
sheriffs function producing three constraints $\\{c_{1},c_{2},c_{3}\\}$. In
particular, $\textit{sheriffs}(t_{1})=\\{c_{1},c_{2}\\}$ and
$\textit{sheriffs}(t_{2})=\\{c_{1},c_{3}\\}$. The only simplicity-oriented
solution would be $\\{c_{1}\\}$, whereas as regards the generality-oriented
solutions we would have both $\\{c_{1}\\},\\{c_{2},c_{3}\\}$. We must remark
that the simplicity principle is based on the intuition that “smaller” Declare
models should be easier to understand for humans. However, we might notice
that, since the two models $\\{c_{1}\\}$ and $\\{c_{2},c_{3}\\}$ are not
directly comparable according to their semantics, deciding which is the “best”
might depend on the constraints themselves, ad well as the specific domain.

###  3.3 Implementation

The first stage is implemented via the Algorithm 1, which starts by collecting
the set $compatibles$ of the constraints that accept (are satisfied by) all
the positive traces (Line 2). Subsequently, each negative trace is associated
(by means of the function sheriffs) with those constraints in $compatibles$
that reject (are violated by) a trace in $L^{-}$ (Line 4). Notice that for
some negative example, i.e. for some trace $t\in L^{-}$ we might have
$\textit{sheriff}(t)=\varnothing$ because the chosen language may not be
expressive enough to find a constraint able to reject $t$ while admitting all
traces of $L^{+}$. This situation might arise also in case $t$ belongs to both
$L^{+}$ and $L^{-}$.

Algorithm 1 Identification of the constraints accepting all traces in $L^{+}$
and rejecting at least one trace in $L^{-}$.

Input: $D[A],L^{+},L^{-}$
Output: $\textit{sheriffs}:L^{-}\rightarrow\mathcal{P}({D[A]})$

1:procedure sheriffsGeneration($D[A],\,L^{+},\,L^{-}$)

2: ${compatibles}=\\{c\in D[A]|\forall t\in
L^{+},\,\textsc{compliant}(t,c)=\texttt{True}\\}$

3: for $t\in L^{-}$ do

4:
$\textit{sheriffs}(t)=\\{c\in{compatibles}|\textsc{compliant}(t,c)=\texttt{False}\\}$

5: end for

6: return sheriffs

7:end procedure

The implementation of the compliance verification compliant (i.e. $t\models
c$) leverages the semantics of Declare patterns defined by means of regular
expressions [CMMM17] to verify the compliance of the traces. It is implemented
in Go language employing a regexp implementation that is guaranteed to run in
time linear in the size of the input666For more details, see the Go package
regexp documentation at https://golang.org/pkg/regexp/.

The second optimisation stage has been implemented using the ASP (ASP) system
Clingo [GKKS14]. The main reason for selecting an ASP system for finite domain
optimisation is that rules provide an effective and intuitive framework to
implement a large class of closure operators. Indeed, all the deductive
systems for Declare that we analysed in the literature (see e.g. [BCDM16,
CMMM17]) can be recasted as Normal Logic Programs [Lif08] by exploiting the
assumption that the set of activities is finite and known in advance. For
example the valid formula $\textsc{Init}(a)\implies\textsc{Precedence}(a,b)$
that holds for any pair of activities $a,b$ can be written as the rule

⬇

precedence(A,B) :- init(A), activity(B).

using a specific predicate (activity) holding the set of activities.

The second stage is implemented as described in Algorithm 2. The required
input parameters, properly encoded as an ASP program, are the initial model
$P$, the sheriffs function computed by Algorithm and a custom function
${is\\_better}:\mathcal{P}({D[A]})\times\mathcal{P}({D[A]})\rightarrow\\{\texttt{True},\
\texttt{False}\\}$. The purpose of the latter is to implement the chosen
optimality criterion by taking as input two constraint sets and providing as
output a boolean value representing whether the first set is better than the
second. If the two sets are not comparable according to the criterion,
${is\\_better}$ returns False. Indeed, such a function is the expression of
the global or partial ordering that the optimality criterion induces on the
solutions.

Algorithm 2 Selection of the best solutions according to a custom criterion.

Input:
$P,\,\textit{sheriffs}:L^{-}\rightarrow\mathcal{P}({D[A]})$,$\,{is\\_better}:\mathcal{P}({D[A]})\times\mathcal{P}({D[A]})\rightarrow\\{\texttt{T},\texttt{F}\\}$
Output: $\mathcal{Z}$, i.e. the set of the best solutions

1:procedure Selection($\textit{sheriffs},\,P$)

2: $\mathcal{Z}=\varnothing$

3: $L^{\prime-}=\\{t\in L^{-}\>|\>\textit{sheriffs}(t)\neq\varnothing\land
t\models P\\}$

4: $\mathcal{C}=\bigcup_{t\in L^{\prime-}}\textit{sheriffs}(t)$

5: for each $S\subseteq\mathcal{C}$ s.t. $\forall t\in
L^{\prime-},\;S\cap\textit{sheriffs}(t)\neq\varnothing$ do

6: if $(\forall S^{\prime}\in\mathcal{Z}\ !is\\_better(S^{\prime},S)\,)$ then

7: $\mathcal{Z}\,\leftarrow\,\\{S\\}\cup\\{S^{\prime}\in\mathcal{Z}\ |\
!is\\_better(S,S^{\prime})\,\\}$

8: end if

9: return $\mathcal{Z}$

10:end procedure

The algorithm starts by computing a set $L^{\prime-}$ of all those negative
traces that can be excluded by at least a constraint
($\textit{sheriffs}(t)\neq\varnothing$) and are still instead accepted by the
initial model $P$ ($t\models P$). Indeed, albeit from the theoretical point of
view we assumed that for each trace $t\in L^{-}$ there exists at least one
Declare constraint in $D[A]$ accepting all positive traces and discarding $t$,
real cases might not fulfil this assumption.When it is not possible to exclude
a negative trace $t$, Algorithm 1 returns $\textit{sheriffs}(t)=\varnothing$,
and Algorithm 2 overlooks this case by computing $L^{\prime-}$. The set
$\mathcal{C}$ is then build (Line 4) by considering the constraints allowing
all traces in $L^{+}$ and disallowing at least one trace in $L^{\prime-}$
(Line 4). From that, the algorithm selects any subset $S$ fulfilling the
condition $\forall t\in L^{\prime-}\;S\cap{choices}(t)\neq\varnothing$ (Line
5), i.e., any $S$ accepting all positive traces and rejecting all the
negatives that can be actually excluded.

Any such $S$ is then included in the solution set $\mathcal{Z}$ if the latter
does not contain another solution $S^{\prime}$ that is better than $S$
according to the custom optimality criterion expressed by the ${is\\_better}$
operator (Line 6). Solutions $S^{\prime}$ previously founded are kept into
$\mathcal{Z}$ only if the newly found solution $S$ is not better than them
(Line 7). Notice that both Line 6 and 7 make use of the function $is\\_better$
in a negated form: this is due to the fact that, according to the chosen
optimality criterion, sometimes it would not be possible to compare two
solutions.

Regarding the optimality criterion, for example we could consider
_generality_. In that case, ${is\\_better}$ employs the criteria of Eq. (6a)
(for generality) and (6b) (to avoid redundancy). Conversely, if we are
interested in the most specific solution, ${is\\_better}$ must implement Eq.
(7) and (6b). Finally, when the optimality criterion is _simplicity_ , Eq.
(8a) and (8b) must be used.

In real cases, the returned set $\mathcal{Z}$ might contain several solutions.
If the number of solutions provided by the procedure is too high for human
intelligibility, the optimality condition could be further refined by inducing
a preference order in the returned solution. For example, among the most
general solutions one can be interested in being reported first those models
with the lower number of constraints, or with certain Declare templates. The
advantage of our approach is precisely in the possibility to implement off-
the-shelves optimisation strategies, where—adapting the $is\\_better$ function
or even the definition of the closure operator—the developer can easily
experiment with different criteria.

######  Example 3.5.

Consider the sets of positive and negative examples composed by only one trace
each: $L^{+}=\\{\textsf{bac}\\}$ and $L^{-}=\\{\textsf{ab}\\}$. Suppose also
that:

  * •

$P=\varnothing$;

  * •

$D=\\{\ \textsf{EXISTENCE(X), INIT(X)}\ \\}$;

  * •

the alphabet of activities is just $A=\\{\textsf{a, b, c}\\}$.

Then, the set of ground constraints can be easily elicited: $D[A]=\\{$
EXISTENCE(a), EXISTENCE(b), EXISTENCE(c), INIT(a), INIT(b), INIT(c)$\ \\}$.

If we want to learn the most general model, Algorithm 1 elects the following
compatible constraints:

$\displaystyle{compatibles}=\\{$ $\displaystyle\textsf{EXISTENCE(a),
EXISTENCE(b)},$ $\displaystyle\textsf{EXISTENCE(c), INIT(b)}\\}$

and emits:

$\textit{sheriffs}(\textsf{ab})=\\{\ \textsf{EXISTENCE(c), INIT(b)}\ \\}.$

In this simple case, the subsets satisfying the condition of Line 5 in
Algorithm 2 would be:

$\displaystyle S_{1}=$ $\displaystyle\\{\textsf{EXISTENCE(c)}\\}$
$\displaystyle S_{2}=$ $\displaystyle\\{\textsf{INIT(b)}\\}$ $\displaystyle
S_{3}=$ $\displaystyle\\{\textsf{EXISTENCE(c)},\textsf{INIT(b)}\\}$
$\displaystyle S_{4}=$
$\displaystyle\\{\textsf{EXISTENCE(c)},\textsf{EXISTENCE(a)}\\}$
$\displaystyle...$ $\displaystyle S_{n}=$
$\displaystyle\\{\textsf{EXISTENCE(c)},\textsf{INIT(b)},\textsf{EXISTENCE(a)}\\}$
$\displaystyle...$

As we are interested in the most general models, both $S_{1}=$ $\\{\
\textsf{EXISTENCE(c)}\ \\}$ and $S_{2}=\\{\ \textsf{INIT(b)}\ \\}$ are optimal
solutions. Note that these two solutions cannot be compared according to the
definitions of generality because there exist traces (such as the unknown
trace b) compliant with $S_{2}$ and non-compliant with $S_{1}$ (i.e., there is
no subset relation between ${C}_{S_{1}}$ and ${C}_{S_{2}}$). Obviously, the
choice of one model over another influences the classification of all those
unknown traces that—being not part of the input log—are not labelled as
positive of negative.

If we were interested in the most simple solution instead, $S_{1}=\\{\
\textsf{EXISTENCE(c)}\ \\}$ would have been our choice, because its closure is
the smaller in cardinality.

Finally, if we were interested in the most specific set of constraints, the
application of a convenient ${is\\_better}$ function would have determined the
choice of $\\{$EXISTENCE(a), EXISTENCE(c), INIT(b)$\\}$—where the redundancy
check of Eq. (6b) operated by discarding EXISTENCE(b).

##  4 Experimental evaluation

One of the difficulties of evaluating process mining algorithms is that given
a log, the underlying model might not be known before. As a consequence, it
might be difficult to establish an _ideal model_ (a golden standard) to refer
and confront with. In this regard, a number of metrics and evaluation indexes
have been proposed in the past to evaluate how a discovered model fits a given
log [AMC+15, vBWVB14, dLNCvB18]. However, those metrics might provide only a
partial answer to the question of “how good” is the discovered model. In the
case of NegDis, a further issue influences the evaluation process: the
difficulty of performing a “fair” comparison with existing techniques because
the majority of the methods we could access have been designed to use
“positive” traces only.

We pursued two different evaluation strategies. On one side, we defined a
model, and from that model we generated a synthetic, artificial log, taking
care that it exhibits a number of desired properties: in a sense, this part of
the evaluation can be referred as being about a “controlled setting”. A first
aim is to understand if NegDis succeeds to discover a _minimum_ set of
constraints for distinguishing positive from negative examples; a second aim
is to qualitatively evaluate the discovered model, having the possibility to
confront it with the original one. Experiments conducted on that synthetic log
are reported and discussed in Section 4.1.

On the other side, we applied NegDis to some existing logs, thus evaluating it
on some real data set. Again, this experiment has two aims: to understand
weakness and strengths of NegDis w.r.t. to some relevant literature; and to
confront the proposed approach with real-world data—and difficulties that
real-world data bring along. Section 4.2 is devoted to present the selected
logs and discuss the obtained results.

The source code and the experiments are available777The repository is
published at https://zenodo.org/record/5158528, and the experiments can be run
through a Jupyter Notebook at
https://mybinder.org/v2/zenodo/10.5281/zenodo.5158528/.

###  4.1 Experiments on a synthetic dataset

The synthetic log has been generated starting from a Declare model, using a
tool [LCCM20] based on Abductive Logic Programming. The model has been
inspired by the Loan Application process reported in [DRMR18]. In our model,
the process starts when the _loan application_ is received. Before _assessing
the eligibility_ , the bank proceeds to _appraise the property_ of the
customer, and to _assess the loan risk_. Then, the bank can either _reject the
application_ or _send the acceptance pack_ and, optionally, _notify the
approval_ (if not rejected). During the process execution the bank can also
_receive positive_ or _negative feedback_ (but not both), according to the
experience of the loan requester. It is not expected, however, that the bank
receives a _negative feedback_ if the _acceptance pack_ has been sent.
Moreover, due to temporal optimization, the bank requires that the _appraise
of the property_ is done before _assessing the loan risk_. To ease the
understanding of the loan application process, a Declare model of the process
is reported in Fig. 1. Moreover, all the activities have been constrained to
either not be executed at all, or to be executed at most once: in Declare
terminology, all the activities have been constrained to absence2(X).

Figure 1: Loan approval declare process model.

To test NegDis, besides positive traces, we generated also negative traces. In
particular, we generated traces that violate two different constraints:

  1. (a)

the precedence(assess_loan_risk, assess_eligibility), that is violated when
either the latter activity is executed and the former is absent, or if both
the activities appear in the log, but in the wrong temporal order;

  2. (b)

the exclusive_choice(send_acceptance_pack, receive_negative_feedback), that is
violated when a trace either contains both the activities, or does not contain
any of them.

The resulting log consists of 64,000 positives traces, 25,600 traces that
violate the constraint as in $(a)$, and 10,240 traces that violate the
constraint as specified in $(b)$. When fed with the positives traces and
traces violating the constraint in $(a)$, NegDis successfully manages to
identify constraints that allow to clearly distinguish positives from
negatives traces. Moreover, the discovered constraint coincides with the one
we originally decided to violate during the generation phase. When confronted
with the scenario $(b)$, NegDis again successfully managed to identify a
minimum model able to discriminate between positive and negative traces, and
the identified constraint is indeed logically consistent with the constraint
originally selected for the violation. Table 1 summarize the obtained results
and reports the first selected model for each scenario.

Scenario | Positive Trace # | Negative Trace # | Time | Originally Violated Constraint | First Discovered Model
---|---|---|---|---|---
(a) | 64,000 | 25,600 | Total: 81.78 + 1.94 + 109.74 + 3.32 + 15.165s |  |
Compatibles: 81.78 + 1.94s | _precedence(assess_loan_risk,_ | _precedence(assess_loan_risk,_
Choices: 109.74 + 3.32s | _assess_eligibility)_ | _assess_eligibility)_
Optimisation: 15.165s |  |
(b) | 64,000 | 10,240 | Total: 81.78 + 1.94 + 94.51 + 2.96 + 1.379s |  |
Compatibles: 81.78 + 1.94s | _exclusive_choice(send_acceptance_pack,_ | _coExistence(reject_application,_
Choices: 94.51 + 2.96s | _receive_negative_ feedback)_ | _receive_negative_feedback)_
Optimisation: 1.379s |  |

Table 1: Models discovered when dealing with the synthetic data set.

For the sake of completeness, we decided to experiment also with the Process
Discovery Tool of the Rum Framework888https://rulemining.org/, that is based
on the Declare Miner algorithm [MDDK18]. Based on the exploitation of positive
traces only, Declare Miner discovers a rich model that describes as “most
exactly” as possible the given traces. When fed with the positive traces of
our artificial log, and with the _coverage_ parameter set to 100% (i.e.,
prefer constraints that are valid for all the traces in the logs), the RuM
Framework discovers a model made of 514 constraints. If the coverage is
relaxed to 80% (prefer constraints that are satisfied by at least the 80% of
the traces), the model cardinality grows up to 1031 constraints.

In both cases the discovered model is able to distinguish between the positive
and the negative traces. This is not surprising, since Declare Miner aims to
identify all the constraints that hold for a given log: hence, it will
discover also those constraints that allow to discern positive from negative
traces. Rather, this result is a clear indication that indeed our artificial
log has been constructed “correctly”, since negative traces differ from the
positive ones for some specific constraints, and the positive traces
exhaustively elicit the cases that can occur. This is typical of artificial
logs, while real-life logs might not enjoy these properties.

Another consideration is about the cardinality of the discovered model: the
Declare Miner approach provides a far richer description of the positive
traces, at the cost perhaps of bigger models. Our approach instead has the
goal of identifying the _smallest_ set of constraints that allow to
discriminate between positive and negatives. In this sense, approaches like
the one presented in this paper and Declare Miner are complementary.

###  4.2 Evaluation on case studies from real data

For the experimentation with real datasets, we used three real-life event
logs: cerv, sepsis and bpic12. Starting from these event logs we generated 5
different datasets, each composed of a set of positive and a set of negative
traces, by applying different criteria to distinguish between positive and
negative traces, i.e., by labeling the event log with different labeling
functions.

cerv is an event log related to the process of cervical cancer screening
carried out in an Italian cervical cancer screening center [LMM+07]. Cervical
cancer is a disease in which malignant (cancer) cells form in the tissues of
the cervix of the uterus. The screening program proposes several tests in
order to early detect and treat cervical cancer. It is usually composed by
five phases: Screening planning; Invitation management; First level test with
pap-test; Second level test with colposcopy, and eventually biopsy. The traces
contained in the event log have been analyzed by a domain expert and labeled
as compliant (positive traces) or non-compliant (negative traces) with respect
to the cervical cancer screening protocol adopted by the screening center.

sepsis [Man16] is an event log that records trajectories of patients with
symptoms of the life-threatening sepsis condition in a Dutch hospital. Each
case logs events since the patient’s registration in the emergency room until
her discharge from the hospital. Among others, laboratory tests together with
their results are recorded as events. The traces contained in the event log
have been labelled based on their cycle execution time. In the sepsismean
dataset, traces with a cycle time lower than the mean duration of the traces
in the event log (~ 28 days) have been labelled as positive, as negative
otherwise. Similarly, in the sepsismedian, traces with a cycle time lower than
the median duration of the traces in the event log (~ 5 days) have been
labeled as positive; as negative otherwise.

bpic12 [vD12] is a real-life event log pertaining to the application process
for personal loans or overdrafts in a Dutch financial institute. It merges
three intertwined sub-processes. Also in this case, the traces have been
labelled based on their cycle execution time. In the bpic12mean dataset (resp.
bpic12mean), traces with a cycle time lower than the mean (resp. median)
duration of the traces in the event log (~ 8 days, resp. ~ 19 hours) have been
labelled as positive; as negative otherwise.

Table 2 summarizes the data related to the five resulting datasets.

Dataset | Log | Trace # | Activity # | Label | Positive | Negative
---|---|---|---|---|---|---
Trace # | Trace #
cervcompl | cerv | 157 | 16 | compliant | 55 | 102
sepsismean | sepsis | 1000 | 16 | mean duration | 838 | 212
sepsismedian | median duration | 525 | 525
bpic12mean | bpic12 | 13087 | 36 | mean duration | 8160 | 4927
bpic12median | median duration | 6544 | 6543

Table 2: Dataset description

The results obtained by applying the NegDis algorithm are summarised in Table
3. The table reports for each dataset, the results related to the Subset
(connected to the _generality_ criterion of Eq. 6a and 6b) and Cardinality
(_simplicity_ criterion of Eq. 8a and 8b) optimizations in terms of number of
returned models999We stop generating models after $20$ models, i.e., max in
Table 3 indicates that more than $20$ models have been returned., minimum size
of the returned models, as well as percentage of negative traces violated by
the returned model. Moreover, the table reports the time required for
computing the set of compatibles, the set of choices, as well as the Subset
and Cardinality optimizations.

Dataset | Subset | Cardinality | Required Time (s)
---|---|---|---
Number of | Min model | Violated | Number of | Min model | Violated | Comp. | Choices | Subset | Cardinality
models | size |  $L^{-}$ trace % | models | size |  $L^{-}$ trace %
cervcompl | max | 4 | 100% | max | 4 | 100% | 0.12 | 0.33 | 0.065 | 0.045
sepsismean | 1 | 8 | 4.25% | 1 | 8 | 4.25% | 0.73 | 1.04 | 0.039 | 0.035
sepsismedian | max | 14 | 26.86% | 16 | 14 | 26.86% | 0.45 | 1.5 | 0.2 | 0.087
bpic12mean | max | 12 | 1.42% | max | 12 | 1.42% | 13.51 | 31 | 0.096 | 0.066
bpic12median | max | 23 | 36.59% | max | 22 | 36.59% | 13.32 | 37.63 | 359.164 | 43.846

Table 3: NegDis results on the real-life logs

The table shows that for the cervcompl dataset, NegDis is able to return
models that satisfy the whole set of positive traces and violate the whole set
of negative traces (the percentage of violated traces in $L^{-}$ is equal to
100%) with a very low number of constraints (4). For the other datasets, the
returned models are always able to satisfy all traces in $L^{+}$, however not
all the negative traces are violated by the returned models. In case of the
datasets built by using the mean of the trace cycle time, the percentage of
violated traces is relatively small ($4.25\%$ for sepsismean and $1.24\%$ for
bpic12mean), as the number of constraints of the returned models ($8$ for
sepsismean and $12$ for bpic12mean). Nevertheless, NegDis is able to obtain
reasonable results with the real life datasets built with the median of the
trace cycle time. Indeed, it is able to identify $14$ (resp. $22$-$23$)
constraints able to accept all traces in $L^{+}$ and to cover about $27\%$
(resp. $37\%$) of the traces in $L^{-}$ for sepsismedian (resp. bpic12median).
The difference in terms of results between the cervcompl and the other
datasets is not surprising. Indeed, while what characterizes positive and
negative traces in the cervcompl dataset depends upon the control flow (i.e.,
it depends on whether each execution complies with the cervical cancer
screening protocol adopted by the screening center), when mean and median
cycle time are used, the difference between positive and negative traces could
likely not exclusively depend upon the control flow of the considered traces.
Overall, the inability to identify a set of constraints that is able to fulfil
all traces in $L^{+}$ and to violate all negative ones is due to a bias of the
considered language (Declare without data) that does not allow to explain the
positive traces without the negative ones.

The difference of the results obtained with the mean and the median cycle time
can also be explained as a language bias issue for the specific labelled
datasets. Indeed, while when the positive and negative trace sets are quite
balanced (i.e., for sepsismedian and bpic12median) NegDis is able to identify
a set of constraints (related to the control flow) describing the traces with
a low-medium cycle time and excluding the ones with a medium-high cycle time,
when the sets of the positive and the negative traces are quite imbalanced
(i.e., for sepsismean and BPIC12mean) characterizing the high number of traces
with a low or medium cycle time while excluding the ones with a very high
cycle time can become hard.

The table also shows that NegDis is overall very fast for small datasets
(e.g., less than one minute for cervcompl), while it requires some more time
for large ones (e.g., bpic12mean and bpic12median). While the time required
for computing compatibles and choices seems to be related to the size of the
dataset, the time required for computing the optimizations seems to depend
also on other characteristics of the datasets.

Compared to state-of-the-art techniques for the discovery of declarative
models starting from the only positive traces, NegDis is able to return a
small number of constraints satisfying all traces in $L^{+}$ without
decreasing the percentage of violated traces in $L^{-}$. Among the classical
declarative discovery approach, we selected the state-of-the-art DeclareMiner
algorithm [MDDK18] implemented in the RuM toolkit [ADH+20]. We discovered the
models using the only positive traces and setting the support parameter, which
measures the percentage of (positive) traces satisfied by the Declare model,
to 100%101010We run the DeclareMiner algorithm with vacuity detection
disabled, activity support filter set to 0%, using both transitive closure and
hierarchy-based reduction of the discovered constraints, as well as with the
whole set of Declare templates..

Table 4 summarizes the obtained results. The table reports for each dataset,
the size of the model in terms of number of constraints, as well as the
percentage of negative traces violated by the model. For lower values of the
support parameter, i.e., for a lower percentage of positive traces satisfied
by the model, the model returned by the DeclareMiner violates a higher
percentage of negative traces. In this way, the support parameter allows for
balancing the percentage of positive trace satisfied and negative traces
violated.

As hypothesised, the optimisation mechanism in NegDis is able to identify a
small set of constraints, that guarantees the satisfaction of all traces in
$L^{+}$ and the same percentage of negative trace violations obtained with
DeclareMiner (with support to 100%).

Dataset | Model size | Violated L- trace %
---|---|---
cervcompl | 323 | 100%
sepsismean | 210 | 4.25%
sepsismedian | 202 | 26.86%
bpic12mean | 514 | 1.42%
bpic12median | 532 | 36.59%

Table 4: DeclareMiner results

Finally, we evaluated the results obtained with NegDis relying on the same
procedure and dataset (cervcompl) used in [LMM+07] to assess the results of
DecMiner, a state-of-the-art declarative discovery approach based on Inductive
Logic Programming that is able to use both positive and negative execution
traces. Five fold-cross validation is used, i.e., the cervcompl dataset is
divided into 5 folds and, in each experiment, 4 folds are used for training
and the remaining one for validation purposes. The average _accuracy_ of the
five executions is collected, where the accuracy is defined as the sum of the
number of positive (compliant) traces that are (correctly) satisfied by the
learned model and the number of negative (non-compliant) traces that are
(correctly) violated by the learned model divided by the total number of
traces.

Approach | Accuracy
---|---
DecMiner | 97.44%
DeclareMiner | 96.79%
NegDis (Subset) | 97.38%
NegDis (Cardinality) | 97.57%

Table 5: Accuracy results obtained with DeclareMiner, DecMiner and NegDis

Table 5 reports the obtained accuracy values for the DecMiner, the
DeclareMiner (with the support parameter set to 100%) and the NegDis (both for
the Cardinality and Subset optimization) approach. The table shows that on
this specific dataset, NegDis and DecMiner have very close performance (with
NegDis Cardinality performing slightly better). DeclareMiner presents instead
on average a slightly lower accuracy mainly due to the highly constrained
discovered model that, on one hand, allows for violating all negative traces
in the validation set, and, on the other hand, leads to the violation of some
of the positive traces in the validation set.

##  5 Related work

Process discovery is generally considered a challenging task of process mining
[MBvdA12]. The majority of works in this field are focused on discovering a
business process model from a set of input traces that are supposed compliant
with it. In this sense, process discovery can be seen as the application of a
machine learning technique to extract a grammar from a set of positive sample
data. Angluin et al. [AS83] provide an interesting overview on this wide
field. Differently from grammar learning, where the model is often expressed
with automata, regular expressions or production rules, process discovery
usually adopts formalisms that can express concurrency and synchronization in
a more understandable way [GMVB09]. The language to express the model is a
crucial point, which inevitably influences the learning task itself. Indeed,
the two macro-categories of business process discovery approaches—procedural
and declarative—differ precisely by the type of language to express the
model.Well known examples of procedural process discoverer are the ones
presented in the works [WvdA03, vdAWM04, GvdA07, vdARV+10, LFvdA13, GWW+15,
ACDR17, ACD+19]. Like most procedural approaches to process discovery, all
these works contemplate the presence of non-informative noise in the log,
which should be separated from the rest of the log and disregarded.

Traditional declarative approaches to process discovery stem from the
necessity of a more friendly language to express loosely-structured processes.
Indeed—as also pointed out by [MBvdA12]—process models are sometimes less
structured than one could expect. The application of a procedural discovery
could produce spaghetti-models. In that case, a declarative approach is more
suitable to briefly list all the required or prohibited behaviours in a
business process. Similarly to our technique, the one exposed by Maggi et al.
in [MMvdA11] starts by considering the set of all activities in the log and
building a set of all possible candidate Declare constraints. That work stems
from the idea that Apriori-like approaches—such as sequence mining [AS94] and
episode mining [MTV97]—can discover local patterns in a log, but not rules
representing prohibited behaviours and choices. Therefore, differently from
our algorithm, the candidate Declare constraints are then translated into the
equivalent LTL and checked (one at a time) against all the log content
employing the technique of [vdAdBvD05]. The process continue until certain
levels of recall and specificity are reached. The performance of this
technique is improved in [MBvdA12] with an interesting two-step approach to
both reduce the search space of candidate constraints and exclude from the
model those LTL formulas that are vacuously satisfied. Also the work [SMS12]
by Schunselaar et al. proposes a model refinement to efficiently exclude
vacuously satisfied constraints. The MINERFul approach described in [CSdLM15]
proposes to employ four metrics to guide the declarative discovery approach:
support, confidence and interest factor for each constraint w.r.t. the log,
and the possibility to include in the search space constraints on prohibited
behaviours. Particularly relevant for our purposes is the work by Di Ciccio et
al. [CMMM17], who focus on refining Declare models to remove the frequent
redundancies and inconsistencies. The algorithms and the hierarchy of
constraints described in that work were particularly inspiring to define our
discovery procedure. Similarly to the procedural approaches, all the
declarative ones described so far do not deal with negative example, although
the vast majority of them envisage the possibility to discard a portion of the
log by setting thresholds on the value of specific metrics that the discovered
model should satisfy.

In the wider field of grammar learning, the foundational work by Gold [Gol67]
showed how negative examples are crucial to distinguish the right hypothesis
among an infinite number of grammars that fit the positive examples. Both
positive and negative examples are required to discover a grammar with perfect
accuracy. Since process discovery does not usually seek perfection, but only a
good performance according to defined metrics, it is not surprising that many
procedural and declarative discoverers disregard the negative examples.
Nonetheless, in this work we instead claim that negative traces are extremely
important when learning declarative process models.

The information contained in the negative examples is actively used in a
subset of the declarative process discovery approaches [LMRS07, CLM+09, BRL10,
BRL16]. All these works can be connected to the basic principles of the ICL
(ICL) algorithm [RL95], whose functioning principle is intrinsically related
to the availability of both negative and positive examples. The DPML (DPML)
described in [LMRS07, LMM+07] by Lamma et al. focuses on learning integrity
constraints expressed as logical formulas. The constraints are later
translated into an equivalent construct of the declarative graphical language
DecSerFlow [vdAP06]. Similarly to this approach, the DecMiner tool described
in [CLM+09], learns a set of SCIFF rules [ACG+08] which correctly classify an
input set of labelled examples. Such rules are then translated into ConDec
constraints [PvdA06]. Differently from [CLM+09], the present work directly
learns Declare constraints without any intermediate language. DPML has been
later used in [BRL10] to extract integrity constraints, then converted into
Markov Logic formulas. The weight of each formula is determined with a
statistical relational learning tool. Taking advantage of the negative
examples, the approach of [BRL10] is improved in [BRL16], thus obtaining
significantly better results than other process discovery techniques. Since
for all these works the availability of negative examples is crucial, recent
years have seen the development of synthetical log generators able to produce
not only positive but also negative process cases [CDG+19, CCLM17, LCCM20,
GMVB09, SA14, vHL10]. In the experimental evaluation of this work, we employ
the abductive-logic generator by Loreti et al. [LCCM20] to synthesise part of
the input event logs.

Particularly related to our approach are the works by Neider et al. [NG18],
Camacho et al. [CM19], and Reiner [Rie19] where a SAT-based solver is employed
to learn a simple set of LTL formulas consistent with an input data set of
positive and negative examples. In particular, Neider et al. [NG18] employ
decision tree to improve the performance and manage large example sets;
Camacho et al. [CM19] exploit the correspondence of LTL formulae with
Alternating Finite Automata (AFA); whereas Reiner uses partial Directed
Acyclic Graphs (DAGs) to decompose the search space into smaller subproblems.
The concept of negative example used in this work could be related to both the
definitions of syntactical and semantic noise of [Gün09]. In particular,
besides being able to extract relevant syntactic information that characterise
the positive examples w.r.t. negative, our approach could also be useful to
deal with the semantic concept of modification noise i.e., the semantic
difference between traces from the same process model, which has been
partially or totally modified at a certain point in time. As a minor point, we
also might notice that these works provides in output LTL formulas, while we
opt for Declare formulas with LTLf semantics.

It is important to underline that also a limited number of procedural
approaches envisage the need for taking into account the information contained
into the negative examples. In particular, the work [dLRC+15] showed how
negative examples can be employed to alleviate problems like log
incompleteness and noise. The AGNEs tool described in [GMVB09] increases the
dimension of an event log with artificially generated negative examples, then
uses ILP (ILP) multi-relational classification to discover a Petri net model.
Negative examples are generated in a rather syntactical way, by adding a
unique negative event at the end of a positive trace. This concept is extended
in the work of Ponce de Leon et al. [dLNCvB18] which envisage the
concatenations of a sequence of negative events. Differently from these
approaches, our technique does not assume syntactical restrictions on the
input negative examples.

ILP is also used in [FF06], where the authors suppose a set of negative
examples provided by domain experts. The approach uses partial-order planning
to discover a structured model. More recently, the works [vBWVB14, vB14]
showed how synthetically generated traces can be employed to improve the
robustness of the compliance monitor task.

Deviant cases—intended as traces whose sequence of activities deviates from
the expected behaviour—are the subject of deviance mining approaches reviewed
and evaluated by Nguyen et al. in [NDR+16]. Some applications of deviance
mining tend to highlight the differences between models discovered from
deviant and non-deviant traces [SMW+14, ABDG14]. Other works intend deviance
mining as a classification task, where the miner is required to identify
normal and deviant traces given a set of examples. The classification
inherently causes the discovery of patterns which distinguish different types
of traces. In this sense, deviance mining is particularly similar to sequence
classification. The discovered patterns can be based on the simple frequency
of individual activities as in [SWO+13, PWS+15], their co-occurrence as in
[SDJV11], or the occurrence of specific subsequences [BvdA13, LKL07, BCDM16].

##  6 Conclusion

While the vast majority of works see process discovery as a one-class
supervised learning task, we embrace the less popular view of process
discovery as a binary supervised learning job, where traces representing a
“stranger” behaviour can be considered as heralds of valuable information
about the process itself. Devoted to this vision, we developed a technique
which considers both positive and negative traces and performs process
discovery as a satisfiability problem, where different heuristics can be
adopted to assess the optimal model according to different goals.

Being able to extract valuable knowledge from negative examples, our proposal
NegDis can be employed to enrich the process description extracted by a state-
of-the-art declarative process discovery algorithm. However, it is worth to
underline that the resulting declarative process discoverer taking advantage
of explicitly defined positive and negative examples would not be necessarily
an alternative to procedural discovery techniques. Indeed in some cases, when
correct thresholds and language biases are adopted, procedural discoverers
have the great advantage to provide the user with a rather easy-to-understand
definition of the process model. Nonetheless, the informative content provided
by those process cases that are discarded by procedural discoverer can still
be extremely important. For the future, as NegDis extracts valuable
information from $L^{-}$ without excluding any trace of $L^{+}$, it could also
be applied as a post processing technique to enrich the output of procedural
discoverers with declarative constraints. The resulting output would be an
hybrid procedural/declarative process model, showing a simple and handy
structured representation of the main business process together with a set of
declarative constraints. The goal of such constraints would be to account for
less frequent deviances or prohibited behaviours in a much more synthetic and
easy-to-understand way with respect to an equivalent spaghetti-like procedural
formulation.

Furthermore, such a hybrid solution could also greatly simplifying the
elicitation of long-term dependencies between activities that occur at the
beginning of the process and those carried out towards the end. Indeed, the
structured nature of procedural approaches makes them not properly suitable to
express such dependencies. One current way to tackle such issue is through the
employment of global variables and “if” statements to control the execution
flow of each instance. For example, Kalenkova et al. [KCPR20] propose a
process discovery technique devoted to repair free-choice procedural workflows
with additional modelling constructs, which can more easily capture non-local
dependencies. Nonetheless, since such additional constraints are intended to
preserve the procedural nature of the model, the result may increase its
complexity and ultimately affect its readability. An hybrid
procedural/declarative model formulation would maintain a structured form to
express the model while integrating it with handy declarative long-term
constraints involving activities occurring far from each other in the
workflow. This idea of a hybrid procedural/declarative model formulation has
been explored by various works and proved to be particularly effective in the
field of medical clinical guidelines [BCM+09b, BCM+09a, BCM+11]. A wider
landscape of applications is considered by Maggi et al. in the work [MMCA18].

Finally, the performance of NegDis presented in this paper could be boosted
through a parallel approach. Analogously to previous works [MDDK18, LCCM18,
LLT20] we can envisage two possible directions to decompose our task: by
spitting the model (i.e. in this case the set of constraints to be learned),
or the input data (i.e. the business log). The algorithm presented here could
easily adopt the first kind of partitioning, whereas the second might be more
challenging.

## Acknowledgment

This work was partially supported by the European Commission funded project
“Humane AI: Toward AI Systems That Augment and Empower Humans by Understanding
Us, our Society and the World Around Us” (grant # 820437). The support is
gratefully acknowledged.

## References

  * [ABDG14] Abel Armas-Cervantes, Paolo Baldan, Marlon Dumas, and Luciano García-Bañuelos.  Behavioral comparison of process models based on canonically reduced event structures.  In BPM, volume 8659 of Lecture Notes in Computer Science, pages 267–282. Springer, 2014.
  * [ACD+19] Adriano Augusto, Raffaele Conforti, Marlon Dumas, Marcello La Rosa, Fabrizio Maria Maggi, Andrea Marrella, Massimo Mecella, and Allar Soo.  Automated discovery of process models from event logs: Review and benchmark.  IEEE Trans. Knowl. Data Eng., 31(4):686–705, 2019.
  * [ACDR17] Adriano Augusto, Raffaele Conforti, Marlon Dumas, and Marcello La Rosa.  Split miner: Discovering accurate and simple business process models from event logs.  In ICDM, pages 1–10. IEEE Computer Society, 2017.
  * [ACG+08] Marco Alberti, Federico Chesani, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni.  Verifiable agent interaction in abductive logic programming: The SCIFF framework.  ACM Trans. Comput. Log., 9(4):29:1–29:43, 2008.
  * [ADH+20] Anti Alman, Claudio Di Ciccio, Dominik Haas, Fabrizio Maria Maggi, and Alexander Nolte.  Rule mining with rum.  In Boudewijn F. van Dongen, Marco Montali, and Moe Thandar Wynn, editors, 2nd International Conference on Process Mining, ICPM 2020, Padua, Italy, October 4-9, 2020, pages 121–128. IEEE, 2020.
  * [AMC+15] 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 Bus. Manag., 13(1):37–67, 2015.
  * [AS83] Dana Angluin and Carl H. Smith.  Inductive inference: Theory and methods.  ACM Comput. Surv., 15(3):237–269, 1983.
  * [AS94] Rakesh Agrawal and Ramakrishnan Srikant.  Fast algorithms for mining association rules in large databases.  In VLDB, pages 487–499. Morgan Kaufmann, 1994.
  * [BCDM16] Mario Luca Bernardi, Marta Cimitile, Chiara Di Francescomarino, and Fabrizio Maria Maggi.  Do activity lifecycles affect the validity of a business rule in a business process?  Inf. Syst., 62:42–59, 2016.
  * [BCM+09a] Alessio Bottrighi, Federico Chesani, Paola Mello, Gianpaolo Molino, Marco Montali, Stefania Montani, Sergio Storari, Paolo Terenziani, and Mauro Torchio.  A hybrid approach to clinical guideline and to basic medical knowledge conformance.  In AIME, volume 5651 of Lecture Notes in Computer Science, pages 91–95, 2009.
  * [BCM+09b] Alessio Bottrighi, Federico Chesani, Paola Mello, Marco Montali, Stefania Montani, Sergio Storari, and Paolo Terenziani.  Analysis of the GLARE and GPROVE approaches to clinical guidelines.  In KR4HC, volume 5943 of Lecture Notes in Computer Science, pages 76–87. Springer, 2009.
  * [BCM+11] Alessio Bottrighi, Federico Chesani, Paola Mello, Marco Montali, Stefania Montani, and Paolo Terenziani.  Conformance checking of executed clinical guidelines in presence of basic medical knowledge.  In Business Process Management Workshops (2), volume 100 of Lecture Notes in Business Information Processing, pages 200–211. Springer, 2011.
  * [BRL10] Elena Bellodi, Fabrizio Riguzzi, and Evelina Lamma.  Probabilistic logic-based process mining.  In CILC, volume 598 of CEUR Workshop Proceedings. CEUR-WS.org, 2010.
  * [BRL16] Elena Bellodi, Fabrizio Riguzzi, and Evelina Lamma.  Statistical relational learning for workflow mining.  Intell. Data Anal., 20(3):515–541, 2016.
  * [BvdA13] R. P. Jagadeesh Chandra Bose and Wil M. P. van der Aalst.  Discovering signature patterns from event logs.  In CIDM, pages 111–118. IEEE, 2013.
  * [CCLM17] Federico Chesani, Anna Ciampolini, Daniela Loreti, and Paola Mello.  Abduction for generating synthetic traces.  In Business Process Management Workshops, volume 308 of Lecture Notes in Business Information Processing, pages 151–159. Springer, 2017\.
  * [CDG+19] Federico Chesani, Chiara Di Francescomarino, Chiara Ghidini, Daniela Loreti, Fabrizio Maria Maggi, Paola Mello, Marco Montali, Vasyl Skydanienko, and Sergio Tessaris.  Towards the generation of the "perfect" log using abductive logic programming.  In CILC, volume 2396 of CEUR Workshop Proceedings, pages 179–192. CEUR-WS.org, 2019.
  * [CLM+09] Federico Chesani, Evelina Lamma, Paola Mello, Marco Montali, Fabrizio Riguzzi, and Sergio Storari.  Exploiting inductive logic programming techniques for declarative process mining.  Trans. Petri Nets Other Model. Concurr., 2:278–295, 2009.
  * [CM19] Alberto Camacho and Sheila A. McIlraith.  Learning interpretable models expressed in linear temporal logic.  In ICAPS, pages 621–630. AAAI Press, 2019.
  * [CMMM17] Claudio Di Ciccio, Fabrizio Maria Maggi, Marco Montali, and Jan Mendling.  Resolving inconsistencies and redundancies in declarative process models.  Inf. Syst., 64:425–446, 2017.
  * [CSdLM15] Claudio Di Ciccio, Mitchel H. M. Schouten, Massimiliano de Leoni, and Jan Mendling.  Declarative process discovery with minerful in prom.  In BPM (Demos), volume 1418 of CEUR Workshop Proceedings, pages 60–64. CEUR-WS.org, 2015.
  * [dLNCvB18] Hernán Ponce de León, Lucio Nardelli, Josep Carmona, and Seppe K. L. M. vanden Broucke.  Incorporating negative information to process discovery of complex systems.  Inf. Sci., 422:480–496, 2018.
  * [dLRC+15] Hernán Ponce de León, César Rodríguez, Josep Carmona, Keijo Heljanko, and Stefan Haar.  Unfolding-based process discovery.  In ATVA, volume 9364 of Lecture Notes in Computer Science, pages 31–47. Springer, 2015.
  * [DRMR18] Marlon Dumas, Marcello La Rosa, Jan Mendling, and Hajo A. Reijers.  Fundamentals of Business Process Management, Second Edition.  Springer, 2018.
  * [FF06] Hugo M. Ferreira and Diogo R. Ferreira.  An integrated life cycle for workflow management based on learning and planning.  Int. J. Cooperative Inf. Syst., 15(4):485–505, 2006.
  * [FLM+09] Dirk Fahland, Daniel Lübke, Jan Mendling, Hajo A. Reijers, Barbara Weber, Matthias Weidlich, and Stefan Zugal.  Declarative versus imperative process modeling languages: The issue of understandability.  In BMMDS/EMMSAD, volume 29 of LNBIP, pages 353–366. Springer, 2009.
  * [GKKS14] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten Schaub.  Clingo = ASP + control: Preliminary report.  CoRR, abs/1405.3694, 2014.
  * [GMVB09] Stijn Goedertier, David Martens, Jan Vanthienen, and Bart Baesens.  Robust process discovery with artificial negative events.  J. Mach. Learn. Res., 10:1305–1340, 2009.
  * [Gol67] E. Mark Gold.  Language identification in the limit.  Inf. Control., 10(5):447–474, 1967.
  * [Gün09] Christian W. Günther.  Process Mining in Flexible Environments.  PhD thesis, Technische Universiteit Eindhoven, 2009.
  * [GV13] Giuseppe De Giacomo and Moshe Y. Vardi.  Linear temporal logic and linear dynamic logic on finite traces.  In Francesca Rossi, editor, IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pages 854–860. IJCAI/AAAI, 2013.
  * [GvdA07] Christian W. Günther and Wil M. P. van der Aalst.  Fuzzy mining - adaptive process simplification based on multi-perspective metrics.  In BPM, volume 4714 of Lecture Notes in Computer Science, pages 328–343. Springer, 2007.
  * [GWW+15] Qinlong Guo, Lijie Wen, Jianmin Wang, Zhiqiang Yan, and Philip S. Yu.  Mining invisible tasks in non-free-choice constructs.  In BPM, volume 9253 of Lecture Notes in Computer Science, pages 109–125. Springer, 2015.
  * [KCPR20] Anna A. Kalenkova, Josep Carmona, Artem Polyvyanyy, and Marcello La Rosa.  Automated repair of process models using non-local constraints.  In Petri Nets, volume 12152 of Lecture Notes in Computer Science, pages 280–300. Springer, 2020.
  * [LCCM18] Daniela Loreti, Federico Chesani, Anna Ciampolini, and Paola Mello.  A distributed approach to compliance monitoring of business process event streams.  Future Gener. Comput. Syst., 82:104–118, 2018.
  * [LCCM20] Daniela Loreti, Federico Chesani, Anna Ciampolini, and Paola Mello.  Generating synthetic positive and negative business process traces through abduction.  Knowl. Inf. Syst., 62(2):813–839, 2020.
  * [LFvdA13] Sander J. J. Leemans, Dirk Fahland, and Wil M. P. van der Aalst.  Discovering block-structured process models from event logs - A constructive approach.  In Petri Nets, volume 7927 of Lecture Notes in Computer Science, pages 311–329. Springer, 2013.
  * [Lif08] Vladimir Lifschitz.  What is answer set programming?  In AAAI, pages 1594–1597. AAAI Press, 2008.
  * [LKL07] David Lo, Siau-Cheng Khoo, and Chao Liu.  Efficient mining of iterative patterns for software specification discovery.  In KDD, pages 460–469. ACM, 2007.
  * [LLT20] Daniela Loreti, Marco Lippi, and Paolo Torroni.  Parallelizing machine learning as a service for the end-user.  Future Gener. Comput. Syst., 105:275–286, 2020.
  * [LMM+07] Evelina Lamma, Paola Mello, Marco Montali, Fabrizio Riguzzi, and Sergio Storari.  Inducing declarative logic-based models from labeled traces.  In Gustavo Alonso, Peter Dadam, and Michael Rosemann, editors, Business Process Management, pages 344–359, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.
  * [LMRS07] Evelina Lamma, Paola Mello, Fabrizio Riguzzi, and Sergio Storari.  Applying inductive logic programming to process mining.  In ILP, volume 4894 of Lecture Notes in Computer Science, pages 132–146. Springer, 2007.
  * [Man16] Felix Mannhardt.  Sepsis cases - event log, Dec 2016.
  * [MBvdA12] Fabrizio Maria Maggi, R. P. Jagadeesh Chandra Bose, and Wil M. P. van der Aalst.  Efficient discovery of understandable declarative process models from event logs.  In CAiSE, volume 7328 of Lecture Notes in Computer Science, pages 270–285. Springer, 2012.
  * [MDDK18] Fabrizio Maria Maggi, Claudio Di Ciccio, Chiara Di Francescomarino, and Taavi Kala.  Parallel algorithms for the automated discovery of declarative process models.  Inf. Syst., 74(Part):136–152, 2018.
  * [MMCA18] Fabrizio Maria Maggi, Andrea Marrella, Giuseppe Capezzuto, and Abel Armas-Cervantes.  Explaining non-compliance of business process models through automated planning.  In ICSOC, volume 11236 of Lecture Notes in Computer Science, pages 181–197. Springer, 2018.
  * [MMvdA11] Fabrizio Maria Maggi, Arjan J. Mooij, and Wil M. P. van der Aalst.  User-guided discovery of declarative process models.  In CIDM, pages 192–199. IEEE, 2011.
  * [MPvdA+10] Marco Montali, Maja Pesic, Wil M. P. van der Aalst, Federico Chesani, Paola Mello, and Sergio Storari.  Declarative specification and verification of service choreographiess.  ACM Trans. Web, 4(1):3:1–3:62, 2010.
  * [MTV97] Heikki Mannila, Hannu Toivonen, and A. Inkeri Verkamo.  Discovery of frequent episodes in event sequences.  Data Min. Knowl. Discov., 1(3):259–289, 1997.
  * [MWvdAvdB06] Laura Maruster, A. J. M. M. Weijters, Wil M. P. van der Aalst, and Antal van den Bosch.  A rule-based approach for process discovery: Dealing with noise and imbalance in process logs.  Data Min. Knowl. Discov., 13(1):67–87, 2006.
  * [NDR+16] Hoang Nguyen, Marlon Dumas, Marcello La Rosa, Fabrizio Maria Maggi, and Suriadi Suriadi.  Business process deviance mining: Review and evaluation.  CoRR, abs/1608.08252, 2016.
  * [NG18] Daniel Neider and Ivan Gavran.  Learning linear temporal properties.  In FMCAD, pages 1–10. IEEE, 2018.
  * [Pes08] M. Pesic.  Constraint-based workflow management systems : shifting control to users.  PhD thesis, Industrial Engineering & Innovation Sciences, 2008.
  * [PvdA06] Maja Pesic and Wil M. P. van der Aalst.  A declarative approach for flexible business processes management.  In Business Process Management Workshops, volume 4103 of Lecture Notes in Computer Science, pages 169–180. Springer, 2006.
  * [PWS+15] Andrew Partington, Moe Thandar Wynn, Suriadi Suriadi, Chun Ouyang, and Jonathan Karnon.  Process mining for clinical processes: A comparative analysis of four australian hospitals.  ACM Trans. Management Inf. Syst., 5(4):19:1–19:18, 2015.
  * [Rie19] Heinz Riener.  Exact synthesis of LTL properties from traces.  In FDL, pages 1–6. IEEE, 2019.
  * [RL95] Luc De Raedt and Wim Van Laer.  Inductive constraint logic.  In ALT, volume 997 of Lecture Notes in Computer Science, pages 80–94. Springer, 1995.
  * [SA14] Thomas Stocker and Rafael Accorsi.  Secsy: A security-oriented tool for synthesizing process event logs.  In BPM (Demos), volume 1295 of CEUR Workshop Proceedings, page 71. CEUR-WS.org, 2014.
  * [SDJV11] Jo Swinnen, Benoît Depaire, Mieke J. Jans, and Koen Vanhoof.  A process deviation analysis - A case study.  In Business Process Management Workshops (1), volume 99 of Lecture Notes in Business Information Processing, pages 87–98. Springer, 2011.
  * [SMS12] Dennis M. M. Schunselaar, Fabrizio Maria Maggi, and Natalia Sidorova.  Patterns for a log-based strengthening of declarative compliance models.  In IFM, volume 7321 of Lecture Notes in Computer Science, pages 327–342. Springer, 2012.
  * [SMW+14] Suriadi Suriadi, Ronny Mans, Moe Thandar Wynn, Andrew Partington, and Jonathan Karnon.  Measuring patient flow variations: A cross-organisational process mining approach.  In AP-BPM, volume 181 of Lecture Notes in Business Information Processing, pages 43–58. Springer, 2014.
  * [SWO+13] Suriadi Suriadi, Moe Thandar Wynn, Chun Ouyang, Arthur H. M. ter Hofstede, and Nienke J. van Dijk.  Understanding process behaviours in a large insurance company in australia: A case study.  In CAiSE, volume 7908 of Lecture Notes in Computer Science, pages 449–464. Springer, 2013.
  * [van12] van der Aalst, et al.  Process mining manifesto.  In Florian Daniel, Kamel Barkaoui, and Schahram Dustdar, editors, Business Process Management Workshops, pages 169–194, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
  * [vB14] Seppe K. L. M. vanden Broucke.  Advances in Process Mining: Artificial Negative Events and Other Techniques.  PhD thesis, Katholieke Universiteit Leuven, 2014.
  * [VBvDvdA10] H. M. W. Verbeek, Joos C. A. M. Buijs, Boudewijn F. van Dongen, and Wil M. P. van der Aalst.  Xes, xesame, and prom 6.  In CAiSE Forum (Selected Papers), volume 72 of Lecture Notes in Business Information Processing, pages 60–75. Springer, 2010.
  * [vBWVB14] Seppe K. L. M. vanden Broucke, Jochen De Weerdt, Jan Vanthienen, and Bart Baesens.  Determining process model precision and generalization with weighted artificial negative events.  IEEE Trans. Knowl. Data Eng., 26(8):1877–1889, 2014.
  * [vD12] Boudewijn van Dongen.  Bpi challenge 2012, Apr 2012.
  * [vdAdBvD05] Wil M. P. van der Aalst, H. T. de Beer, and Boudewijn F. van Dongen.  Process mining and verification of properties: An approach based on temporal logic.  In OTM Conferences (1), volume 3760 of Lecture Notes in Computer Science, pages 130–147. Springer, 2005.
  * [vdAP06] Wil M. P. van der Aalst and Maja Pesic.  Decserflow: Towards a truly declarative service flow language.  In WS-FM, volume 4184 of Lecture Notes in Computer Science, pages 1–23. Springer, 2006.
  * [vdAPS09] Wil M. P. van der Aalst, Maja Pesic, and Helen Schonenberg.  Declarative workflows: Balancing between flexibility and support.  Comput. Sci. Res. Dev., 23(2):99–113, 2009.
  * [vdARV+10] Wil M. P. van der Aalst, Vladimir A. Rubin, H. M. W. Verbeek, Boudewijn F. van Dongen, Ekkart Kindler, and Christian W. Günther.  Process mining: a two-step approach to balance between underfitting and overfitting.  Software and Systems Modeling, 9(1):87–111, 2010.
  * [vdAWM04] Wil M. P. van der Aalst, Ton Weijters, and Laura Maruster.  Workflow mining: Discovering process models from event logs.  IEEE Trans. Knowl. Data Eng., 16(9):1128–1142, 2004.
  * [vHL10] Kees M. van Hee and Zheng Liu.  Generating benchmarks by random stepwise refinement of petri nets.  In ACSD/Petri Nets Workshops, volume 827 of CEUR Workshop Proceedings, pages 403–417. CEUR-WS.org, 2010.
  * [WvdA03] A. J. M. M. Weijters and Wil M. P. van der Aalst.  Rediscovering workflow models from event-based data using little thumb.  Integr. Comput. Aided Eng., 10(2):151–162, 2003.

  *[BPM]:
  *[XES]:
  *[LTL]:
  *[ASP]:
  *[ICL]:
  *[DPML]:
  *[ILP]: