=Paper=
{{Paper
|id=Vol-3779/paper1
|storemode=property
|title=Probabilistic Compliance in Declarative Process Mining
|pdfUrl=https://ceur-ws.org/Vol-3779/paper1.pdf
|volume=Vol-3779
|authors=Michela Vespa,Elena Bellodi,Federico Chesani,Daniela Loreti,Paola Mello,Evelina Lamma,Anna Ciampolini
|dblpUrl=https://dblp.org/rec/conf/pmai/VespaBCLMLC24
}}
==Probabilistic Compliance in Declarative Process Mining==
https://ceur-ws.org/Vol-3779/paper1.pdf
Probabilistic Compliance in Declarative Process Mining
Michela Vespa1,* , Elena Bellodi1 , Federico Chesani2 , Daniela Loreti2 , Paola Mello2 ,
Evelina Lamma1 and Anna Ciampolini2
1
Dipartimento di Ingegneria, Universitร di Ferrara, Via Saragat 1, Ferrara, Italy
2
Dipartimento di Informatica - Scienza e Ingegneria, Viale Risorgimento 2, Bologna, Italy
Abstract
When addressing real-world processes, it is crucial to account for their intrinsic uncertainty to better reflect the
nature of such processes. In this work, we introduce the concept of Probabilistic Declarative Process Specification
(PDS), which is based on the Distribution Semantics from Probabilistic Logic Programming, in order to describe
declarative process models with both crisp and probabilistic constraints. The probability associated to a constraint
represents its strength or importance in a specific process domain. From this, we propose a novel notion of
probabilistic compliance of a process trace w.r.t. a PDS, and how to compute it with an existing algorithm.
Preliminary experimental results on a healthcare protocol are presented to evaluate the feasibility of our proposed
semantics on process conformance checking.
Keywords
Process Mining, Declarative language, Compliance, Distribution Semantics, Probabilistic Logic Programs
1. Introduction
In the Business Process Mining community, many different languages have been proposed to model/de-
scribe a process, capturing the many aspects of a work process, ranging from the resource perspective, to
the artifact-based and data perspective, up to the control-flow aspects. The latter viewpoint in particular
has been subject to intense research activity. Two families of process modeling languages emerged:
procedural approaches, such as BPMN1 , and declarative ones, such as Declare [1, 2] and DCR Graphs
[3]. Declarative approaches have been introduced to overcome some forms of rigidness derived by
procedural ones, with the aim of finding a balance between flexibility and control. Declare in particular,
was defined with this aim: allowing the specification of which properties a process instance should
exhibit, without specifying the exact steps to achieve them. Since the initial proposal, Declare has
been equipped with a formal semantics based on a strict subset of LTL๐ . This enables a straightforward
specification of process properties through the use of established formulas.
However, the adoption of a logic-based semantics has also raised a practical issue when dealing
with the problem of evaluating if a log is compliant with a process specification. On one side, a log
is composed of many traces; on the other side a Declare process specification is composed of many
constraints. Typically, in real-world applications, different subsets of traces are compliant with different
subsets of constraints. The direct consequence is that a logic-crisp notion of compliance might be
difficult or unsatisfactory to identify. In turn, such difficulty could undermine the capacity of a process
specification to properly describe the process. In a seminal work [4], the authors tackled the problem
by introducing the notion of probabilities into the Declare formalism: each constraint is assigned a
probability (and a relational operator). A probabilistic constraint is satisfied over the log if the number
PMAI@ECAI24: International ECAI Workshop on Process Management in the AI era, October 19, 2024, Santiago De Compostela,
Spain
*
Corresponding author.
โ
These authors contributed equally.
$ michela.vespa@unife.it (M. Vespa); elena.bellodi@unife.it (E. Bellodi); federico.chesani@unibo.it (F. Chesani);
daniela.loreti@unibo.it (D. Loreti); paola.mello@unibo.it (P. Mello); evelina.lamma@unife.it (E. Lamma);
anna.ciampolini@unibo.it (A. Ciampolini)
0009-0004-4350-8151 (M. Vespa); 0000-0002-3717-3779 (E. Bellodi); 0000-0003-1664-9632 (F. Chesani); 0000-0002-6507-7565
(D. Loreti); 0000-0002-5929-8193 (P. Mello); 0000-0003-2747-4292 (E. Lamma); 0000-0002-9314-1958 (A. Ciampolini)
ยฉ 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
1
https://www.bpmn.org/
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
of traces satisfying the constraint over the log cardinality achieves the mathematical relation established
by the relational operator and the probability assigned. As a practical example, a constraint c1 with
assigned probability (0.9, โฅ) is satisfied if the number of traces complaint with c1 is at least (โฅ) the 90%
of the total traces. In summary, probabilities express the relative frequency of traces, and are employed
with such a meaning for the tasks of discovering, monitoring and conformance checking. Nonetheless,
when the available log does not represent the whole process domain, the application of the approach
[4] by domain expert might be challenging.
In this work, we also tackle the problem of probabilistic conformance checking with Declare
constraints, but we propose a different semantics underlying the probabilistic constraints. We introduce
the concept of Probabilistic Declarative Process Specification (PDS) starting from Probabilistic Logic
Programming (PLP) and the Distribution Semantics [5]. A PLP program under that semantics defines a
probability distribution over normal logic programs called worlds. In a PLP program, logic formulas
are equipped with a probability, which is interpreted as the probability of them appearing or not in a
normal logic program. Similarly, the probability of a Declare constraint is treated as the probability
that such constraint will appear (or not) in a possible process specification. The presence or not of a
constraint in a process specification tells us how โimportantโ or strong that constraint is. The stronger
or more important the constraint, the greater its probability. According to the our semantics, all worlds
including one such constraint "inherit" its probability, while those not including the constraint take into
account the complement to 1 of its probability. Differently from [4], this probability does not represent
a fraction of traces satisfying the constraint, but allows one to model uncertainty in the domain by
means of the probability attached to the constraint.
To better clarify our proposal, let us consider the following university course scenario, described
with two constraints: (๐) it is mildly advised that a student only take the final examination if she
has attended all the classes; (๐) it is strongly advised that a student attend a practical session only
if she attended the corresponding preparatory class. Declare provides the way for expressing such
constraints; however, there is no way to specify that rule (๐) is โmildly advisedโ, while rule (๐) is โstrongly
advisedโ. Our proposal consists of attaching probabilities to constraints (๐) and (๐): such values would
indicate the probability that each rule would end up in a possible model (process specification), and
the probability attached to (๐) would be higher than the one attached to (๐). By making (๐) and (๐)
probabilistic, we would find four possible process models, and we can formally define the compliance
of the studentsโ careers (process traces) towards these four models (i.e., worlds in the Distribution
Semantics terminology).
The contribution of this work is the following: we introduce a semantics for probabilistic declarative
process specifications, provide a novel notion of compliance, and ground its application on a health
protocol. Then, we exploit previous results, and in particular (๐) the mapping provided to Declare
in terms of the SCIFF modeling language [6] and (๐๐) the extension of the Distribution Semantics to
Abductive Logic Programming (ALP) in the SCIFF Framework [7]. Thanks to the existing work, we
can implement our proposed semantics and compute a compliance probability. In order to evaluate the
feasibility of our approach, we report some preliminary experimentation over the clinical guideline.
The paper is organized as follows: Section 2 introduces background on Declare and the distribution
semantics, Section 3 describes the proposed semantics, Section 4 describes how we perform probabilistic
compliance. Section 5 presents first experimental results and Section 6 concludes the paper.
2. Background
2.1. Traces, logs, and the Declare modeling language
In the BPM setting [8] the starting point is the observation of a process execution in terms of the
execution of the activities that compose the process. Each execution of the process is usually referred
to as a process instance or trace, where the executions of the distinct activities are referred to as distinct
activity instances or activity executions. Each activity is characterized by at least a name, and each
activity instance is usually denoted with a temporal timestamp. The timestamp provides, within the
(a) The response template. (b) The init template. (c) The precedence template.
Figure 1: Examples of the Declare graphical notation: x and y are placeholders that should be substituted with
proper activity names.
same trace, a relation order between the different activity executions: it is often the case that traces are
represented directly as a sequence of activity names, ordered on the base of the timestamp. Depending
on the specific context, the timestamp can be omitted: this is also our choice.
Formally, we consider the existence of a finite alphabet of symbols ฮฃ corresponding to the activity
names. A trace and a log then are defined as follows:
Definition 1 (Trace ๐ก and Log โ). Given a finite set ฮฃ of symbols (i.e., activity names), a trace ๐ก is a
finite, ordered sequence of symbols over ฮฃ, i.e. ๐ก โ ฮฃ* , where the latter is the infinite set of all the possible
finite sentences over ฮฃ. A log โ is a finite set of traces.
In a process log, each trace ๐ก represents a different process instance. Different process instances may
have the same trace, although referring to different executions.
Example 1. Let us suppose that a process is made of activities a, b, c, and d. ฮฃ = {a, b, c, d}. An example
of a log might be: โ = {๐ก1 = โจa, b, cโฉ, ๐ก2 = โจa, b, a, dโฉ, ๐ก3 = โจa, a, dโฉ, ๐ก4 = โจa, b, cโฉ, ๐ก5 = โจa, b, cโฉ}.
The Declare modeling language was initially introduced by [2] and subsequently studied in [9].
Aimed to overcome the โrigidnessโ of procedural modeling languages, it focuses on modeling processes
by specifying what are the relevant properties that a process instance should exhibit, without specifying
how these properties should be achieved. To this end, Declare models a process in terms of constraints,
sort of rules about activities that can appear in a process execution (i.e., in a trace), with qualitative
temporal relations among these activities. A simple example of a Declare constraint is response(a,b),
meaning that every occurrence of (the execution of) activity a in a trace should be followed by the
occurrence of an activity b.
Declare provides a finite set of constraint patterns, whose arguments should be properly instantiated
with the activity names peculiar to the specific process to be modeled. For example, a common pattern
is response(x,y) with x and y placeholders to be substituted with proper activities. Another pattern is
init(x), that specifies that every process instance should always start with the execution of activity x.
Another common pattern is precedence(x,y), that states that every occurrence of the execution of y
should be preceded by the execution of x.
Declare provides a graphical representation for the patterns (see Figure 1 for a few examples), and
has been equipped with two different formal semantics, both based on logic formalisms. In the original
formulation in [2] the semantics was given using the LTL temporal logic; subsequent works have shown
the feasibility of adopting the LTL๐ logic [10]: for a recent recap see [11]. A second formal semantics
has been proposed in [6], where the SCIFF language and ALP [12] has been exploited.
Both the semantics exploit the idea that each Declare template can be mapped onto one (or more)
logic formula ๐, and that logical entailment can be used to define the notion of compliance/violation of a
trace ๐ก w.r.t. to a constraint formula ๐. With the aim of being the most general, we provide an intuitive
definition of compliance/violation, where the meaning of the entailment symbol |= should be referred
to the chosen semantics (LTL๐ or ALP).
Definition 2 (Compliance/violation of a trace versus a constraint). A trace ๐ก is compliant with a Declare
constraint if, named ๐ the corresponding logic formula modelling that constraint, it holds: ๐ก |= ๐.
A trace ๐ก violates a Declare constraint if it does not entail the corresponding formula ๐, i.e. if ๐ก ฬธ|= ๐.
Definition 3 (Declarative Process Specification, from [11]). A declarative process specification is a
tuple DS=(Rep, ฮฃ, ๐ถ) where:
โข Rep is a finite non-empty set of templates, where each template is a predicate c(๐ฅ1 , . . . , ๐ฅ๐ ) โ Rep
on variables ๐ฅ1 , . . . , ๐ฅ๐ (with ๐ โ N the arity of c);
โข ฮฃ is a finite non-empty set of activity names;
โข ๐ถ is a finite set of constraints, obtained by instantiating templates from Rep to ฮฃ; we will compactly
denote such constraints with c(๐1 , . . . , ๐๐ ), ๐1 , . . . , ๐๐ โ ฮฃ.
Usually the constraints c(๐1 , . . . , ๐๐ ) in a DS are considered as being in logical conjunction. The
notion of compliance can be then lifted from a trace vs. a constraint towards a trace vs. a DS as follows:
Definition 4 (Compliance of a trace versus a Declarative Process Specification). A trace is compliant
with a DS if it entails the conjunction of the formulas ๐๐ corresponding to the ๐๐ โ ๐ถ:
๐ก |= ๐1 โง . . . โง ๐๐
where ๐ is the cardinality of ๐ถ.
Example 2. Let us consider the log introduced in Example 1, and the following DS (Rep and ฮฃ are omitted
for the sake of simplicity):
๐ถ={ c1 = response(a,b)
c2 = init(a) }
Even without considering the corresponding formal semantics, we can notice that:
โข ๐ก1 , ๐ก4 , and ๐ก5 are compliant with c1 ;
โข ๐ก2 is not compliant with c1 because the second occurrence of activity a is not followed by an occurrence
of activity b;
โข ๐ก3 is not compliant with c1 because two occurrences of a are not followed by an occurrence of b;
โข ๐ก1 , . . . , ๐ก5 are all compliant with c2 .
2.2. Distribution Semantics and Probabilistic Logic Programming
Probabilistic Logic Programming has recently received an increasing attention for its ability to incor-
porate probability in logic programming. Among various proposals for PLP, the one based on the
distribution semantics [5] has gained popularity as being introduced for the PRISM language [5] but
is the basis for many other languages such as Probabilistic Logic Programs [13], Probabilistic Horn
Abduction (PHA) [14], Independent Choice Logic (ICL) [15], pD [16], Logic Programs with Annotated
Disjunctions (LPADs) [17], ProbLog [18] and CP-logic [19]. Such semantics is particularly appealing for
its intuitiveness and because efficient inference algorithms were proposed. By combining probability
with logic programming, PLP languages are a suitable framework to handle uncertain information.
A program in one of these languages defines a probability distribution over normal logic programs
called worlds. The distribution semantics has been defined both for programs that do not contain
function symbols, and thus have a finite set of worlds, and for programs that contain them, that have
an infinite set of worlds. We consider here the first case for the sake of simplicity, for the treatment of
function symbols see [20]. A survey of the distribution semantics in PLP can be found in [21]. In the
following, the distribution semantics will be described with reference to LPADs. Formally, an LPAD
consists of a finite set of "annotated disjunctive clauses", where the head is a disjunction in which each
atom is annotated with a probability. If the body holds true, only one of the atoms in the head will be
true with the associated probability. An annotated disjunctive clause ๐
๐ is of the form
โ๐1 : ๐๐1 ; . . . ; โ๐๐๐ : ๐๐๐๐ : โ ๐๐1 , . . . , ๐๐๐๐ ,
where
โ๏ธโ๐1 , . . . , โ๐๐๐ are logical atoms and {๐๐1 , . . . , ๐๐๐๐ } are real โ๏ธ
numbers in the interval [0, 1] such
that ๐๐=1
๐
๐๐๐ โค 1; ๐๐1 , . . . , ๐๐๐๐ is indicated with ๐๐๐๐ฆ(๐
๐ ). If ๐๐=1 ๐
๐๐๐ < 1, the head implicitly
contains
โ๏ธ ๐ an extra atom ๐๐ข๐๐ that does not appear in the body of any clause and whose annotation is
1 โ ๐๐=1 ๐๐๐ . We denote by ๐๐๐๐ข๐๐(๐ ) the grounding of an LPAD ๐ .
An atomic choice [15] is a triple (๐
๐ , ๐๐ , ๐) where ๐
๐ โ ๐ , ๐๐ is a substitution that grounds ๐
๐ and
๐ โ {1, . . . , ๐๐ } identifies one of the head atoms. (๐
๐ , ๐๐ , ๐) means that, for the ground clause ๐
๐ ๐๐ ,
the head โ๐๐ was chosen. A set of atomic choices ๐
is consistent if only one head is selected from the
same ground clause; we assume independence between the different choices. A composite choice ๐
is a
consistent set of atomic choices [15]. The probability ๐ (๐
) of โ๏ธ a composite choice ๐
is the product of the
probabilities of the independent atomic choices, i.e. ๐ (๐
) = (๐
๐ ,๐๐ ,๐)โ๐
๐๐๐ .
A selection ๐ is a composite choice that, for each clause ๐
๐ ๐๐ in ๐๐๐๐ข๐๐(๐ ), contains an atomic
choice (๐
๐ , ๐๐ , ๐). Let us indicate with ๐๐ the set of all selections. A selection ๐ identifies a normal
logic program ๐ค๐ defined as ๐ค๐ = {(โ๐๐ โ ๐๐๐๐ฆ(๐
๐ ))๐๐ |(๐
๐ , ๐๐ , ๐) โ ๐}. ๐ค๐ is called a (possible)
world of โ๏ธ
๐ . Since selections are composite choices, we can assign a probability to worlds: ๐ (๐ค๐ ) =
๐ (๐) = (๐
๐ ,๐๐ ,๐)โ๐ ๐๐๐ .
โ๏ธWe denote the set of all worlds of ๐ by ๐๐ . ๐ (๐๐ ) is a probability distribution over worlds, i.e.,
๐คโ๐๐ ๐ (๐ค) = 1. A composite choice ๐
identifies a set of worlds ๐ค๐
= {๐ค๐ |๐ โ ๐๐ , ๐ โ ๐
}.
Similarly we can define the set of possible worlds associated to a set of composite choices ๐พ: ๐๐พ =
.
โ๏ธ
๐ค
๐
โ๐พ ๐
Example 3. Consider the following LPAD T encoding the effect of flu and hay fever on the sneezing
symptom.
(๐
1 ) ๐ ๐ก๐๐๐๐_๐ ๐๐๐๐ง๐๐๐(๐) : 0.3; ๐๐๐๐๐๐๐ก๐_๐ ๐๐๐๐ง๐๐๐(๐) : 0.5 : โ๐ ๐๐ข(๐).
(๐
2 ) ๐ ๐ก๐๐๐๐_๐ ๐๐๐๐ง๐๐๐(๐) : 0.2; ๐๐๐๐๐๐๐ก๐_๐ ๐๐๐๐ง๐๐๐(๐) : 0.6 : โโ๐๐ฆ_๐ ๐๐ฃ๐๐(๐).
(๐
3 ) ๐ ๐๐ข(๐๐๐).
(๐
4 ) โ๐๐ฆ_๐ ๐๐ฃ๐๐(๐๐๐).
If somebody has the flu or hay fever, there is the possibility that he experiences sneezing symptoms with
different intensity: if she has the flu, then she might show strong sneezing with probability 0.3, or moderate
sneezing with probability 0.5; similarly for the second clause. She might not experience any symptom with
probability 0.2 in both cases. We know for sure that Bob has both the flu and hay fever. ๐ has 3 ยท 3 = 9
worlds, as each probabilistic clause has one grounding ๐1 = {๐/๐๐๐}. Worlds are shown in Table 1.
Table 1
Worlds for Example 3. The probabilities of the worlds sum up to 1.
World id World ๐ (๐ค)
strong_sneezing(bob):-flu(bob).
๐ค1 strong_sneezing(bob):-hay_fever(bob). 0.3ร0.2 = 0.06
flu(bob). hay_fever(bob).
strong_sneezing(bob):-flu(bob).
๐ค2 moderate_sneezing(bob):-hay_fever(bob). 0.3ร0.6=0.18
flu(bob). hay_fever(bob).
strong_sneezing(bob):-flu(bob).
๐ค3 0.3ร0.2=0.06
flu(bob). hay_fever(bob).
moderate_sneezing(bob):-flu(bob).
๐ค4 strong_sneezing(bob):-hay_fever(bob). 0.5ร0.2=0.1
flu(bob). hay_fever(bob).
moderate_sneezing(bob):-flu(bob).
๐ค5 moderate_sneezing(bob):-hay_fever(bob). 0.5ร0.6=0.3
flu(bob). hay_fever(bob).
moderate_sneezing(bob):-flu(bob).
๐ค6 0.5ร0.2=0.1
flu(bob). hay_fever(bob).
strong_sneezing(bob):-hay_fever(bob).
๐ค7 0.2ร0.2=0.04
flu(bob). hay_fever(bob).
moderate_sneezing(bob):-hay_fever(bob).
๐ค8 0.2ร0.6=0.12
flu(bob). hay_fever(bob).
๐ค9 flu(bob). hay_fever(bob). 0.2ร0.2=0.04
Given a goal G, its probability ๐ (๐บ) can be defined by marginalizing the joint probability of the goal
and the worlds:
โ๏ธ โ๏ธ โ๏ธ
๐ (๐บ) = ๐ (๐บ, ๐ค) = ๐ (๐บ|๐ค)๐ (๐ค) = ๐ (๐ค) (1)
๐คโ๐๐ ๐คโ๐๐ ๐คโ๐๐ :๐ค|=๐บ
The probability of a goal ๐บ given a world ๐ค is ๐ (๐บ|๐ค) = 1 if ๐ค |= ๐บ and 0 otherwise. ๐ (๐ค) =
๐ (๐ค๐ ) = ๐ (๐), i.e. is the product of the annotations ๐๐๐ of the atoms selected in ๐. Therefore, the
probability of a goal G can be computed by summing the probability of the worlds where the goal is
true. In practice, given a goal to solve, it is unfeasible to enumerate all the worlds where ๐บ is entailed.
Inference algorithms, instead, find explanations for a goal: a composite choice ๐
is an explanation for
๐บ if ๐บ is entailed by every world of ๐ค๐
. In particular, algorithms find a covering set of explanations
w.r.t. ๐บ, where a set of composite choices ๐พ is covering with respect to ๐บ if every program ๐ค๐ โ ๐๐
in which ๐บ is entailed is in ๐ค๐พ .
3. Probabilistic Declarative Process Specifications under the
Distribution semantics
In this Section, we propose a semantics for Declarative Process Specifications that is highly inspired by
the Distribution Semantics introduced in Section 2.2. First of all, we introduce the notion of probabilistic
constraint. Please note that also in Definition 8 of [4] it is adopted the term probabilistic constraint, but
that definition includes also a relational operator that we do not need in our semantics.
Definition 5 (Probabilistic Constraint). Given a finite, non-empty set Rep of constraint templates and a
set ฮฃ of activity names ๐1 , . . . , ๐๐ , a probabilistic constraint is a constraint template c โ Rep instantiated
over ฮฃ that is annotated with a real number ๐ โ [0..1] (the probability of the constraint). We will indicate
a generic ๐-th probabilistic constraint with the syntax:
๐๐ :: c๐ (๐1 , . . . , ๐๐ )
The probability is to be interpreted as the strength or importance of c๐ . The stronger or more important
the constraint, the greater its probability. By applying the Distribution Semantics, a constraint c๐ (. . .)
will have a probability ๐๐ of being part of a Probabilistic Declarative Process Specification, defined as
follows:
Definition 6 (Probabilistic Declarative Process Specification). A Probabilistic Declarative Process
Specification PDS is a Declarative Process Specification DS where each constraint c๐ โ ๐ท๐ is a probabilistic
constraint.
We will refer to constraints annotated with probability ๐๐ = 1 as crisp constraints. If all the constraints
have probability equal to 1, we simply end up having a Declarative Specification as in Def. 3. Probabilities
will be omitted when they are equal to 1. We now propose to interpret the probability ๐๐ of a constraint
borrowing a few concepts from Section 2.2.
Definition 7 (Atomic Choice, and its probability). An atomic choice over a probabilistic constraint
๐๐ :: c๐ is a couple (c๐ , ๐) where ๐ โ {0, 1}. ๐ indicates whether c๐ is chosen to be included in a PDS with
probability ๐๐ (e = 1), or not with probability 1 โ ๐๐ (e = 0).
Note that here we do not need the substitution ๐ as in the definition of atomic choice in subsection
2.2, since, according to Def. 5, the constraint c๐ is ground.
Definition 8 (Composite Choice, and its probability). A set of atomic choices ๐
is consistent if there is
only one choice in ๐
for each probabilistic constraint c๐ ; we assume independence between the different
atomic choices. A composite choice ๐
is a consistent set of atomic
โ๏ธ choices. โ๏ธ
The probability ๐ (๐
) of a composite choice ๐
is ๐ (๐
) = (c๐ ,1)โ๐
๐๐ (c๐ ,0)โ๐
(1 โ ๐๐ ), where ๐๐ is
the probability associated with c๐ .
Definition 9 (Selection ๐ over a PDS, and its probability). A selection ๐ over a Probabilistic Declarative
Process Specification is a composite choice that contains an atomic choice (c๐ , ๐) for every probabilistic
constraint of the PDS. A selection ๐ identifies
โ๏ธ โ๏ธ in this way: ๐ค๐ = {c๐ |(c๐ , 1) โ ๐}. The probability
a world
of a world ๐ค๐ is ๐ (๐ค๐ ) = ๐ (๐) = (c๐ ,1)โ๐ ๐๐ (c๐ ,0)โ๐ (1 โ ๐๐ ).
Definition 10 (Probability of a DS). Given the set of all selections ๐๐ over a Probabilistic Declarative
Process Specification, every world ๐ค๐๐ identified by a selection ๐๐ โ ๐๐ is a different Declarative Process
Specification ๐ท๐๐ , and its probability is ๐ (๐ท๐๐ ) = ๐ (๐ค๐๐ ) = ๐ (๐๐ ).
A PDS defines a probability distribution over regular (non-probabilistic) DSs that correspond to
worlds. Let us consider the following example to better illustrate this concept.
Example 4. Let us consider the following PDS, obtained as an extension of the DS in Example 2:
๐ถ={ 0.9 :: response(a,b) (c1 )
0.8 :: init(a) (c2 ) }
The probability of c1 indicates that the constraint response(a,b) is considered very strong therefore, the
more traces satisfy it, the better. The probability of c2 indicates that the fact that a trace starts with the
execution of activity a is rather important, but less than the fact that a is followed by b. For each constraint
there are 2 different atomic choices, and this leads to 4 selections and 4 possible worlds; in turn, 4 different
regular DS are possible, each one corresponding to a world:
Selection DS ๐ (๐ท๐๐ )
๐1 = {(๐1 , 1), (๐2 , 1)} ๐ท๐1 = {response(a,b), init(a)} ๐ (๐ท๐1 ) = 0.9 ร 0.8 = 0.72
๐2 = {(๐1 , 1), (๐2 , 0)} ๐ท๐2 = {response(a,b)} ๐ (๐ท๐2 ) = 0.9 ร 0.2 = 0.18
๐3 = {(๐1 , 0), (๐2 , 1)} ๐ท๐3 = {init(a)} ๐ (๐ท๐3 ) = 0.1 ร 0.8 = 0.08
๐4 = {(๐1 , 0), (๐2 , 0)} ๐ท๐4 = { } ๐ (๐ท๐4 ) = 0.1 ร 0.2 = 0.02
Example 4 allows us to highlight some characteristics of the semantics proposed in this paper. First
of all, we might notice that, thanks to the notion of world, we started from a probabilistic declarative
specification, and ended up with a set of non-probabilistic declarative specifications. Secondly, we
might notice that each different ๐ท๐๐ has its own probability (i.e., the one obtained by the corresponding
selection
โ๏ธ ๐๐ ), and that the set of all the possible selections achieves a probability distribution over DSs,
i.e. ๐ ๐ (๐ท๐๐ ) = 1.
4. Probabilistic Compliance
In this Section we will define the notion of compliance of a trace w.r.t. a Probabilistic Declarative
Process Specification PDS. In doing so, we will heavily rely on the simpler notion of compliance of
a trace vs. a DS as in Definition 4. Note that in turn Def. 4 builds upon Def. 2, that abstracts away
from the formal Declare semantics (๐ฟ๐ ๐ฟ๐ or ALP). As a consequence, our definition of compliance
towards a probabilistic specification is general, and is valid for both ๐ฟ๐ ๐ฟ๐ and ALP. Obviously, in order
to compute the compliance, one semantics should be chosen: we will discuss such a choice and the
implementation in the next Section.
Definition 11 (Compliance of a trace versus a PDS). Given a a Probabilistic Declarative Process Specifica-
tion PDS, let us consider all the possible selections ๐๐ over PDS, and all the possible Declarative Specification
๐ท๐๐ associated with ๐๐ . A trace ๐ก has a probability of compliance w.r.t. a PDS defined as follows:
โ๏ธ
๐๐๐๐(๐ก, ๐ ๐ท๐) = ๐ (๐ท๐๐ ) (2)
๐๐ : ๐ก is compliant with ๐ท๐๐
We might observe that, w.r.t. Def. 4, we move forward from a crisp boolean concept towards a degree
of compliance: this is an expected consequence of introducing probabilities in the specification. Then,
we might notice that the formula above indeed is simply an application of Equation 1 to the process
specification domain. Let us apply the notion of compliance of a trace vs. a PDS by considering the
following example:
Example 5 (continued from Ex. 4). Consider the PDS of Ex. 4 and the trace ๐ก1 = โจa, b, cโฉ: ๐ก1 is compliant
with all 4 ๐ท๐๐ and, as expected, its probability of compliance is:
๐๐๐๐(๐ก1 , ๐ ๐ท๐) = ๐ (๐ท๐1 ) + ๐ (๐ท๐2 ) + ๐ (๐ท๐3 ) + ๐ (๐ท๐4 ) = 0.72 + 0.18 + 0.08 + 0.02 = 1
Let us consider then a trace ๐ก2 = โจc, a, bโฉ and suppose temporarily that c1 and c2 are crisp constraints: ๐ก2
is compliant with c1 since after a there is b; however it is not compliant with c2 since ๐ก2 does not start with
a. By considering again the constraint as probabilistic, out of the four declarative specifications ๐ท๐๐ , ๐ก2 is
compliant with ๐ท๐2 and ๐ท๐4 , i.e. those specifications that do not contain c2 . ๐ก2 probability of compliance
is:
๐๐๐๐(๐ก2 , ๐ ๐ท๐) = ๐ (๐ท๐2 ) + ๐ (๐ท๐4 ) = 0.18 + 0.02 = 0.2
By violating c2 , which was a rather important constraint as indicated by a probability value of 0.8, the
trace has a low degree of compliance vs. the PDS.
Finally, let us consider the trace ๐ก3 = โจc, aโฉ. ๐ก3 is not compliant with c1 nor with c2 , considered
individually, however it is compliant with the empty specification ๐ท๐4 , so its probability of compliance is
not zero but is equal to ๐ (๐ท๐4 ) = 0.02.
Example 5 illustrates the intuition behind the idea, proposed in this work, of interpreting the probabil-
ity of a constraint as its strength or, in other words, how much important it is to satisfy such constraint.
In the aforementioned example, trace ๐ก1 is compliant with both the constraints, hence its degree of
compliance is the maximum possible. Trace ๐ก2 instead is compliant with only one of the two constraints,
hence its degree is lower in relation to the strength/importance we have associated to the violated
constraint. We might finally notice that trace ๐ก3 , even if it does not comply with any constraints, still
achieves a score. This is a direct consequence of the interpretation of the probability of a constraint as
its strength: if the strength ๐๐ is lower than 1, then we are saying that we will admit non-compliant
traces with a degree (1 โ ๐๐ ).
In more formal terms, if all the constraints in a PDS have the attached probabilities ๐๐ < 1, then there
is always a selection ๐ * corresponding to including no constraint in the ๐ท๐ * (the empty specification),
and whose probability is ๐ (๐ * ) > 0. In Example 4, such a special selection is ๐4 . Every possible trace
will be always compliant with ๐ท๐ * , since itโs empty. Similarly, all the constraints annotated with
probability ๐๐ = 1 will appear in all the corresponding non-probabilistic DS, as shown in the following
example:
Example 6. Let us consider the following PDS:
๐ถ={ 0.8 :: response(a,b) (c1 )
init(a) (c2 ) }
The corresponding selections and specifications would be:
Selection DS ๐ (๐ท๐๐ )
๐1 = {(c1 , 1)} ๐ท๐1 = {response(a,b), init(a)} ๐ (๐ท๐1 ) = 0.8
๐2 = {(c1 , 0)} ๐ท๐2 = {init(a)} ๐ (๐ท๐2 ) = 0.2
Example 6 clearly illustrates how our proposed semantics for PDS accommodates for both probabilistic
and non-probabilistic constraints: the latter are treated as mandatory constraints as usual in Process
Mining, and the derived specifications ๐ท๐๐ will always contain them.
5. Implementation and Evaluation
For computing the probabilistic compliance of a trace vs a PDS we leveraged on the implementation
presented in [22]. This implementation supports reasoning on ALP programs featuring "integrity
constraints" similar to those offered by IFF [23], extended with the possibility of annotating them with
a probability value. The semantics of these programs, called IFFProb programs, defines a probability
distribution over IFF programs inspired by the distribution semantics, so the IFFProb implementation
could be directly used for our goals. IFFProb is based on the implementation of the SCIFF proof-procedure.
SCIFF [12] is an extension of the IFF proof procedure that also features constraints (ร la CLP) and
universally quantified abducibles. In [22], the IFF sub-language is extended to the probabilistic case with
a new CHR constraint that represents the current explanation (๐๐ฅ๐๐, ๐ ) meaning that, in the current
derivation branch, the explanation is ๐๐ฅ๐๐ and has probability ๐ . ๐ธ๐ฅ๐๐ is a collection of couples (c๐ , ๐),
holding the constraint c๐ and the Boolean value ๐ indicating whether c1 belongs to ๐๐ฅ๐๐ or not.
In [9] declare constraints were mapped into a rule-based language known as CLIMB (Computational
Logic for the verIfication and Modeling of Business constraints), a specialized subset of the SCIFF
language that is based on abductive semantics. This mapping allows declarative models to be converted
into sets of executable, logic-based rules. These rules are referred to as integrity constraints since they
constrain the courses of interaction to ensure their integrity and compliance with interaction protocols.
Each atomic Declare activity can be expressed in CLIMB as a term and is linked to a single time point,
allowing its execution to be represented as either happened (H), expected (E), or forbidden. For example,
the fact that an atomic activity ๐ has happened at time ๐ can be denoted by ๐ป(exec(๐), ๐ ), while
๐ธ(exec(๐), ๐ ) states that ๐ is expected to occur at time ๐ . We do not consider here forbidden activities.
Integrity constraints are of the form ๐ต๐๐๐ฆ โ ๐ป๐๐๐, where ๐ต๐๐๐ฆ contains (a conjunction of) happened
events, together with constraints on their variables, as well as Prolog predicates; ๐ป๐๐๐ contains (a
disjunction of conjunctions of) positive and negative expectations, together with constraints and Prolog
predicates, applied on their variables and/or on variables contained in the ๐ต๐๐๐ฆ.
We created a Declare process model for elective colorectal surgery based on the ERASยฎ (Enhanced
Recovery After Surgery) Society guidelines for perioperative care [24], as shown in Figure 2. The
model is a PDS written in the CLIMB language, where the protocol activities are subject to both crisp
and probabilistic constraints: the former represent strongly recommended practices according to the
guidelines, reflecting critical, evidence-supported activities that must be adhered to rigorously, while the
latter represent weakly recommended practices, whose associated probability states the importance to
apply them in the healthcare flow. Weakly recommended practices may have some degree of flexibility
in their implementation due to individual patient needs, local variations in resources and demographics,
advancements in medical research, institutional policies, and cultural considerations. The model includes
21 constraints capturing essential perioperative events, from patient admission to post-surgery recovery.
Of these, 14 constraints were identified as crisp (๐๐ = 1) and 7 as probabilistic. An excerpt of the PDS is:
true โ ๐ธ(exec(program_admission), 0). (๐1 )
๐ป(exec(program_admission), ๐1 ) โ ๐ธ(exec(counseling), ๐2 ) โง ๐2 > ๐1 . (๐2 )
๐ป(exec(start_surgery), ๐2 ) โ ๐ธ(exec(counseling), ๐1 ) โง ๐1 < ๐2 . (๐3 )
0.3 :: ๐ป(exec(start_surgery), ๐2 ) โ ๐ธ(exec(preanesthesia), ๐1 ) โง ๐1 < ๐2 . (๐4 )
0.4 :: ๐ป(exec(start_surgery), ๐2 ) โ ๐ธ(exec(fasting), ๐1 ) โง ๐1 < ๐2 . (๐5 )
Here, the integrity constraint ๐1 represents the init constraint. It specifies that the process must
always start with the event program admission of the patient, occurring at time 0. Obviously, it is a
mandatory constraint. Constraint ๐2 represents the response constraint, indicating that whenever the
event program admission happens, the pre-operative patient counseling and education must eventually
follow at a time T2 later than T1. Itโs strongly recommended to begin patient counseling after admission
into the program and prior to surgical procedures, thus constraints ๐2 and ๐3 are treated as crisp. Instead,
๐4 and ๐5 are modeled as probabilistic precedence constraints since, in the guidelines, preanesthesia
and fasting before surgery could sometimes be skipped. The relatively low probability assigned to
them derives from the consensus around those specific perioperative practices, suggesting they are
generally not enforced for optimal postoperative outcomes. Each event trace was then adapted to the
format required by the algorithm, transforming each trace into an interpretation. Every fact has two
Figure 2: declare model of the ERASยฎ protocol for colorectal surgery across the pre-operative (PRE-OP),
intra-operative (INTRA-OP), and post-operative (POST-OP) phases. Strong recommendations are shown in black,
while weak ones in gray.
arguments: the first one is a ground term that records the event name, and the second one is an integer
that indicates the timestamp. An example of an interpretation is the following:
โ๐๐(๐๐ฅ๐๐(๐๐๐๐๐๐๐_๐๐๐๐๐ ๐ ๐๐๐), 0).
โ๐๐(๐๐ฅ๐๐(๐๐๐ข๐๐ ๐๐๐๐๐), 5).
โ๐๐(๐๐ฅ๐๐(๐ ๐๐ ๐ก๐๐๐), 80).
To perform our experiments we wrote one synthetic trace composed of 21 events, one for each
activity of the protocol. The process trace satisfied all the model constraints.
We provide two preliminary scalability tests in order to show how both crisp and probabilistic
constraints influence the execution time in computing the probability of compliance of that trace.
Experiments were carried out on a Linux machine with Intelยฎ Xeonยฎ E5-2630v3 running at 2.40 GHz
with 20 GB of RAM and a time limit of 8 hours. In the first test, the number of crisp constraints was
kept fixed respectively to 3, 6, 9, and 14 and the number of probabilistic constraints was increased from
1 to 7 at steps of 1. In the second test, the number of probabilistic constraints was kept fixed at 2, 4, and
7 and the number of crisp constraints was increased from 1 to 14 at steps of 1.
ยท104 ยท104
1 1
3 Crisp Constr. 2 Prob. Constr.
Execution Time (s)
Execution Time (s)
0.8 6 Crisp Constr. 0.8 4 Prob. Constr.
9 Crisp Constr. 7 Prob Constr.
0.6 14 Crisp Constr. 0.6
0.4 0.4
0.2 0.2
0 0
0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Number of Probabilistic Constraints Number of Crisp Constraints
(a) Execution time as the number of probabilistic (b) Execution time as the number of crisp con-
constraints varies, keeping the number of crisp straints varies, keeping the number of prob-
constraints fixed. abilistic constraints fixed.
Figure 3: Scalability analysis of the computation of the probability of compliance of a trace vs. a PDS with
varying numbers of crisp and probabilistic constraints.
Figure 3 illustrates the results, showing an exponential trend in execution times as the number
of either crisp or probabilistic constraints increases. The impact on the time is higher when using
probabilistic constraints: we obtain an exponential trend with 7 probabilistic constraints compared to
14 crisp ones.
6. Conclusions and Future Work
In this paper, we presented a new semantics for Declare process model specifications which allows one
to specify probabilistic constraints representing their strength/importance in a specific process domain.
In this way, we can model domains where some constraints are stronger (or weaker) than others. Such
models are called Probabilistic Declarative Process Specifications. The underlying semantics is inspired
by the distribution semantics from Probabilistic Logic Programming, and abstracts away from the
formal Declare semantics (LTL๐ or ALP), aiming at computing the probability of compliance of a trace
versus the model. The computation of the compliance relies on an existing algorithm. Preliminary
tests show that the time taken for computing the probability has an exponential trend by increasing
the number of both crisp and probabilistic constraints. Future work includes: extending experimental
evaluation, defining the compliance of a set of traces (log) vs. a PDS; extending the new semantics
to manage uncertainty at the level of events, traces or the log itself; studying the profiles of energy
consumption when computing the probability of compliance.
7. Acknowledgments
Research funded by the Italian Ministerial grant PRIN 2022 โProbabilistic Declarative Process Mining
(PRODE)โ, n. 20224C9HXA - CUP F53D23004240006, funded by European Union โ Next Generation
EU. Research partly funded by the Italian Ministry of University and Research through PNRR - M4C2 -
Investimento 1.3 (Decreto Direttoriale MUR n. 341 del 15/03/2022), Partenariato Esteso PE00000013
- "FAIR - Future Artificial Intelligence Research" - Spoke 8 "Pervasive AI" - CUP J33C22002830006,
funded by the European Union under the NextGeneration EU programme". This work was realized by
Daniela Loreti with a research contract co-financed by the European Union (PON Ricerca e Innovazione
2014-2020 art. 24, comma 3, lett. a), della Legge 30/12/2010, n. 240 e s.m.i. e del D.M. 10/08/2021 n. 1062).
References
[1] M. Pesic, H. Schonenberg, W. M. van der Aalst, Declare: Full support for loosely-structured
processes, in: 11th IEEE International Enterprise Distributed Object Computing Conference
(EDOC 2007), 2007, pp. 287โ287. doi:10.1109/EDOC.2007.14.
[2] M. Pesic, Constraint-based workflow management systems : shifting control to users, Phd thesis 1
(research tu/e / graduation tu/e), Industrial Engineering and Innovation Sciences, 2008. doi:10.
6100/IR638413, proefschrift.
[3] T. T. Hildebrandt, R. R. Mukkamala, Declarative event-based workflow as distributed dy-
namic condition response graphs, in: K. Honda, A. Mycroft (Eds.), Proceedings Third Work-
shop on Programming Language Approaches to Concurrency and communication-cEntric Soft-
ware, PLACES 2010, Paphos, Cyprus, 21st March 2010, volume 69 of EPTCS, 2010, pp. 59โ73.
doi:10.4204/EPTCS.69.5.
[4] A. Alman, F. M. Maggi, M. Montali, R. Peรฑaloza, Probabilistic declarative process mining, Inf. Syst.
109 (2022) 102033. doi:10.1016/J.IS.2022.102033.
[5] T. Sato, A statistical learning method for logic programs with distribution semantics, in: L. Ster-
ling (Ed.), Logic Programming, Proceedings of the Twelfth International Conference on Logic
Programming, Tokyo, Japan, June 13-16, 1995, MIT Press, 1995, pp. 715โ729.
[6] M. Montali, Specification and Verification of Declarative Open Interaction Models - A Logic-Based
Approach, volume 56 of LNBIP, Springer, 2010. doi:10.1007/978-3-642-14538-4.
[7] D. Azzolini, E. Bellodi, S. Ferilli, F. Riguzzi, R. Zese, Abduction with probabilistic logic programming
under the distribution semantics, Int. J. Approx. Reason. 142 (2022) 41โ63. doi:10.1016/J.IJAR.
2021.11.003.
[8] van der Aalst, et al., Process mining manifesto, in: F. Daniel, K. Barkaoui, S. Dustdar (Eds.), Business
Process Management Workshops - BPM 2011 International Workshops, Clermont-Ferrand, France,
August 29, 2011, Revised Selected Papers, Part I, volume 99 of LNBIP, Springer, 2011, pp. 169โ194.
doi:10.1007/978-3-642-28108-2\_19.
[9] M. Montali, Specification and Verification of Declarative Open Interaction Models - A Logic-based
framework, Ph.D. thesis, alma, 2009. URL: http://amsdottorato.unibo.it/1829/.
[10] G. D. Giacomo, M. Y. Vardi, Linear temporal logic and linear dynamic logic on finite traces, in:
F. Rossi (Ed.), IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial
Intelligence, Beijing, China, August 3-9, 2013, IJCAI/AAAI, 2013, pp. 854โ860. URL: http://www.
aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6997.
[11] C. D. Ciccio, M. Montali, Declarative process specifications: Reasoning, discovery, monitoring,
in: W. M. P. van der Aalst, J. Carmona (Eds.), Process Mining Handbook, volume 448 of LNBIP,
Springer, 2022, pp. 108โ152. doi:10.1007/978-3-031-08848-3\_4.
[12] M. Alberti, F. Chesani, M. Gavanelli, E. Lamma, P. Mello, P. Torroni, Verifiable agent interaction
in abductive logic programming: The SCIFF framework, ACM Trans. Comput. Log. 9 (2008)
29:1โ29:43. doi:10.1145/1380572.1380578.
[13] E. Dantsin, Probabilistic logic programs and their semantics, in: Russian Conference on Logic
Programming, volume 592 of LNCS, Springer, 1991, pp. 152โ164.
[14] D. Poole, Logic programming, abduction and probability - a top-down anytime algorithm for
estimating prior and posterior probabilities, New Generation Computing 11 (1993) 377โ400.
[15] D. Poole, The Independent Choice Logic for modelling multiple agents under uncertainty, Artificial
Intelligence 94 (1997) 7โ56.
[16] N. Fuhr, Probabilistic datalog: Implementing logical information retrieval for advanced applications,
Journal of the American Society for Information Science 51 (2000) 95โ110.
[17] J. Vennekens, S. Verbaeten, M. Bruynooghe, Logic programs with annotated disjunctions, in:
B. Demoen, V. Lifschitz (Eds.), 20th International Conference on Logic Programming (ICLP 2004),
volume 3131 of LNCS, Springer, 2004, pp. 431โ445. doi:10.1007/978-3-540-27775-0_30.
[18] L. De Raedt, A. Kimmig, H. Toivonen, ProbLog: A probabilistic Prolog and its application in link
discovery, in: M. M. Veloso (Ed.), 20th International Joint Conference on Artificial Intelligence
(IJCAI 2007), volume 7, AAAI Press, 2007, pp. 2462โ2467.
[19] J. Vennekens, M. Denecker, M. Bruynooghe, CP-logic: A language of causal probabilistic events
and its relation to logic programming, Theory and Practice of Logic Programming 9 (2009) 245โ308.
doi:10.1017/S1471068409003767.
[20] F. Riguzzi, T. Swift, Well-definedness and efficient inference for probabilistic logic programming
under the distribution semantics, Theory and Practice of Logic Programming 13 (2013) 279โ302.
doi:10.1017/S1471068411000664.
[21] E. Bellodi, The distribution semantics in probabilistic logic programming and probabilistic descrip-
tion logics: a survey, Intelligenza Artificiale 17 (2023) 143 โ 156. doi:10.3233/IA-221072.
[22] E. Bellodi, M. Gavanelli, R. Zese, E. Lamma, F. Riguzzi, Nonground abductive logic programming
with probabilistic integrity constraints, Theory and Practice of Logic Programming 21 (2021)
557โ574. doi:10.1017/S1471068421000417.
[23] T. H. Fung, R. A. Kowalski, The IFF proof procedure for abductive logic programming, Journal of
Logic Programming 33 (1997) 151โ165. doi:10.1016/S0743-1066(97)00026-5.
[24] U. O. Gustafsson, et al., Guidelines for perioperative care in elective colorectal surgery: Enhanced
recovery after surgery (erasยฎ) society recommendations: 2018, World Journal of Surgery 43 (2019)
659โ695. doi:10.1007/s00268-018-4844-y.