Page 64 -

2 The Language: Rationale and Fundamentals 51
Fig. 2.13 Petri net constructs

place transition arc

describing the dynamics of processes and are widely utilized. Although they have a
simple graphical format, they also have a precise operational semantics that makes
them an attractive option for modeling the static and dynamic aspects of processes.
A Petri net takes the form of a directed bipartite graph where the nodes are either
transitions or places. Figure 2.13 illustrates the elements appearing in a Petri net.
Places represent intermediate states that may exist during the operation of a process
and transitions correspond to the activities or events of which the process is made up.
Arcs connect places and transitions in such a way that places can only be connected
to transitions and vice versa. It is not permissible for places to be connected to places
or for transitions to be connected to other transitions. A directed arc from a place to a
transition indicates an input place to a transition and a directed arc from a transition
to a place indicates an output place of a transition. These places are significant when
discussing the operational semantics of Petri nets. A Petri net can be characterized
formally as follows.
Definition 1. (Petri net). A Petri net is a triple (P, T, F):

P is a finite set of places,
T is a finite set of transitions where P \ T D ∅;
F .P T/ [ .T P/ is a set of arcs known as the flow relation.
A place p is called an input place of a transition t if and only if there is a directed
arc from p to t. Similarly, a place p is called an output place of transition t if and
only if there is a directed arc from t to p. The set of input and output places for
a transition t are denoted t and t , respectively. The notations p and p have
analogous meanings: for example, p is the set of transitions that have p as an input
place.
The operational semantics of a Petri net are described in terms of tokens,which
signify a thread of control flowing through a process. Places in a Petri net can con-
tain any number of tokens. The distribution of tokens across all of the places in a net
is called a marking. It precisely describes the current state of an operational instance
of a process and can be characterized by the function M W P ! N. A state can be
compactly described as shown in the following example: 2p 1 C 1p 2 C 0p 3 C 1p 4
is the state with two tokens in place p 1 , one token in p 2 ,no tokens in p 3 ,and
one token in p 4 . We can also represent this state in the following (equivalent) way:
2p 1 C p 2 C p 4 .
We can usefully describe an ordering function over the set of possible states
such that for any two states M 1 and M 2, M 1 M 2 if and only if for each p 2 P W
M 1 .p/ M 2.p/. M 1 >M 2 iff M 1 M 2 and M 1 ¤ M 2 .