=Paper=
{{Paper
|id=None
|storemode=property
|title=Incremental Process Mining
|pdfUrl=https://ceur-ws.org/Vol-827/14_MarcSole_article.pdf
|volume=Vol-827
|dblpUrl=https://dblp.org/rec/conf/acsd/SoleC10
}}
==Incremental Process Mining==
https://ceur-ws.org/Vol-827/14_MarcSole_article.pdf
Incremental Process Mining
Marc Solé1 and Josep Carmona2
1
Computer Architecture Department, UPC msole@ac.upc.edu
2
Software Department, UPC jcarmona@lsi.upc.edu
Abstract. The problem of synthesis of Petri nets from transition sys-
tems or languages has many applications, ranging from CAD for VLSI
to medical applications, among others. The most common algorithms to
accomplish this task are based on the theory of regions. However, one of
the problems of such algorithms is its space requirements: for real-life or
industrial instances, some of the region-based algorithms cannot handle
in memory the internal representation of the input or the exploration
lattice required. In this paper, the incremental derivation of a basis of
regions and the later partitioned basis exploration is presented, which
allows the splitting of large inputs.
1 Introduction
The introduction of the theory of regions [1] in the early nineties enabled a
new area of research that strives for transforming language or state-based repre-
sentations into event-based ones. This transformation, known as synthesis, was
initially devoted to derive a Petri net whose reachability graph was bisimilar or
isomorphic to the input transition system. A variant of this problem, known as
mining, has weaker requirements: the language of the derived Petri net must be
a superset (maybe proper) of the language of the input transition system [2].
The theory of this paper provides algorithms for mining.
Many research has been carried out since the introduction of regions, specially
of theoretical nature, which has brought a better understanding of the theory [3–
6], and has provided meaningful extensions to make it more general [7–10].
As a consequence of the aforementioned theoretical work, tools based on
the theory of regions started to be available by the end of the nineties [11, 12]
and still new ones are developed nowadays [9, 10]. These tools are the outcome
of bridging the gap between the theory and practice, and many of them are
used extensively in the academic domain, whereas few are used in industry. The
reasons for the limited success of these tools in industry might be:
1. The algorithms involved are complex, i.e. in general polynomial with the size
of the input [3], that might be prohibitive for large inputs, and the use of
efficient data structures like BDDs or heuristics only alleviates the problem.
2. No high-level techniques are provided to cope with the inherent complexity
of the problem.
Recent Advances in Petri Nets and Concurrency, S. Donatelli, J. Kleijn, R.J. Machado, J.M. Fernandes
(eds.), CEUR Workshop Proceedings, ISSN 1613-0073, Jan/2012, pp. 175–190.
176 Petri Nets & Concurrency Solé and Carmona
2
In [15] In [6, 14]
log L1 TS A1 Basis B1 Sect. 3
TS A2 Basis B2 S S Sect. 4
Basis i Bi PN N
.. .. ..
. RG(Nn ) . .
PN Nn TS An Basis Bn
(a)
TS A1 Basis B1
TS A2 Basis B2 S S
TS A Basis i Bi PN N
.. ..
. .
TS An Basis Bn
(b)
Fig. 1. Incremental Process Mining.
In this work we provide the theoretical basis for deriving high-level strate-
gies that may allow to handle large specifications. More concretely, as space
requirements are typically the bottleneck for some of the tools listed above, in
this paper we present an incremental technique that allows splitting the input
into several smaller parts. Moreover, we show how the theory of regions can be
extended algorithmically to combine the regions of each part in order to derive
the regions of the whole input.
The theory presented will be oriented for the problem of mining: given
a set of objects describing behaviors (like a Petri net, a transition systems
or an event
Sn log) O1 , O2 , . . . , On , we want to obtain a Petri net N such that
L(N ) ⊇ i=1 L(Oi ). The traditional way to solve this problem is to generate
a transition system Ai for each Oi , join all these Ai to create a single transi-
tion system, and then apply a synthesis technique to derive a Petri net from a
transition system [12, 13].
In this paper we explore a different approach. Instead of working with a
monolithic transition system, we use the fact that a transition system can be
represented by a basis of regions, such that any other region is a linear combina-
tion of the regions in the basis (a recent publication shows an efficient technique
to accomplish this task [14]). Then, bases can be combined to obtain a region
basis for the whole system, from which we can derive the Petri net N .
The general picture of the approach of this paper is outlined on Fig. 1(a).
Some arcs are labeled with an indication of the section or the reference where the
conversion/operation is explained. Basically the first step is to convert inputs
that are not transition systems into a transition system, and then compute a
region basis from which a PN can be generated. Another possible application
is also shown in Fig. 1(b), where a large TS is split into smaller subsystems of
manageable size, with the only restriction that all the subsystems must include
the initial state and be connected.
Incremental process mining Petri Nets & Concurrency – 177
3
1.1 Related work
In [16] an incremental approach was suggested based on the observation that
any region of the union of two transition systems can be expressed as the union
of regions of those systems. As in the approach presented in this paper, the
approach in [16] trades space for time, since it must first compute all the re-
gions and then obtain the minimal ones, a slower process than finding directly
the minimal regions if the whole transition system fits into memory. The main
drawback of this method is that the complete set of regions of each component
transition system must be stored (either in memory or disk) in order to compute
the set of regions of the union. In this work we propose a faster methodology
based on the fact that the complete set of regions can be succintly represented
by a basis of regions.
1.2 Organization
We start by giving the necessary background in Sect. 2. The process of combining
a set of bases to produce a unique basis for the whole system is explained in
Sect. 3. A description of the generation of a PN from a region basis is given in
Sect. 4 and, finally, Sect. 5 concludes this paper.
2 Background
2.1 Finite Transition Systems and Petri Nets
Definition 1 (Transition system). A transition system (TS) is a tuple hS, Σ, T, s0 i,
where S is a set of states, Σ is an alphabet of actions, T ⊆ S × Σ × S is a set
of (labelled) transitions, and s0 ∈ S is the initial state.
e
We use s −→s0 as a shortcut for (s, e, s0 ) ∈ T , and we denote its transitive
∗ ∗
closure as −→. A state s0 is said to be reachable from state s if s −→s0 . We
σ
extend the notation to transition sequences, i.e., s1 −→sn+1 if σ = e1 . . . en and
(si , ei , si+1 ) ∈ T . We denote #(σ, e) the number of times that event e occurs in
σ. Let A = hS, Σ, T, s0 i be a TS. We consider connected TSs that satisfy the
following axioms: i) S and Σ are finite sets, ii) every event has an occurrence
and iii) every state is reachable from the initial state. The language of a TS A,
L(A), is the set of transition sequences feasible from the initial state.
For two TSs A1 and A2 , when L(A1 ) ⊆ L(A2 ), we will say that A2 is an
over-approximation of A1 .
Definition 2 (Union of TSs). Given two TSs A1 = hS1 , Σ1 , T1 , s0 i and A1 =
hS2 , Σ2 , T2 , s0 i, the union of A1 and A2 is the TS A1 ∪ A2 = hS1 ∪ S2 , Σ1 ∪
Σ2 , T1 ∪ T2 , s0 i.
Clearly, the TS A1 ∪ A2 is an over-approximation of the TSs A1 and A2 , i.e.
L(A1 ) ∪ L(A2 ) ⊆ L(A1 ∪ A2 ).
178 Petri Nets & Concurrency Solé and Carmona
4
Definition 3 (Petri net [17]). A Petri net (PN) is a tuple (P, T, W, M0 ) where
the sets P and T represent disjoint finite sets of places and transitions, respec-
tively, and W : (P × T ) ∪ (T × P ) → N is the weighted flow relation. The initial
marking M0 ∈ NP defines the initial state of the system.
A transition t ∈ T is enabled in a marking M if ∀p ∈ P : M (p) ≥ W (p, t).
Firing an enabled transition t in a marking M leads to the marking M 0 defined by
t
M 0 (p) = M (p) − W (p, t) + W (t, p), for p ∈ P , and is denoted by M → M 0 . The
set of all markings reachable from the initial marking M0 is called its Reachability
Set. The Reachability Graph of N , denoted RG(N ), is a transition system in
which the set of states is the Reachability Set, the events are the transitions of
t
the net and a transition (M1 , t, M2 ) exists if and only if M1 → M2 . We use L(N )
as a shortcut for L(RG(N )).
2.2 Generalized Regions
The theory of regions [1, 5] provides a way to derive a Petri net from a transition
system. Intuitively, a region corresponds to a place in the derived Petri net. In
the initial definition, a region was defined as a subset of states of the transition
system satisfying a homogeneous relation with respect to the set of events. Later
extensions [7, 18, 10] generalize this definition to multisets, which is the notion
used in this paper.
Definition 4 (Multiset, k-bounded Multiset, Subset). Given a set S, a
multiset r of S is a mapping r : S → Z. The number r(s) is called the multiplicity
of s in r. Multiset r is k-bounded if all its multiplicities are less or equal than k.
Multiset r1 is a subset of r2 (r1 ⊆ r2 ) if ∀s ∈ S : r1 (s) ≤ r2 (s).
We define the following operations on multisets:
Definition 5 (Multiset operations).
Maximum power pow(r) = maxs∈S r(s)
Minimum power minp(r) = mins∈S r(s)
Scalar product (k · r)(s) = k · r(s), for k ∈ Z
Scalar sum (r + k)(s) = r(s) + k, for k ∈ Z
Union (r1 ∪ r2 )(s) = max(r1 (s), r2 (s))
Sum (r1 + r2 )(s) = r1 (s) + r2 (s)
Subtraction (r1 − r2 )(s) = r1 (s) − r2 (s)
The operations described above have algebraic properties, e.g., r + r = 2 · r and
r1 − k · r2 = r1 + (−k) · r2 .
Definition 6 (Gradient). Let hS, Σ, T, s0 i be a TS. Given a multiset r and a
e e
transition s −→s0 ∈ T , its gradient is defined as δr (s −→s0 ) = r(s0 ) − r(s). If all
the transitions of an event e ∈ Σ have the same gradient, we say that the event
e has constant gradient, whose value is denoted as δr (e).
Incremental process mining Petri Nets & Concurrency – 179
5
s0
6
a b
s4 2 3
4 s1 3
a a b
a b
b
2 s2 1 s5 0 s6
a
0 s3 (a) (b)
Fig. 2. (a) Region in a TS: r(s0 ) = 6, r(s1 ) = 4, . . . , r(s6 ) = 0, (b) corresponding place
in the Petri net.
Definition 7 (Region). A region r is a multiset defined in a TS, in which all
the events have constant gradient.
Example 1. Fig. 2(a) shows a TS. The numbers within the states correspond to
the multiplicity of the multiset r shown. Multiset r is a region because both
events a and b have constant gradient, i.e. δr (a) = −2 and δr (b) = −3. There is
a direct correspondence between regions and places of a PN. The gradient of the
region describes the flow relation of the corresponding place, and the multiplicity
of the initial state indicates the number of initial tokens [10]. Fig. 2(b) shows
the place corresponding to the region shown in Fig. 2(a).
We say that region r is normalized if minp(r) = 0. Similarly, it is non-
negative if minp(r) ≥ 0. Any region r can become normalized by subtracting
minp(r) from the multiplicity of all the states.
Definition 8 (Normalization). We denote by ↓r the normalization of a region
r, so that ↓r = r − minp(r).
It is useful to define a normalized version of the sum operation between
regions, since it is closed in the class of normalized regions.
Definition 9 (Normalized sum). Let r1 and r2 be normalized regions, we
denote by r1 ⊕ r2 their normalized sum, so that r1 ⊕ r2 =↓(r1 + r2 ).
Definition 10 (Gradient vector). Let r be a region of a TS whose set of
events is Σ = {e1 , e2 , . . . , en }. The gradient vector of r, denoted as ∆(r), is the
vector of the event gradients, i.e. ∆(r) = (δr (e1 ), δr (e2 ), . . . , δr (en )).
Proposition 1. Gradient vectors have the following properties:
∆(r1 + r2 ) = ∆(r1 ) + ∆(r2 ) ∆(k · r) = k · ∆(r)
∆(r + k) = ∆(r) ∆(r1 − r2 ) = ∆(r1 ) − ∆(r2 )
∆(r1 ⊕ r2 ) = ∆(r1 ) + ∆(r2 )
180 Petri Nets & Concurrency Solé and Carmona
6
s0 s0 s0
a a
s1 c d = s1 ∪ c d
b a b a
s2 s3 s2 s2 s3
TS A TS A1 TS A2
Fig. 3. TS A is split into two subsystems A1 and A2 .
Regions can be partitioned into classes using their gradient vectors.
Definition 11 (Canonical region). Two regions r1 and r2 are said to be
equivalent if their gradient is the same, i.e. r1 ≡ r2 ⇔ ∆(r1 ) = ∆(r2 ). Given a
region r, the equivalence class of r, is defined as [r] = {ri | ri ≡ r}. A canonical
region is the normalized region of an equivalence class, i.e. ↓r.
Example of canonical regions are provided in Fig. 4, where two TSs are shown
in which some regions have been shadowed. For instance, the canonical region
r0 = {s1 , s2 } has gradient vector ∆(r0 ) = (1, 0). A PN built from the set of
minimal canonical regions has the same language as a PN built using all the
regions [5], thus it yields the smallest overapproximation with respect to the
language of the TS [10].
Definition 12 (Subregion, Empty region, Minimal canonical region).
r1 is a subregion of r2 , denoted as r1 v r2 , if, for any state s, ↓r1 (s) ≤ ↓r2 (s).
We denote by ∅ the region in which all states have zero multiplicity. A minimal
canonical region r satisfies that for any other region r0 , if r0 v r then r0 ≡ ∅.
3 Combining region bases
In this section we detail how region bases of different TSs can be joined, yielding
a region basis of their union. We will illustrate the theory with the running
example shown in Fig. 3. In this case, we assume A is a very large TS that
cannot be easily handled, hence it is split into two smaller subsystems, namely
A1 and A2 , so that A = A1 ∪ A2 .
3.1 Basis of regions
Definition 13 (Region basis). Given a TS, a region basis B = {r1 , r2 , . . . , rn }
is a minimal subset of the canonical regions of TS
Pnsuch that any region r can be
expressed as a linear combination of B ( i.e. r = i=1 ci ·ri , with ci ∈ Q, ri ∈ B).
Incremental process mining Petri Nets & Concurrency – 181
7
Event ∆(r0 ) ∆(r1 )
s0 s0 a 1 0 s0 s0
a a b 0 1
s1 s1 c d c d
Event ∆(q0 ) ∆(q1 )
b b a -1 -1 a a
s2 s2 s2 s3 s2 s3
c 1 0
d 0 1 q0 region q1 region
r1 region
r0 region
Fig. 4. Region bases for A1 and A2 .
The set of canonical regions of a TS, together with the normalized sum op-
eration, forms a free Abelian group [18]. Consequently, there exists a basis (i.e.
subset of the group) such that every element in the group can be rewritten as a
unique linear combination of the basis elements.
Region bases are interesting because, as the following theorem states, their
size is usually small.
Theorem 1 ([18]). Let hS, Σ, T, s0 i be a TS. The size of the region basis is less
or equal to min(|Σ|, |S| − 1).
3.2 Region compatibility
Given two systems described by their region basis, we want to obtain the region
basis of their union TS. The work more closely related is [16], in which it is
described how the set of regions in the joined system can be obtained from the
regions of the component systems. This is achieved by introducing the concept
of compatible (standard) regions. In this section we first review and extend this
concept of compatibility to generalized regions.
Definition 14 (Compatible TSs). Two TSs A1 and A2 are compatible if they
have the same initial state.
Def. 14 is more general than the one in [16], where the number of shared
states is restricted to one (the initial state). For instance, systems A1 and A2 of
Fig. 3 are compatible according to this definition, but not using the definition
in [16], since they share states s0 and s2 .
Definition 15 (Compatible regions, offset). Two regions r1 and r2 from
two compatible TSs A1 = hS1 , Σ1 , T1 , s0 i and A2 = hS2 , Σ2 , T2 , s0 i are said to be
compatible if:
– ∀e ∈ Σ1 ∩Σ2 , δr1 (e) = δr2 (e), i.e. they have the same gradient for all common
events, and,
182 Petri Nets & Concurrency Solé and Carmona
8
– ∃k ∈ Z : ∀s ∈ S1 ∩ S2 , r2 (s) − r1 (s) = k, i.e. the difference in multiplicity
of each shared state is equal to a constant, that we call the offset between r1
and r2 , denoted as off(r1 , r2 ).
Two compatible regions are said to be directly compatible if off(r1 , r2 ) = 0, a
fact that we denote as r1 ↔ r2 . Conversely, if off(r1 , r2 ) 6= 0, we say that the
regions are indirectly compatible and we use the following notation r1 ! r2 .
An immediate consequence of Def. 15 is that, if there is only a single shared
state, then any two regions with the same gradient for all common events are
compatible. This is, for instance, the case when TSs represent execution trees
and only the initial state is shared among them.
Two compatible regions can be made directly compatible by adding the offset
to one of them.
Definition 16 (Directly compatible region). Given two compatible regions
r1 and r2 with off(r1 , r2 ) > 0, the directly compatible region of r1 with respect to
r2 is r1↑r2 = r1 + off(r1 , r2 ).
Definition 17 (Union of compatible regions). Given two compatible regions
r1 and r2 , defined over sets of states S1 and S2 , respectively, with off(r1 , r2 ) > 0,
their union, denoted r1 t r2 , is
(
(r1↑r2 )(s) if s ∈ S1
(r1 t r2 )(s) =
r2 (s) otherwise
Proposition 2 (Union of compatible regions is a region of union sys-
tem). Given two compatible regions r1 and r2 of two compatible TSs A1 and
A2 , r1 t r2 is a region of A1 ∪ A2 . For each shared event, its gradient is equal
to the gradient in r1 or r2 , which are equal. For non-shared events of A1 (A2 ),
their gradient is the gradient in A1 (A2 ).
Proof. Assume off(r1 , r2 ) ≥ 0. Region r = r1 t r2 , where r1↑r2 = r1 + off(r1 , r2 ).
The latter entails that, in a shared state s, the multiplicity is the same for
r1 ↑r2 and r2 , which is the multiplicity assigned to r. For non-shared states, on
the other hand, the multiplicity assigned in r is the multiplicity of the region
whose TS contains the state. Thus any arc (either going from a shared to non-
shared state or any other combination) has a constant gradient, equal to the
gradient of that event in the corresponding region. Result transfers to r1 because
∆(r1 ) = ∆(r1↑r2 ). t
u
Example 2. In Fig. 5 we show one region of each subsystem of our running
example. They are compatible, since the gradient of the single shared event a is
the same in both regions. More specifically, they are indirectly compatible, since
their offset is different than 0.
Incremental process mining Petri Nets & Concurrency – 183
9
r q r q↑r
s0 s0 s0 s0
a a
s1 c d s1 c d
b a b a
s2 s2 s3 s2 s2 s3
Indirectly compatible Directly compatible
regions (r ! q) regions (r ↔ q ↑r )
Fig. 5. Region r of A1 and q of A2 , are indirectly compatible.
Property 1. Given two compatible non-negative regions r1 and r2 . If they are
directly compatible then r1 t r2 is a normalized region, if and only if, one of
them is normalized. If they are not directly compatible, but both of them are
normalized, then again r1 t r2 is a normalized region.
Proof. If one of them is normalized and they are directly compatible no modifi-
cation of multiplicities is performed, so the state with 0 multiplicity will remain
untouched and since regions are non-negative, then minp(r1 t r2 ) = 0. Con-
versely, if r1 t r2 is a normalized region and r1 ↔ r2 , then all multiplicities of
either r1 or r2 are greater or equal to 0, and since there is at least one 0 multi-
plicity, at least one of them must be normalized. If both are normalized but are
not directly compatible, only one of them modifies its multiplicities and we end
up in the same situation. t
u
3.3 Incremental algorithm for obtaining a basis
Given two TSs, A1 and A2 . Let {r1 , . . . , rn } be the region basis of A1 and
{q1 , . . . , qm } the basis of A2 . The set of all regions of the union system A1 ∪ A2
whose language satisfies L(A1 ∪ A2 ) ⊇ L(A1 ) ∪ L(A2 ) is obtained by finding all
non-trivial solutions for xi variables that satisfy:
X X
∀ei ∈ Σ1 ∩ Σ2 : δrj (ei ) · xj = δqk (ei ) · xn+k
1≤j≤n 1≤k≤m
i.e. for all common events their gradient must be the same on both systems.
This system of equations can be rewritten in matrix form as M ·x = 0, where
x is the column vector of variables xi and M is the following matrix:
δr1 (e1 ) . . . δrn (e1 ) −δq1 (e1 ) . . . −δqm (e1 )
δr1 (e2 ) . . . δrn (e2 ) −δq1 (e2 ) . . . −δqm (e2 )
M =
.. ..
. .
δr1 (ec ) . . . δrn (ec ) −δq1 (ec ) . . . −δqm (ec )
184 Petri Nets & Concurrency Solé and Carmona
10
where c is the number of common events in the system, i.e. c = |Σ1 ∩ Σ2 |. We
call this matrix the gradient compatibility matrix between A1 and A2 .
Compatibility of regions demands not only the gradients of common events to
be the same, but also that the offset is the same for all shared states. To enforce
such condition, assume that we shift all the regions in the bases {r1 , . . . , rn } and
{q1 , . . . , qm } so that for all ri and qj we have that ri (s0 ) = qj (s0 ) = 0. Now any
region obtained by combining the regions in the bases will have a 0 multiplicity
in the initial state. Thus, if the offset is the same in all shared states, their
multiplicity must coincide in all remaining shared states.
If there is a path between s0 and shared state s in which the same events
(and the same number of times but no matter in which order) are fired in both
TSs A1 and A2 , then the condition is automatically satisfied. Only in the case
where all paths are different, we say that shared state s is in conflict, and then
we must explicitly enforce the equality of the multiplicity of s in both systems.
This condition can be expressed in matrix form using a row for each shared
state in conflict (different than s0 since this state is never in conflict). For a shared
state s in conflict, its corresponding row will be of the form (r1 (s) . . . rn (s) −
q1 (s) . . . qm (s)), where all regions ri and qj have been shifted, as said before, so
that ri (s0 ) = qj (s0 ) = 0. Let us name as C the matrix containing such rows, we
will call it the shared state conflict matrix between A1 and A2 . Now since the
multiplicity of all these states must be the same, their subtraction must be 0.
Thus, C · x = 0.
Theorem 2. Let A1 and A2 be two compatible TSs with region bases {r1 , . . . , rn }
and {q1 , . . . , qm } respectively. Let M be their gradient compatibility matrix, C be
the shared state conflict matrix, and x the column vector of variables x1 to xn+m .
M
Consider an assignment to the variables in x such P that C · xP 0 and some
=
xi 6= 0. This assignment identifies a region rtq = 1≤i≤n ri xi t 1≤j≤m qj xn+j
in A1 ∪ A2 .
Proof.
P A non-trivial solution
P x defines two compatible regions, namely r =
1≤i≤n ri x i and q = 1≤j≤m qj xn+j , in A1 and A2 respectively. These two
regions are compatible according to Definition 15 if M · x = 0, because for com-
mon events the gradient is the same and the offset is the same in all shared
states if C · x = 0. By Proposition 2, r t q is a region of A1 ∪ A2 . t
u
So the problem reduces to finding the solutions to a homogeneous linear
system. Note that the system does not require to have solutions in the integer
domain. In fact all the solutions are in Q, since all the gradients are integers.
Homogeneous linear systems have one trivial solution (i.e. 0) and infinite non-
trivial solutions. Let yi be all the non-redundant solution vectors, then any
possible solution of the system can be obtained by linear combination of these
solution vectors, since adding or subtracting 0 from 0 does not change its value.
These yi are a basis of the nullspaceP of M C , and any solution x can be written
as a unique linear combination x = i λi yi , with λi ∈ Q.
There are several well-known methods to obtain a basis for the nullspace [19],
one of the easiest is to put the matrix in reduced row echelon form, determine the
Incremental process mining Petri Nets & Concurrency – 185
11
b0 b1
b10 b20 b11 b21
s0 s0 s0 s0
a a
s1 c d s1 c d
b a b a
s2 s2 s3 s2 s2 s3
−b0 −b1
−b10 −b20 −b11 −b21
s0 s0 s0 s0
a a
s1 c d s1 c d
b a b a
s2 s2 s3 s2 s2 s3
Fig. 6. Region basis {b0 , b1 } (and their coregions {−b0 , −b1 }) for system A1 ∪ A2 .
Regions are partitioned so that b0 = b10 ∪ b20 , where bi0 is the part of b0 in Ai .
free variables, and then, for each free variable xi , derive a vector of the basis by
assigning 1 to xi and 0 to the rest of free variables. The yi columns correspond
to the combination of regions of both system that have the same gradient, and
the resulting combined region is a region basis for the union TS.
Example 3. We will compute the region basis of the union of TSs A1 and A2
shown in Fig. 3. Two possible region basis for these systems are {r0 , r1 } and
{q0 , q1 }, show in Fig. 4. The matrix M in this case is
M = 1011
where columns (from left to right) correspond to regions r0 , r1 , q0 , q1 and there
is only a single row that corresponds to the only shared event between A1 and
A2 , namely event a.
The set of shared states is {s0 , s2 }, thus the shared state conflict matrix C
has only one row because only state s2 is reachable from s0 by firing a differ-
ent multiset of events. Consequently C = r0 (s2 ) r1 (s2 ) −q0 (s2 ) −q1 (s2 ) . With
matrices M and C we can now build
M 1 0 1 1 reduced row 10 1 1
= −−−−−−−−→
C 1 1 −1 0 echelon form 0 1 −2 −1
which is an indeterminate system with 2 degrees of freedom. We can write x1 =
2x2 + x3 and x0 = −x2 − x3 , so by changing the values of variables x2 and x3
186 Petri Nets & Concurrency Solé and Carmona
12
Comb. (1, −1): Comb. (−1, 1):
(0,0)
b10 + (−b11 ) −b10 + b11
s0 s0
a a
(1,0) (-1,0) (0,1) (0,-1)
s1 s1
b b
s2 s2
(1,1) (1,-1) (-1,1) (-1,-1)
Fig. 7. Exploration of the region space. Each node represents a combination of the
basis {b0 , b1 } that will be explored. The combinations shaded in blue are the ones for
which A1 yields a non-normalized region (shown on right), thus only these combinations
would be checked in A2 .
we can generate all the possible solutions. Given these parameters the region
solution will be ((−x2 − x3 ) · r0 + (2x2 + x3 ) · r1 ) t (x2 · q0 + x3 · q1 ). Using the
parameter values (1, 0), and (0, 1) for vector (x2 , x3 ) we do obtain the following
regions in the joined system: b0 = (−r0 + 2r1 ) t q0 and b1 = (−r0 + r1 ) t q1 . The
set {b0 , b1 } forms a region basis for the A1 ∪ A2 system (see Fig. 6).
4 Generating a PN from a basis
In [14] an algorithm was presented that allows finding minimal regions by careful
exploration of the region space defined by the region basis. The fundamental idea
is that the regions in the basis are initially assumed to be minimal, and then
combinations of these regions can only yield a minimal region if the resulting
region is non-normalized, since otherwise the region is a superregion of any of
its component regions.
However this approach cannot be directly used if the number of states in the
monolithic TS is too high to easily perform region operations in memory. The
alternative we propose in this paper is to partition the region operations into
the different component TSs, so that each time only the information of one of
the systems is accessed.
To achieve this partitioning, consider the region basis {b0 , . . . , bn }, we denote
by bji the part of region bi that belongs to subsystem j. All the regions in the
basis are assumed to be normalized, but the different bji could be non-normalized,
since they are defined so that, given i, all bji are directly compatible (cf. Def. 15).
For instance region b0 in Fig. 6 is normalized, however b20 it is not.
P
Consequently a combination of the basis i ci · bi yields a non-normalized
P j
region only if, for all subsystem j, i ci · bi is a non-normalized region (by
Incremental process mining Petri Nets & Concurrency – 187
13
Partial order ⊆ in A1 Partial order ⊆ in A2
(0,0) (0,0)
(1, -1) (0, -1) (-1, 1) (0, -1)
(-1, 0)
(0, 1) (-1, 1) (0, 1) (1, -1)
(1, 0)
(1, 0) (-1, 0)
Fig. 8. Partial orders between combinations of regions in each subsystem, according
to the subset relation on multisets (⊆).
Property 1)3 . Thus, the strategy would be to test the basis combinations in
the first subsystem, keeping only the combinations producing non-normalized
regions. Then only these combinations will be tested in the second subsystem,
discarding the ones that yield a normalized region, and the process will continue
until all subsystems have been checked.
Finally, with only the surviving combinations, the subregion test will be
performed to guarantee that only the minimal regions are found.
P Again this test
can be distributed among the subsystems, since i ci · bi ⊆ i c0i · bi if, and only
P
if, for all subsystem j, i ci · bji ⊆ i c0i · bji .
P P
We will illustrate all this process using our running example. In Fig. 7 we
can see a tree of combinations of the {b0 , b1 } basis. Each node is a tuple (c0 , c1 )
describing the coefficients used to obtain a region r as c0 · b0 + c1 · b1 . The second
level of the tree corresponds to the regions in the basis and their coregions (as
shown in Fig. 6). To bound the search space, assume we arbitrarily fix that the
coefficients are only allowed to take values in the set {−1, 0, 1}.
From the four possible combinations in the third level, two of them yield
already normalized regions in A1 , namely combinations (1, 1) and (−1, −1). On
the other hand, combinations (1, −1) and (−1, 1) correspond to non-normalized
regions in A1 , as shown in the figure. Consequently only these two combinations
will be checked in subsystem A2 . In this case, both regions, namely, b20 + (−b21 )
and −b20 +b21 , are also non-normalized in A2 . Thus these combinations correspond
to non-normalized regions in A1 ∪ A2 , which means that they might be minimal
regions (once normalized).
3
Since Property 1 only holds for non-negative regions, negative ci coefficients are
treated as markers for summing the normalized coregions of bi . For instance 2b1 −3b2
will be actually computed as 2 · b1 + 3 · ↓(−b2 ). This way all regions are always non-
negative and Property 1 can be safely used.
188 Petri Nets & Concurrency Solé and Carmona
14
a b d c
Fig. 9. Mined PN.
At this point we must check for minimal regions. The list of candidates
includes all the regions in the basis (and their coregions), that is all the combi-
nations in the second level, as well as combinations (1, −1) and (−1, 1) that have
been found during the exploration. To check for minimality, we create a partial
order among all these combinations in each subsystem (see Fig. 8). A region is
not minimal if there is a combination, different than (0, 0), that appears before
it in all the partial orders. In our example, combinations (1, 0) and (−1, 0) are
not minimal. Conversely, for instance (−1, 1) is minimal because, although com-
bination (0, −1) precedes it in A1 (i.e. −b11 ⊆ −b10 + b11 ), it is not longer true in
A2 (i.e. −b21 6⊆ −b20 + b21 ).
With the minimal regions found we build the mined PN of Fig. 9.
For a set of subsystems A1 , . . . , An the algorithm can be summarized as
follows:
– Take the first subsystem (A1 ) and explore region space until either combina-
tions are exhausted (according to the user defined bounds on the coefficients)
or the border of non-normalized regions is found.
– Pass to next subsystem the set of combinations of non-normalized regions
and check for normality in this other subsystem.
• If region is normalized, then discard, but mark sibling combinations to
be explored in the current subsystem (since all sibling combinations in
the first subsystem will remain to be non-normalized).
• On the other hand, if region is non-normalized and we are not in the last
subsystem, then add it to the list of regions that conform the border of
non-normalized regions that will be passed to next subsystem. If we are
already in the last subsystem, then add the combination to the list of
candidate minimal regions, normalize it, and then check the normaliza-
tion status in all subsystems. Sibling combinations are scheduled to be
explored in the first subsystem whose subpart of the region is normalized.
5 Conclusions
In this paper we have extended the theory developed in [14] to devise an incre-
mental algorithm for process mining. Given that space requirements are often the
Incremental process mining Petri Nets & Concurrency – 189
15
real bottleneck of some of the region-based techniques in the literature, methods
like the one presented in this paper might represent a crucial step into making
the theory applicable in industrial scenarios.
References
1. Ehrenfeucht, A., Rozenberg, G.: Partial (Set) 2-Structures. Part I, II. Acta Infor-
matica 27 (1990) 315–368
2. van der Aalst, W.M.P., Weijters, T., Maruster, L.: Workflow mining: Discovering
process models from event logs. IEEE Trans. Knowl. Data Eng. 16(9) (2004)
1128–1142
3. Badouel, E., Bernardinello, L., Darondeau, P.: Polynomial algorithms for the syn-
thesis of bounded nets. Lecture Notes in Computer Science 915 (1995) 364–383
4. Hoogers, P.W., Kleijn, H.C.M., Thiagarajan, P.S.: An event structure semantics
for general petri nets. Theor. Comput. Sci. 153(1&2) (1996) 129–170
5. Desel, J., Reisig, W.: The synthesis problem of Petri nets. Acta Inf. 33(4) (1996)
297–315
6. Badouel, E., Darondeau, P.: Theory of regions. In Reisig, W., Rozenberg, G., eds.:
Petri Nets. Volume 1491 of LNCS., Springer (1998) 529–586
7. Mukund, M.: Petri nets and step transition systems. Int. Journal of Foundations
of Computer Science 3(4) (1992) 443–478
8. Darondeau, P.: Deriving unbounded petri nets from formal languages. In Sangiorgi,
D., de Simone, R., eds.: CONCUR. Volume 1466 of Lecture Notes in Computer
Science., Springer (1998) 533–548
9. Bergenthum, R., Desel, J., Lorenz, R., Mauser, S.: Synthesis of petri nets from
finite partial languages. Fundam. Inform. 88(4) (2008) 437–468
10. Carmona, J., Cortadella, J., Kishinevsky, M.: New region-based algorithms for
deriving bounded Petri nets. IEEE Transactions on Computers 59(3) (2009)
11. Caillaud, B.: Synet : A synthesizer of distributable bounded Petri-nets from finite
automata. http://www.irisa.fr/s4/tools/synet/ (2002)
12. Cortadella, J., Kishinevsky, M., Lavagno, L., Yakovlev, A.: Deriving Petri nets
from finite transition systems. IEEE Trans. on Computers 47(8) (1998) 859–882
13. Carmona, J., Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L.,
Yakovlev, A.: A symbolic algorithm for the synthesis of bounded Petri nets. In:
Application and Theory of Petri Nets and Other Models of Concurrency. (2008)
14. Solé, M., Carmona, J.: Process mining from a basis of state regions. In: Application
and Theory of Petri Nets and other Models of Concurrency. LNCS, Springer (2010)
226–245
15. van der Aalst, W., Rubin, V., Verbeek, H., van Dongen, B., Kindler, E., Günther,
C.: Process mining: a two-step approach to balance between underfitting and
overfitting. Software and Systems Modeling (2009)
16. Dongen, B.F.V., Busi, N., Pinna, G.M., van der Aalst, W.: An iterative algo-
rithm for applying the theory of regions in process mining. In: Proceedings of
the Workshop on Formal Approaches to Business Processes and Web Services
(FABPWS’07). (2007) 36–55
17. Murata, T.: Petri Nets: Properties, analysis and applications. Proceedings of the
IEEE (April 1989) 541–580
18. Bernardinello, L., Michelis, G.D., Petruni, K., Vigna, S.: On the synchronic struc-
ture of transition systems. In Desel, J., ed.: Structures in Concurrency Theory,
Proc. of the Int. Workshop on Structures in Concurrency Theory. (1995) 69–84
190 Petri Nets & Concurrency Solé and Carmona
16
19. Kalman, D.: Basic null space calculations. The College Mathematics Journal 15(1)
(1984) 42–47