Page 144 -

126 5 Process Discovery: An Introduction

3 2
Fig. 5.1 WF-net N 1 discovered for L 1 =[ a,b,c,d , a,c,b,d , a,e,d ]

ments. To make things more concrete, we define the target to be a Petri net model.
Moreover, we use a simple event log as input (cf. Definition 4.4). A simple event
∗
log L is a multi-set of traces over some set of activities A , i.e., L ∈ B(A ).For
example,
3 2

L 1 = a,b,c,d , a,c,b,d , a,e,d
L 1 is a simple log describing the history of six cases. The goal is now to discover a
Petri net that can “replay” event log L 1 . Ideally, the Petri net is a sound WF-net as
defined in Sect. 2.2.3. Based on these choices, we reformulate the process discovery
problem and make it more concrete.
Definition 5.2 (Specific process discovery problem) A process discovery algorithm
is a function γ that maps a log L ∈ B(A ) onto a marked Petri net γ(L) = (N,M).
∗
Ideally, N is a sound WF-net and all traces in L correspond to possible firing se-
quences of (N,M).

Function γ defines a so-called “Play-in” technique as described in Chap. 1. Based
on L 1 , a process discovery algorithm γ could discover the WF-net shown in Fig. 5.1,
i.e., γ(L 1 ) = (N 1 ,[start]). Each trace in L 1 corresponds to a possible firing se-
quence of WF-net N 1 shown in Fig. 5.1. Therefore, it is easy to see that the WF-net
can indeed replay all traces in the event log. In fact, each of the three possible firing
sequences of WF-net N 1 appears in L 1 .
Let us now consider another event log:
3 4 2
L 2 = a,b,c,d , a,c,b,d , a,b,c,e,f,b,c,d , a,b,c,e,f,c,b,d ,
2
a,c,b,e,f,b,c,d , a,c,b,e,f,b,c,e,f,c,b,d
L 2 is a simple event log consisting of 13 cases represented by 6 different traces.
Based on event log L 2 ,some γ could discover WF-net N 2 showninFig. 5.2.This
WF-net can indeed replay all traces in the log. However, not all firing sequences of
N 2 correspond to traces in L 2 . For example, the firing sequence a,c,b,e,f,c,b,d
does not appear in L 2 . In fact, there are infinitely many firing sequences because of
the loop construct in N 2 . Clearly, these cannot all appear in the event log. Therefore,
Definition 5.2 does not require all firing sequences of (N,M) to be traces in L.