Page 199 -

6.4 Region-Based Mining 181

• X ⊆ A is the set of input transitions of R.
• Y ⊆ A is the set of output transitions of R.
• c ∈{0,1} is the initial marking of R.
k
• For any σ ∈ L, k ∈{1,...,|σ|}, σ 1 = hd k−1 (σ), a = σ(k), σ 2 = hd (σ) =
σ 1 ⊕ a:

c + ∂ multiset (σ 1)(t) − ∂ multiset (σ 2)(t) ≥ 0
t∈X t∈Y

R = (X,Y,c) is a region of L if and only if inserting a place p R with •p R = A,
p R •= B, and initially c tokens does not disable the execution of any of the traces
in L. To check this, Definition 6.4 inspects all events in the event log. Let σ ∈ L be
a trace in the log. a = σ(k) is the kth event in this trace. This event should not be
disabled by place p R . Therefore, we calculate the number of tokens M(p R ) that are
in this place just before the occurrence of the kth event.

M(p R ) = c + ∂ multiset (σ 1)(t) − ∂ multiset (σ 1)(t)
t∈X t∈Y

σ 1 = hd k−1 (σ) is the partial trace of events that occurred before the occurrence of
the kth event. ∂ multiset (σ 1 ) converts this partial trace into a multi-set. ∂ multiset (σ 1 ) is

also known as the Parikh vector of σ 1 . t∈X multiset (σ 1 )(t) counts the number of
∂

tokens produced for place p R , t∈Y multiset (σ 1 )(t) counts the number of tokens
∂
consumed from this place, and c is the initial number of tokens in p R . Therefore,
M(p R ) is indeed the number of tokens in p R just before the occurrence of the kth
event. This number should be positive. In fact, there should be at least one token in
p R if a ∈ Y. In other words, M(p R ) minus the number of tokens consumed from
p R by the kth event should be nonnegative. Hence,

M(p R ) − ∂ multiset a (t)
t∈Y

= c + ∂ multiset (σ 1)(t) − ∂ multiset (σ 2)(t) ≥ 0
t∈X t∈Y
This shows that a region R, according to Definition 6.4, indeed corresponds to a
so-called feasible place p R , i.e., a place that can be added without disabling any of
the traces in the event log.
The requirement stated in Definition 6.4 can also be formulated in terms of an
inequation system. To illustrate this, we use an example log from Chap. 5:

45 42

L 9 = a,c,d , b,c,e
There are five activities. For each activity t, we introduce two variables: x t and y t .
x t = 1 if transition t produces a token for p R and x t = 0 if not. y t = 1 if transition
t consumes a token from p R and y t = 0 if not. A potential region R = (X,Y,c)
corresponds to an assignment for all of these variables: x t = 1if t ∈ X, x t = 0if