Page 52 -

34 2 Process Modeling and Analysis

The Petri net shown Fig. 2.2 can be formalized as follows: P ={start,c1,c2,c3,
c4,c5,end}, T ={a,b,c,d,e,f,g,h}, and F ={(start,a),(a,c1),(a,c2),(c1,b),
(c1,c), (c2,d), (b,c3), (c,c3), (d,c4), (c3,e), (c4,e), (e,c5), (c5,f ), (f,c1),
(f,c2), (c5,g), (c5,h), (g,end),(h,end)}.

Multi-sets
A marking corresponds to a multi-set of tokens. However, multi-sets are not
only used to represent markings; later we will use multi-sets to model event
logs where the same trace may appear multiple times. Therefore, we provide
some basic notations used in the remainder.
A multi-set (also referred to as bag) is like a set in which each element
2
3
2
may occur multiple times. For example, [a,b ,c ,d ,e] is the multi-set with
nine elements: one a,two b’s, three c’s, two d’s, and one e. The follow-
2
3
2
3
ing three multi-set are identical: [a,b,b,c ,d,d,e], [e,d ,c ,b ,a], and
3
2
2
[a,b ,c ,d ,e]. Only the number of occurrences of each value matters, not
the order. Formally, B(D) = D → N is the set of multi-sets (bags) over a fi-
nite domain D, i.e., X ∈ B(D) is a multi-set, where for each d ∈ D, X(d)
denotes the number of times d is included in the multi-set. For example, if
2
3
X =[a,b ,c ], then X(b) = 2 and X(e) = 0.
The sum of two multi-sets (X Y), the difference (X \ Y), the presence of
an element in a multi-set (x ∈ X), and the notion of subset (X ≤ Y) are de-
2 3 3 2 3
fined in a straightforward way. For example, [a,b ,c ,d] [c ,d,e ,f ]=
6
3
2
2
2
3
[a,b ,c ,d ,e ,f ] and [a,b]≤[a,b ,c]. Moreover, we can also apply
these operators to sets, where we assume that a set is a multi-set in which
2
3
every element occurs exactly once. For example, [a,b ] {b,c}=[a,b ,c].
The operators are also robust with respect to the domains of the multi-sets,
i.e., even if X and Y are defined on different domains, X Y, X \ Y, and
X ≤ Y are defined properly by extending the domain whenever needed.
The marking shown in Fig. 2.2 is [start], i.e., a multi-set containing only one
token. The dynamic behavior of such a marked Petri net is defined by the so-called
firing rule. A transition is enabled if each of its input places contains a token. An
enabled transition can fire thereby consuming one token from each input place and
producing one token for each output place. Hence, transition a is enabled at marking
[start]. Firing a results in the marking [c1,c2]. Note that one token is consumed
and two tokens are produced. At marking [c1,c2], transition a is no longer enabled.
However, transitions b, c, and d have become enabled. From marking [c1,c2],firing
b results in marking [c2,c3]. Here, d is still enabled, but b and c not anymore.
Because of the loop construct involving f there are infinitely many firing sequences
starting in [start] and ending in [end].
5
Assume now that the initial marking is [start ]. Firing a now results in the mark-
4
ing [start ,c1,c2]. At this marking, a is still enabled. Firing a again results in mark-
2
2
3
ing [start ,c1 ,c2 ]. Transition a can fire five times in a row resulting in marking