Process alignment aims at relating an actual execution, captured as a log trace, to a process run of a model. Besides considering the control flow aspect, in this paper we propose to leverage on contextual information expressed in terms of responsibilities. This allows us to select, among the possible alignments, those where the fewest number of responsibilities is neglected. Additionally, we leverage on responsibilities to evaluate the deviations occurring between a process run and the log trace: deviations which are justified by a responsibility are considered correct behaviours rather than errors.
When it comes to process model executions, it might be the case that the actual executions
do not perfectly match with a run foreseen by the model. Conformance checking in
process mining aims at finding the process run which is closest to an execution [
In performing this task, most of the approaches consider control flow information only,
and attribute the same cost to the deviations. As a result, the optimal alignment is
the one minimizing the number of deviations. More recent works consider contextual
information to evaluate mismatches [
In this paper we focus on responsibilities, through which organizations are capable of
incorporating regulations, laws, policies, objectives and such like. Responsibilities, which
can be on simple tasks as well as complex tasks (i.e., subprocesses), are an integral part of
business organizations. Several models exists to define them, such as Business Motivation
Models (BMM) [
In this work, we propose to complement such a model with responsibilities ans we
show how this would allow us to determine when a mismatch in an alignment is not
necessarily a misbehavior, but an acceptable alternative. The paper is organized as
follows. In Section 2 we propose a formalism for responsibility representation which
supports the specification of declarative orderings among activities. In Section 3 we
provide the formalization of process model extended with responsibilities. An alignment
strategy that accounts for mismatches with the process model as well as responsibilities
that are either satisfied or neglected is presented in Section 4. An extended version of
the paper can be found in [
The term responsibility is associated with multiple shades of meaning [
Our proposal is to leverage on responsibilities, and the fact that they can be neglected,
as a preference criterion on alignments. In fact, in the real execution of a process, an
actor can either meet or neglect her responsibilities. Our goal is to use these events as
contextual information for trace alignment, relying on the assumption that role players
will act so to be aligned as much as possible with their responsibilities. Let us consider
an example inspired by [
Example (Alignments and Responsibilities). In a Fine Management Process, a fine is ifrst sent (Send-Fine) to the ofender, then the ofender can either appeal to the judge (Appeal-Judge), or pay (Pay), in which case a receipt is produced by an employee (Send-Receipt). Only two model runs are possible: E1 = ⟨Send-Fine, Appeal-Judge⟩ and E2 = ⟨Send-Fine, Pay, Send-Receipt⟩. Let us consider the observed execution trace: = ⟨ Send-Fine⟩. The possible alignments with trace T are the following, where ≫ represents mismatches (i.e., moves where either the log trace or the model moves one step).
A1 = SSeenndd--FFiinnee Appea≫l-Judge A2 = SSeenndd--FFiinnee P≫ay Send-≫Receipt Classical approaches would conclude that the model execution E1 is closer to the trace because in A1 there is one mismatch, while in A2 there are two. Let us now assume that the model is complemented with an explicit representation of responsibilities, and that the employee is (always) responsible for producing a receipt only after the payment of the ifne, and only in case it occurs. Assessing the two alignments against such a responsibility allows us to observe that the lack of Send-Receipt in A2 is actually correct, justified by the fact that the payment did not occur. Therefore, it should not be considered a mismatch, and the two alignments can be considered as equivalent in terms of number of mismatches.
Responsibilities provide, in a declarative manner, the expected context of an activity, which is precious for interpreting a logged trace in a way that goes beyond the syntactic distance between strings. Accordingly, we define the cost of an alignment as depending both on the responsibilities that are neglected, and the found mismatches as follows: a neglected responsibility amounts to a cost accumulated by the alignment; a mismatch justified by responsibilities (as for Send-Receipt in our example) does not contribute to the cost of an alignment, while other mismatches are considered as misbehavior and contribute to the cost.
To express context conditions and duties in a responsibility relation we rely on
precedence logic defined in [
Precedence Logic. Given a responsibility R(x,u,v), we denote the conditions u and v as
precedence logic expressions, defined over the set of symbols Σ ∪ {0, ⊤}; here, Σ is a set of
activity symbols, 0 means false, and ⊤ means true. Precedence logic is an event-based
linear temporal logic, obtained from propositional logic augmented with the temporal
operator (⋅) before. Such an operator is used to express minimal ordering requirements
between events. For instance, ⋅ expresses the requirement for event to occur some
time before the occurrence of event (need not be strictly before). Besides the before
operator, the logic includes the ∨ (choice) and the ∧ (interleaving) operators (capturing
that two conditions need to be satisfied but there is no temporal requirements between
them). Given a workflow expressed in precedence logic, the residual of against an
event , denoted as / , defines the evolution of after the occurrence of event . The
residual operator is defined by rules (a – h) below, defined in [
The residual / is defined as:
(a)
(c)
(e)
(g)
0/ ≐ 0
( 1 ∧ 2)/ ≐ (( 1/) ∧ ( 2/))
( ⋅ 1)/ ≐ 1 if ∉ Γ 1
( ′ ⋅ 1)/ ≐ 0 if ∈ Γ 1
(b)
(d)
(f)
(h)
⊤/ ≐ ⊤
( 1 ∨ 2)/ ≐ (( 1/) ∨ ( 2/))
( 1/) ≐ 1 if ∉ Γ 1
( ⋅̄ 1)/ ≐ 0
Since 0 amounts to false, and ⊤ to true, the residual operator can be used for assessing
whether a workflow expression is satisfied by a given sequence of events = ⟨ 1, … , ⟩
in Σ. Specifically, we denote as / the expression (((/ 1)/ 2) …)/ . When / leads
to ⊤, is a possible execution run of . When / leads to 0 represents a trace not
compliant with . According to [
Intuitively, when the responsibility is active there is an expectation on to bring about v since the context condition u holds. When the responsibility is discharged, instead, the context condition does not hold (and cannot hold along the given ), and hence no expectation about v can be made. The responsibility is satisfied along when both u and v progress to ⊤. Finally, a responsibility is neglected either when, at any execution step, the context condition u holds and the duty v does not, or when, at the end of the trace, u holds and v has not progressed to ⊤, that is, the expectation created with u has not been met.
Example (Responsibilities). Let us consider a set Σ of activity symbols {p, sf, sr} standing respectively for Pay, Send-Fine and Send-Receipt. Consider a responsibility relation R(x,⊤, p ⋅ sr) expressing that the receipt has to be sent only after the payment. Let us consider the execution ⟨sf, sr⟩ and apply the residual with respect to it. First, since sf ∉ Γp⋅sr, rule (e) applies: p ⋅ sr/sf = p ⋅ sr. Then, rule (g) applies to p ⋅ sr/sr since sr ∈ Γsr, bringing the responsibility to be neglected.
In our approach a process model accounts both for the control flow, and for responsibility relations assigned to roles taking part to the process. We distinguish the two parts, defining a Process Net, specified as a labeled Petri Net in Definition 3.1; and complementing it with a set of responsibilities annotating it.
We define a process net as an extension of the process model given in [
Definition 3.1 (Process Net). A Process Net is a Labeled Petri Net defined as a tuple N = ⟨ , , , 0, , Σ, , , ⟩ , where is the set of places, is the set of transitions (with ∩ = ∅ ), is the flow relation ⊆ ( × ) ∪ ( × ) , 0 is the initial marking, is the ifnal marking, Σ is the set of activity symbols, ∶ → Σ ∪ { } labels every transition by an activity or as silent, is the set of roles, and ∶ Σ → assigns a role to every activity in Σ.
A process net N sets the scope of responsibility relations, since it specifies both the roles and the activities Σ over which a responsibility is defined. Responsibilities are defined at design time, and relying on precedence logic allows us to specify that a responsibility be active when a precise execution path occurs. For instance, given a process net N and the activities a, b, c, d ∈ Σ, and a role ∈ , to specify that an actor playing role is responsible for activity d only if activities a, b, and c (in the order but possibly interleaved with other events) occur, one can specify the responsibility relation R( , a ⋅ b ⋅ c, d). Instead, to specify that the responsibility is activated when the three activities occur in any order one can use the relation R( , a ∧ b ∧ c, d).
We expect that each responsibility is consistently defined with the process model it refers to. In other terms, both the context and the duty conditions are assumed to be (sub)workflows that can be generated by at least one model run. Therefore, there is always at least a way to satisfy a responsibility.
Activities are part of the context in which responsibilities hold. For instance, by accepting an order, an employee becomes responsible for a number of duties. We “attach” responsibilities to activities, meaning intuitively that a responsibility gets relevant when its corresponding activity is performed. For instance, R( , a ⋅ b ⋅ c, d) can be attached to e, to express that it gets relevant when e is executed. The context condition captures that, if e can be reached from more than one path, the responsibility is activated only by the path where a ⋅ b ⋅ c holds. Definition 3.2 formally define the responsibility labelling of a process net.
Definition 3.2 (Responsibility Labelling). Let N be a process net, and let and Σ be, respectively, the set of roles and activity symbols in N. A responsibility labeling over N is a function R ∶ Σ → {R1, … , R } where each R is a responsibility relation R( , u , v ), such that: ∈ and u and v are precedence logic expressions over Σ ∪ {0, ⊤}.
A process model is then defined as a pair M = ⟨N, R⟩ where N is a process net as in Definition 3.1, and R is a responsibility labelling as in Definition 3.2.
An alignment compares a process execution against an execution trace (i.e., a log trace).
Generally, the objective is to find, among the possible ones, an alignment which is optimal
w.r.t. a criterion of preference. Intuitively, an alignment proceeds step-by-step on the
model and on the log: at each step, if the activity in the model and the one in the log
match each other, a synchronous move is made, and both model and log advance one
step. Otherwise, either the model moves and the log does not, or the other way around,
the log moves and the model does not. Usually, to find an optimal matching, a cost
function associated with mismatches (i.e., asynchronous moves) is defined. So, an optimal
alignment is the one minimizing the cumulative cost of the mismatches. The classical
approach is to minimize the number of asynchronous moves [
In our approach, an optimal alignment is determined taking into account both the
alignment between a log trace and a model run, and the involved responsibilities. We refer
to the former as flow alignment and to the latter as responsibility alignment. Definition 4.1
formalizes the notion of flow alignment. The symbol ≫ represents a no-move, and is used
for marking asynchronous moves. More in general, given a process model M = ⟨N, R⟩, we
use the term model run for the sequence of activity symbols in Σ produced by a full run
of the process net N, where a Petri Net full run is a sequence of firings from the initial
marking to the final one [
Definition 4.1 (Flow Alignment). Let = ⟨ 1, … , ⟩ be a log trace in Σ∗, and N = ⟨ , , , 0, , Σ, , , ⟩ a process net, an alignment of with the process net N is a finite sequence = ⟨( 1, 1′), … , ( ′, ′ )⟩ of moves such that:
′ • each move is either: a synchronous move ( , ) ∈ Σ × with = () , a log move (, ≫ ), or a model move (≫, ), • dropping the ≫ symbols from the left projection ( 1′, … , ′) of , yields , • dropping the ≫ symbols from the right projection ( 1′, … , ′ ) of , yields a full run of N.
To consider the responsibilities in evaluating the optimal alignment, our approach is to collect all the responsibilities attached to the activities of a model run (i.e., the responsibilities that should be satisfied along a possible, expected execution), and assess them against a log trace (to check if indeed they are satisfied). The cost of an alignment, thus, takes also into account the cost of neglected responsibilities. Moreover, the responsibilities collected along a model run give us a context for assessing whether a model move (i.e., a “skip” on the log side) actually represents an execution error, or a proper behavior.
Given a flow alignment , its responsibility set is the set of responsibilities attached to the activities in the model run given by the right projection of (i.e., the model-side projection). In general, a responsibility set can be computed for any non-empty prefix of by considering the alignment up to a given step .
Definition 4.2 (Responsibility Set). Let = ⟨( 1′, 1′), … , ( ′, ′ )⟩ be a flow alignment between a process model M = ⟨N, R⟩ and a log trace ∈ Σ ∗, the responsibility set R, for the alignment at step (1 ≤ ≤ ) is defined as R, = ∪=1 R(( ′)).
It holds R(≫) = ∅. As a shortcut, we denote as R the set R, , that is the set of responsibilities computed considering all the steps in the alignment . The responsibilities in R are actually satisfied or neglected depending on the activities that are included in the log trace (i.e., log-side projection of ). Thus, we first extend the notion of residuation of the precedence logic to responsibility relations, and then to a responsibility set.
Given a responsibility set R = {R1, … , R } with R = R(x ,u ,v ), let ′ = ⟨ 1′, … , ′⟩ be the log-side projection of . Then, the notation R / ′ is a shorthand for R(x ,u / ′,v / ′) and R / ′ is a shorthand for {R1/ ′, … , R / ′}. Additionally, the residuation of any expression u with ≫ has no efect on the expression, namely u/ ≫= u.
It is worth noting that the rewriting rules of the precedence logic guarantee a consistent
evaluation of the responsibilities against a log trace. In fact, whenever a responsibility
progresses from the active state to either satisfied, neglected, or discharged, such a second
state is final: the state of the responsibility can no longer evolve along the same trace.
That is, further events along the trace cannot satisfy a neglected responsibility nor vice
versa. At the same time, a responsibility activated along a log trace must necessarily
evolve to either satisfied or neglected by the end of the same trace (see [
In general, several alignments of a log trace w.r.t. a model exist. To compare them and determine the optimal one we define a cost function that considers both the cost of the mismatches between the model run and the log trace, which we call Flow Alignment Cost CN,, and the cost for the neglected responsibilities, which we call Responsibility Alignment Cost CR,.
The cost CR, corresponds to the number of responsibilities that are neglected in a lfow alignment . To compute them, first the responsibility set R for is determined (Definition 4.2). Then, R is residuated with respect to the projection log-side of . Neglected responsibilities are then those that are active, but not satisfied at the end of the trace.
Example (Responsibility Alignment Cost). Let us consider the fine process scenario, and assume that the employee is responsible for archiving (ar) any sent fine ( sf) after 60 days. Now, in both alignments A1 and A2 (see Section 2), the responsibility is activated but is not satisfied by the end of both alignments. Thus is marked as neglected and brings a cost in both alignments.
The flow cost CN,, calculates the cost of every mismatch (i.e., either model or log moves) included within a given alignment. Notably, this calculation takes into account responsibilities as a sort of context. By using them, in fact, we are able to identify some model moves as correct, and not as mismatches. Intuitively, to compute CN,, each alignment step ( ′, ′) of a flow alignment is considered. A step is a mismatch, and hence has to be counted as a cost, when it is either a log move or it is a model move which is not justified by any responsibility. A model move is justified by a responsibility if executing that activity in the log (instead of a ≫) would have lead an active responsibility to progress to neglected. This means that skipping the activity is consistent with at least one responsibility, and hence does not represent a misbehavior.
Example (Flow Alignment Cost). Let us consider again alignment A2 in Section 2, and let us assume that R(x,⊤, p ⋅ sr) is associated with activity Pay to indicate that, if the expected execution is the one that goes through Pay rather than Appeal-Judge, then the receipt has to be sent only after and only in case of a payment. Concerning the Flow Alignment Cost, albeit A2 has two asynchronous model moves, only the first one actually contributes to the flow cost. The log skip on Send-Receipt ( sr), instead, is justified since the occurrence of sr in the log would lead to the violation of R(x,⊤, p ⋅ sr).
The total cost of an alignment is computed as the weighted sum of the flow and the responsibility costs: C = ⋅ CN, + ⋅ CR,
Coeficients and are domain-dependent weights that can be tuned for penalizing more either neglected responsibilities or asynchronous moves. An alignment between a model M and a log trace is optimal if C is minimal.
We presented a novel methodology of process alignment which takes into account
responsibilities during the search for optimal alignments. Several proposals in the literature
focus on extending process alignment considering other perspectives besides the control
lfow [
An explicit representation of responsibilities opens several future directions. First, each
alignment found by our algorithm is associated with a set of met and unmet responsibilities.
These two sets provide a sort of justification why a specific alignment has been selected
as optimal. Moreover, by considering the set of unmet responsibilities one could reason
about possible ineficiencies and flaws, enabling a responsibility-driven procedure for
re-engineering a process. In addition, role responsibilities designate the actors playing a
specific role as “in charge” of some job, and hence capable of providing accounts about
its accomplishment or failure. As future work, our responsibility framework can be
complemented with accountability relationships [