Information Technology Reference
In-Depth Information
F
(
P
T
)
[
(
T
P
) is a set of arcs (flow relation),
W
:
F
!
{1, 2, 3, . . . } is a weight function,
M
0
:
P
{0, 1, 2, 3, . . . } is an initial marking.
A Petri net
N
!
¼
(
P
,
T
,
F
,
W
) without any specific initial marking is
denoted by
N
.
A Petri net with a given initial marking
M
0
is denoted by (
N
,
M
0
).
The meaning of Definition 2.1 is explained intuitively as follows. A
Petri net is a bipartite graph that consists of two disjoint set of nodes,
that is,
places
and
transitions
. Place nodes represent conditions or
resources, and transition nodes represent events that change conditions,
or consume/generate resources. In this bipartite graph, the
flow
relation
defines the directed arcs connecting places and transitions. If there is
an arc from a place
p
to a transition
t
,
p
is called an input place of
t
;if
there is an arc from a transition
t
to a place
p
,
p
is called an output place
of
t
. We use
t
and
t
to denote the sets of input and output places for a
transition
t
, respectively. Likewise,
p
and
p
are the sets of input and
output transitions of place
p
, respectively. Such a notation can be
extended to a set
S
T
,
S
S
x
.
Each arc has a
weight
that is a positive natural number. A Petri net
is called
ordinary
if each of the arc weights is one. When a place is
assigned a nonnegative integer
n
, we say that the place is holding or
marked with
n
tokens; when each place in a Petri net is assigned a
nonnegative integer, we say that the net is in a
marking
designated by
this token assignment. In Definition 2.1 of Petri nets, tokens in all places
are identical. Later we will see extensions of this definition in which
tokens belong to different types and thus are different.
The behavior of a Petri net is governed by its transition enabling and
firing rules, called execution rules for short. A transition of a Petri net is
enabled
and may
fire
when every of its input place has sufficient tokens,
that is, the number of tokens in it is not less than the weight of the
connecting arc. When a transition fires, it consumes tokens from each of
its input places and deposits tokens to all of its output places. The
numbers of consumed and deposited tokens are equal to the weight of
the corresponding arcs. Firing of a transition is atomic, that is, a single
noninterruptible step.
The firings of transitions are
nondeterministic
and
concurrent
.
When multiple transitions are enabled in some marking, any one of
2
P
[
¼[
S
x
and
S
¼[
x
2
x
2
