Page 53 -

2.2 Process Models 35

Fig. 2.2 A marked Petri net

5
5
[c1 ,c2 ]. Note that after the first occurrence of a,also b, c, and d are enabled and
can fire concurrently.
To formalize the firing rule, we introduce a notation for input (output) places
(transitions). Let N = (P,T,F) be a Petri net. Elements of P ∪ T are called nodes.
A node x is an input node of another node y if and only if there is a directed arc from
x to y (i.e., (x,y) ∈ F). Node x is an output node of y if and only if (y,x) ∈ F .
For any x ∈ P ∪ T , •x ={y | (y,x) ∈ F} and x•={y | (x,y) ∈ F}.InFig. 2.2,
•c1 ={a,f } and c1•={b,c}.

Definition 2.3 (Firing rule) Let (N,M) be a marked Petri net with N = (P,T,F)
and M ∈ B(P). Transition t ∈ T is enabled, denoted (N,M)[t
, if and only if
•t ≤ M.The firing rule _[_
_ ⊆ N × T × N is the smallest relation satisfying
for any (N,M) ∈ N and any t ∈ T , (N,M)[t
⇒ (N,M)[t
(N,(M \•t) t•).

(N,M)[t
denotes that t is enabled at marking M, e.g., (N,[start])[a
in Fig. 2.2.
(N,M)[t
(N,M ) denotes that firing this enabled transition results in marking M .

For example, (N,[start])[a
(N,[c1,c2]) and (N,[c3,c4])[e
(N,[c5]).
Let (N,M 0 ) with N = (P,T,F) be a marked Petri net. A sequence σ ∈ T ∗
is called a firing sequence of (N,M 0 ) if and only if, for some natural number
n ∈ N, there exist markings M 1 ,...,M n and transitions t 1 ,...,t n ∈ T such that σ =
t 1 ,...,t n
and, for all i with 0 ≤ i< n, (N,M i )[t i+1
and (N,M i )[t i+1
(N,M i+1 ). 1

1 X is the set of sequences containing elements of X, i.e., for any n ∈ N and x 1 ,x 2 ,...,x n ∈ X:
∗
∗
x 1 ,x 2 ,...,x n
∈ X . See also Sect. 4.2.