Page 145 -

5.1 Problem Statement 127

4
3
2
Fig. 5.2 WF-net N 2 discovered for L 2 =[ a,b,c,d , a,c,b,d , a,b,c,e,f,b,c,d ,
2
a,b,c,e,f,c,b,d , a,c,b,e,f,b,c,d , a,c,b,e,f,b,c,e,f,c,b,d ]
In this chapter, we focus on the discovery of Petri nets. The reason is that Petri
nets are simple and graphical while still allowing for the modeling of concurrency,
choices, and iteration. This is illustrated by Figs. 5.1 and 5.2. In both models, ac-
tivities b and c are concurrent. In N 1 , there is choice following a.In N 2 , there is
choice between d and e each time both b and c complete. Both N 1 and N 2 are sound
WF-nets. As explained in Chap. 2, WF-nets are a natural subclass of Petri nets tai-
lored toward the modeling and analysis of operational processes. A process model
describes the life-cycle of one case. Therefore, WF-nets explicitly model the cre-
ation and the completion of the cases. The creation is modeled by putting a token in
the unique source place i (place start in Figs. 5.1 and 5.2). The completion is mod-
eled by reaching the state marking the unique sink place o (place end in Figs. 5.1
and 5.2). Given a unique source place i and a unique sink place o, the soundness
requirement described in Definition 2.7 follows naturally. Recall that a WF-net N is
sound if and only if
• (N,[i]) is safe, i.e., places cannot hold multiple tokens at the same time.
• For any marking M ∈[N,[i] , o ∈ M implies M =[o], i.e., if the sink place is
marked, all other places should be empty (proper completion).
• For any marking M ∈[N,[i] , [o]∈[N,M , i.e., it is always possible to mark
the sink place (option to complete).
• (N,[i]) contains no dead transitions, i.e., all parts of the model are potentially
reachable.
Most process modeling notations use or assume correctness criteria similar to
soundness. For instance, deadlocks and livelocks are symptoms of a process that
cannot complete (properly). These phenomena are undesired, independent of the
notation used.
Although we use WF-nets in this chapter, this does not imply that discovered
process models cannot be presented using other notations. As discussed in Chap. 2,
there exist many translations from Petri nets into other notations and vice versa.
Compact formalisms with formal semantics like Petri nets are most suitable to de-
velop and explain process mining algorithms. The representation used to show re-
sults to end users is less relevant for the actual process discovery task. For example,
the WF-nets depicted in Figs. 5.1 and 5.2 can also be presented in terms of the