CHAPTER 8
TIMED PETRI NETS
Petri nets were developed as an operational formalism for specifying untimed con-
current systems. They can show concurrent activities by depicting control and data
flows in different parts of the modeled system. As an operational formalism, a Petri
net gives a dynamic representation of the state of a system through the use of mov-
ing tokens. The original, classical, untimed Petri nets have been used successfully
to model a variety of industrial systems. More recently, time extensions of Petri nets
have been developed to model and analyze time-dependent or real-time systems. The
fact that Petri nets can show the different active components of the modeled system
at different stages of execution or at different instants of time makes this formalism
especially attractive for modeling embedded systems that interact with the external
environment.
8.1 UNTIMED PETRI NETS
A Petri net, or place-transition net, consists of four basic components: places, tran-
sitions, directed arcs, and tokens. A place is a state the specified system (or part of
it) may be in. The arcs connect transitions to places and places to transitions. If an
arc goes from a place to a transition, the place is an input for that transition and the
arc is an input arc to that transition. If an arc goes from a transition to a place, the
place is an output for that transition and the arc is an output arc from that transition.
More than one arc may exist from a place to a transition, indicating the input place’s
multiplicity. A place may be empty, or may contain one or more tokens. The state of
a Petri net is defined by the number of tokens in each place, known as the marking
and represented by a marking vector M. M[i] is the number of tokens in place i.
212
Real-Time Systems: Scheduling, Analysis, and Verification. Albert M. K. Cheng
Copyright
¶
2002 John Wiley & Sons, Inc.
ISBN: 0-471-18406-3
UNTIMED PETRI NETS

P
t
2
n2
cs2
cs2 r2
P
r3
r3
t
P
n2
t
1
n1
cs1
r1 cs1
T
tt
r2
P
P
t
cs3
P
3
T
cs3
n3
P

, t
cs2
,andt
cs3
, since the input
places of each transition contain tokens. The dot in place P
mutex
indicates that one
token (privilege) is available to grant to one task to enter and execute the critical
section. The task to obtain this privilege is selected nondeterministically. Suppose
task T
1
is selected, then the transition t
cs1
fires by removing the tokens from both
of its input places and then putting a token in its output place P
cs1
, indicating that
task T
1
is executing the critical section. Note that transitions t
cs2
and t
cs3
are now
disabled since the token in P
mutex
has been removed by the firing of t
cs1
.

if firing a transition enabled
in state s
1
leads the net to state s
2
.
8.2 PETRI NETS WITH TIME EXTENSIONS
Classical Petri nets cannot express the passage of time, such as durations and time-
outs. The tokens are also anonymous and thus cannot model named items. They
also lack hierarchical decomposition or abstraction mechanisms to properly model
large systems. To model realistic real-time systems, several extended versions of
Petri nets have been proposed to deal with timing constraints. There are basically
two approaches: one associates the notions of time to transitions and the other asso-
ciates time values to places.
[Ramchandani, 1974] associated a finite firing time to each transition in a classi-
cal Petri net to yield timed Petri nets (TdPNs). More precisely, the firing of a transi-
tion now takes time and a transition must fire as soon as it is enabled. TdPNs have
been used mainly for performance evaluation. Shortly thereafter, [Merlin and Farber,
1976] developed a more general class of nets called time Petri nets (TPNs). These
are Petri nets with labels: two values of time expressed as real numbers, x and y,are
associated with each transition where x < y. x is the delay after which and y is the
deadline by which to fire the enabled transition. A TPN can model a TdPn but not
vice versa.
PETRI NETS WITH TIME EXTENSIONS
215
8.2.1 Timed Petri Nets
A TdPN is formally defined as a tuple (P, T, F, V, M
0
, D) where
P is a finite set of places;

, t
2
,...,t
m
;
B is the backward incidence function B : T × P → N ,whereN is the set of
nonnegative integers;
F is the forward incidence function F : T × P → N ;
M
0
is the initial marking function M
0
: P → N ;
S is the static interval mapping
S : T → Q
∗
× (Q
∗
∪∞),whereQ
∗
is the set of positive rational numbers.
[Merlin and Farber, 1976] specifies timing constraints on a transition t
i
using
constrained static rational values as follows.
Static Firing Interval: Suppose α
i
S
and β
i

S
,β
i
S
) is the static firing interval for transition t
i
, indicated by the
superscript S,whereα
i
S
is the static earliest firing time (EFT) and β
S
is the static
216
TIMED PETRI NETS
latest firing time (LFT). In general, for states other than the initial state, the firing in-
tervals in the firing domain will be different from the static intervals. These dynamic
lower and upper bounds are denoted α
i
and β
i
, respectively, and are called simply
EFT and LFT, respectively.
Both the static and dynamic lower and upper bounds are relative to the instant at
which t
i
is enabled. If t
i
is enabled at time θ, then while t
i

(EFT,LFT) in I . Since the number of transitions enabled by a marking varies, the
number of entries in I also varies as the Petri net runs. If the enabled transitions are
ordered (numbered) in I , then entry i in I is the i th transition in the set of transitions
enabled by M.
Example. For the example Petri net in Figure 8.1, M = P
r1
(1), P
r2
(1), P
r3
(1),
P
mutex
(1). Four places are marked, each containing one token. There are three en-
abled transitions: t
cs1
, t
cs2
,andt
cs3
. Suppose I has the following three time interval
entries: (1, 6)(2, 7)(3, 8). Transition t
cs1
may fire at any time between 1 and 6.
Transition t
cs2
may fire at any time between 2 and 7. Transition t
cs3
may fire at any
time between 3 and 8. Note that as soon as one transition fires, the other two become

