Page 51 -

2.2 Process Models 33

that the absence of deadlocks does not guarantee successful termination. The transi-
tion system may livelock, i.e., some transitions are still enabled but it is impossible
to reach one of the final states.
Any process model with executable semantics can be mapped onto a transition
system. Therefore, many notions defined for transition systems can easily be trans-
lated to higher-level languages such as Petri nets, BPMN, and UML activity dia-
grams. Consider, for example, the seemingly simple question: “When are two pro-
cesses the same from a behavioral point of view”. As shown in [120], many equiv-
alence notions can be defined. Trace equivalence considers two transition systems
to be equivalent if their execution sequences are the same. More refined notions
like branching bisimilarity also take the moment of choice into account. These no-
tions defined for transition systems can be used for any pair of process models as
long as the models are expressed in a language with executable semantics (see also
Sect. 5.3).
Transition systems are simple but have problems expressing concurrency suc-
cinctly. Suppose that there are n parallel activities, i.e., all n activities need to be ex-
ecuted but any order is allowed. There are n! possible execution sequences. The tran-
n
sition system requires 2 states and n × 2 n−1 transitions. This is an example of the
well-known “state explosion” problem [91]. Consider for example 10 parallel activi-
ties. The number of possible execution sequences is 10!= 3,628,800, the number of
reachable states is 2 10 = 1024, and the number of transitions is 10 × 2 10−1 = 5120.
The corresponding Petri net is much more compact and needs only 10 transitions
and 10 places to model the 10 parallel activities. Given the concurrent nature of
business processes, more expressive models like Petri nets are needed to adequately
represent process mining results.

2.2.2 Petri Nets

Petri nets are the oldest and best investigated process modeling language allowing
for the modeling of concurrency. Although the graphical notation is intuitive and
simple, Petri nets are executable and many analysis techniques can be used to ana-
lyze them [58, 77, 96]. In the Introduction, we already showed an example Petri net.
Figure 2.2 shows the Petri net again with the various constructs highlighted. A Petri
net is a bipartite graph consisting of places and transitions. The network structure
is static, but, governed by the firing rule, tokens can flow through the network. The
state of a Petri net is determined by the distribution of tokens over places and is
referred to as its marking. In the initial marking shown in Fig. 2.2 there is only one
token; start is the only marked place.

Definition 2.2 (Petri net) A Petri net is a triplet N = (P,T,F) where P is a finite
set of places, T is a finite set of transitions such that P ∩T =∅, and F ⊆ (P ×T)∪
(T ×P) is a set of directed arcs, called the flow relation.A marked Petri net is a pair
(N,M), where N = (P,T,F) is a Petri net and where M ∈ B(P) is a multi-set over
P denoting the marking of the net. The set of all marked Petri nets is denoted N .