j
if
no other enabled transition has fired, modifying the marking and thus the state of the
TPN.
The firing of a transition t
i
at relative time δ leads the TPN to a new state S

=
(M

, I

), which can be derived as follows:
1. The new marking M

is derived with the usual Petri nets rule: ∀ pM

( p) =
M

( p) − B(t
i
, p) + F(t
i
, p).
2. To derive the new set of time intervals I

, we first remove from I the intervals
associated with the transitions that are disabled after firing t

2
,δ
2
) ···
(t
n
,δ
n
). This schedule is feasible from state S iff states exist such that
S
(t
1
,δ
1
)
−→ S
1
(t
2
,δ
2
)
−→ S
2
··· −→ S
n−1
(t
n
,δ
n

, t
cs3
may fire according to the
following timing restrictions. Transition t
cs1
may fire in the period between relative
time 1 (the EFT of (1,8)) and relative time 6 (the minimum of the LFTs (6,7,8) of the
218
TIMED PETRI NETS
intervals for the three enabled transitions). Similarly, transition t
cs2
may fire in the
period between relative time 2 (the EFT of (2, 7)) and relative time 6; and transition
t
cs3
may fire in the period between relative time 3 (the EFT of (3, 6)) and relative
time 6. The choice of which transition to fire is nondeterministic.
Thus at any time δ
1
within the infinite number of real values in interval (1, 6),
firing t
cs1
leads to state S
1
= (M
1
, I
1
):
M

2
=
(M
2
, I
2
):
M
1
= p
n1
(1), p
r2
(1), p
r3
(1) and
I
1
= (2, 4).
8.2.3 High-Level Timed Petri Nets
High-level timed Petri nets (HLTPNs), or time environment/relationship nets
(TERNs) [Ghezzi et al., 1991], integrate functional and temporal descriptions in
the same model. In particular, HLTPNs provide features that can precisely model
the identities of a system’s components as well as their logical and timing properties
and relationships. A HLTPN is a classical Petri net augmented with the following
features.
For each place, a restriction exists on the type of tokens that can mark it; for
example, each place has one or more types. If any type of token can mark a place,
then this place has the same meaning as in a classical Petri net. Each token has a
time-stamp indicating its creation time (or birth date) and a data structure for storing

postset of transition t , respectively. The weight of each arc is 1. Also, h(t)>0
for all t. The predicate of transition t, denoted π(t), is the projection of α(t)
on ENV
k(t)
.
3. A marking M is an assignment of multisets of environments to places.
4. In a marking M, a transition t is enabled iff for every input place p
i
of t, at least
one token env
i
exists such that the enabling tuple env
1
,...,env
k(t)
∈π(t).
More than one enabling tuple may exist for transition t, and a token may appear
in more than one enabling tuple.
5. A firing is a triple x =enab, t, prod, where enab is the input tuple, prod is
the output tuple, and enab, prod∈α(t ).
6. In a marking M, the firing enab, t, prod occurs by removing the enabling
tuple enab from the input places of transition T and storing the tuple prod in
the output places of transition T , thus producing a new marking, M

.
7. A firing sequence starting from marking M
0
is a finite sequence of firings,
enab
1

Example. Figure 8.2 shows a sample ER net, which consists of three places and one
transition with an action:
token
1
={x, −1, y, 2}
token
2
={x, 2, y, 2}
token
3
={x, 1, y, 2}
act ={p
1
, p
2
, p
3
| p
1
.x < p
2
.x ∧ p
1
.y = p
2
.y ∧
p
3
.x = p
1

1
3
2
token = {<x, 2>, <y, 2>}
Figure 8.2 Sample ER net.
enabling tuple for transition t. Firing t produces an environment in place p
3
where
p
3
.x =−1 + 1 = 0and p
3
.y = 2.
In the next section, we describe in detail time ER nets, the most recent of the three
time-extended Petri nets introduced here.
8.3 TIME ER NETS
To extend ER nets to specify the notions of time, a variable chronos is introduced
[Ghezzi et al., 1991] to represent the time-stamp of the token in each environment.
This time-stamp gives the time when the token is produced. The time-stamps of the
tokens put in output places are produced by the actions associated with the transitions
and are based on the selected input enabling a tuple’s environments’ values.
The variable chronos can take on nonnegative real numbers when used in a con-
tinuous time model, or nonnegative integers when used in a discrete time model.
This concept of a time-stamp assigned to a token when it is produced is similar to
the time value given by the occurrence function in real-time logic and the time value
τ indicating the time of the corresponding event occurrence in timed languages and
automata. An occurrence function assigns a time to the occurrence of an instance of
an event. τ denotes the occurrence time of an event ρ in the pair (ρ, τ ).
To enforce time restrictions on chronos, we need the following axioms.
Local Monotonicity Axiom: Let c

an ER net satisfying the constraint on time-stamps axiom iff for every i, j, i < j →
time(t
i
) ≤ time(t
j
).
For each firing sequence s with an initial marking M
0
in an ER net satisfying the
local monotonicity axiom and the constraint on time-stamps axiom, a time-ordered
firing sequence s

exists equivalent to s.
Time ER Net (TERN): An ER net satisfying both the local monotonicity axiom
and the constraint on time-stamps axiom, and with a variable chronos in every envi-
ronment, is a TERN.
Example. Figure 8.3 shows a partial TERN for a smart traffic light system at an in-
tersection. The traffic light for cars turns green when a car arrives at the intersection.
P
P
2
3
P
1
no pedestrian
for cars
car(s) at
intersection
light turns green
PP