Petri nets are a generalization of automata, developed by C. A. Petri in the early 60s. A Petri net consists of a finite number of places linked by transitions. This is very similar to automata but the places can contain zero, one or more tokens, and each place can be connected to several transitions, as well as several transitions to one place. Petri nets have a greater expressive power than (finite) state automata, mainly due to the fact that a finite number of elements (places and transitions) can represent an infinite state-space. At the same time, Petri nets have certain limitations that do not allow them full expressive power (that is, they are not Turing machine equivalent). The limitations consist of not being able to test for the absence of tokens, that is, we cannot test for zero. There are extensions of Petri nets that allow this, however, we will not use those in our approach. We will merely use Petri nets as a more compact way to express automata. Primarily, we want to avoid the problems associated with infinite state-spaces, as described above. A short orientation about the more general Petri nets will be given, though.
A Petri net N can be described
by a 5-tuple, where
· P is the finite set of places (or rather, place-names). A place has zero or more (even an infinite number of) tokens at any time. A place represents a partial state and the token distribution among the places represents (the global) state of the net. Places are connected to transitions by directed and weighted arcs, some arcs pointing from transitions (the input-transitions) to the place, and some arcs pointing from the place to transitions (the output-transitions).
· T is a finite set of transitions (or rather, transition-names). A transition is connected to any number of places by directed and weighted arcs, some arcs pointing from places (the input-places) to the transitions, and some arcs pointing from the transition to places (the output-places).
·
is
a
incidence matrix defining the weights of
the arcs between the input-transitions and their output-places.
·
is
a
incidence matrix defining the weights of
the arcs between the input-places and their output-transitions
·
is
a vector of initial markings, specifying for each place the initial number of
tokens in that place.
Note that a Petri net consists of places and transitions, connected so that places are connected to transitions and transitions to places. Never are two places or two transitions connected. (Mathematically this is called a bipartite graph.) The following table is meant to clarify this.
Table 1. The various constructs valid for proper Petri nets. The gray constructs are valid for automata (additionally an automaton requires an initial marking with at most one token in each place and all weights 1).
In addition to the constructs shown in Table 1, the arcs are weighted. When the weight is 1 it is not explicitly given. Usually, for weight 2 (and perhaps 3) that number of 1-weighted arcs are drawn. With larger weights, the weight is explicitly specified beside a small diagonal mark, as in Figure 2.
Figure 2. A small Petri net with 4- and 5-weighted arcs.
When the input-places of a transition hold at least as many tokens as the weight of the respective arcs to the transition the transition is said to be fireable. This means that the transition can “be executed” and the marking will change due to the transition being executed, or fired. The marking of the net will then change so that the number of input-tokens required for the transition to be fired will be subtracted from the input-places, and the number of tokens determined by the weights of the output-arcs will be added to the respective output-places. In this way, the net will evolve as the transitions are fired.
The Petri net to the left above is described by the sets and matrices to the right. In
the current marking, which is the initial marking When
From
this marking, |
The evolution of a Petri net can be recorded as the markings resulting from the firing of the transitions. Writing down all evolutions of the net results in the reachability tree. This graph will have the initial marking as its root, and the consequent markings as its nodes, connected by the arcs representing the transitions fired. If the reachability tree is drawn without recurring markings so that when already present markings are not drawn again but arcs are pointing back, the result will be a graph; the reachability graph. Generally, the reachability tree cannot be drawn in its entirety, since it is infinitely large. However, the reachability graph can always be made of finite size, and for a certain class of Petri nets the reachability graph is of great importance.
In general, there are no restrictions on the number of tokens in a place so that the reachability tree will be infinite. However, it is reasonable to assume that the initial marking will not specify an infinite marking for any place. Furthermore, the structure of a net may be such that no place can ever acquire an infinite number of tokens. Such a net is said to be bounded.
Bounded Petri nets are important to us, since they in fact represent finite automata, though in disguise. For a bounded net, the reachability graph will correspond to the automata represented by the Petri net.
The Petri net shown in the previous example has the following reachability tree (left) and graph (right). The grayed bottom arrow of the reachability tree signifies that the tree recurses.
The reachability tree is infinitely large, since the net can execute its transition firing repeatedly as long as we let it, although the net is bounded. During that execution, though, the same marking (state) will be reached more than once. Thus, we can collapse the tree to let the arcs point back to previously already reached markings, and not write these down again. This gives us the reachability graph to the right. |
Bounded Petri nets allow us to verify important aspects about the nets. In many cases we do this by calculating the reachability graph and verify the properties on that. For instance, the net above is easily verified to be live, meaning that regardless of the firing order of the transitions and for how many times they are fired, no marking such that no transition can be fired will ever be reached[1]. This is, of course, easily asserted from the reachability graph as well as from the net itself, in this particular case. In other cases, it is not straightforward to ascertain this property for a complex net without using its reachability graph. In the reachability graph, on the other hand, determining liveness is merely a matter finding a state from which no transition can be made. (Note though, that algorithmically this may be a daunting task for large state-spaces.)
Above we have described and defined what is commonly referred to as autonomous Petri nets. This means that neither time nor external synchronization is involved in the model. The model is purely qualitative. However, it is crucial for our purposes to be able to synchronize transition firings on external events or on the firing of transitions in other nets. For this, we introduce labeled (sometimes also called synchronized) Petri nets. (We will as usual happily refrain from introducing absolute time, though).
A labeled Petri net is a
Petri net, as above, augmented with a set of transition-labels. That is, a labeled
Petri net is described by a 6-tuple , where
is a (finite) set
of transitions-labels that we can regard as events. The firing of a transition
t is associated with an event
so that
either
is
generated when t fires or t fires as
occurs (assuming t is enabled). Just as we did in the case
of automata, we will as far as possible avoid defining the causality between
whether the event is generated as the transition occurs or vice versa. Again,
this significantly simplifies our reasoning. Given a transition
we will
use
to
denote the event associated with t.
Note that several transitions could be associated with the same event.
To be able to use autonomous Petri nets together with labeled Petri nets, we can state the following convention.
An
autonomous Petri net can always be regarded as a
labeled Petri net
with the transition names as
the events.
Since it can always be arranged so that two Petri nets have disjoint place- as well as transition sets, this convention incurs no loss of generality.
As a labeled Petri net evolves its transition firings “executes” events.
Thus, a labeled Petri net PN has
a language . Since we do not define final
markings[2]
this language is always prefix closed.
Just as automata can be brought together to interact via synchronous compositions, so can Petri nets be synchronized. The definition is rather complex, much more so than in the automata case. When two Petri nets are synchronized, a transition in one Petri net labeled with an event in the alphabet of the other net, can fire only if an equally labeled transition in the other net also can fire. Thus, generating a new Petri net that describes the synchronous composition of two Petri nets essentially involves “layering” equally labeled transitions on each other. When more than one equally labeled transition exists in each net, we must consider all possible pairs of transitions from the two nets. For each of these pairs, a transition is added to the new net that fires if and only if both transitions fire in the old nets. This makes the place set of the new net equal to the union of the respective Petri nets place sets.
Let PN1 and PN2 be two labeled Petri nets.
Denote their synchronous composition . This is a new labeled Petri
net
where
(see Giua (1992))
1. The transition set T12 is defined as
·
If labels a transition
, then a labels a transition in T12 with the same input and output
places as t.
·
If labels a transition
, then a labels a transition in T12 with the same input and output
places as t.
·
If labels m transitions in
and n transitions in
, then a labels mn
transitions in T12,
each of which has the union of the input and output places of one transition
in
and
one transition in
as input and output place set,
respectively.
2.
The initial
marking is .
The and
matrices hold the
corresponding weights for the transitions of the new net, as usual. We have
not given their dimensions since this depends on the number of labels mutual
between the nest. If the two alphabets are disjoint, the dimensions of the matrices
will be
. Note that in general the set
of places grows linearly while the set of transitions may grow faster. Note
also that many transitions as well as places in the new net may not be reachable
from the initial marking. These are of little importance to us, and they will
be disregarded. Just as for automata, when
then
.
The synchronous composition of two Petri nets P1 and P2 is shown above in two versions. In P10, the b event is not in the alphabet of P1, so P2 can execute it freely when in p21. In P20, on the other hand, b is in the alphabet of P1, but there is no transition in P1 labeled by that event. In any case, the transitions of P1 can only be fired in participation with the a labeled transition of P2. Thus, in the composed system P10, P2 must make two “loops” for each loop executed by P1. While P2 executes its b transition, P1 remains in its state. In P20 the b event is hindered from ever being executed since no b-labeled transition exists in P1. In this composition, P1 can be though of as controlling the execution of b. The
language of P10 is |
[1] Note that this defines liveness of level x according to Peterson (1981), equating liveness with the absence of deadlocks. This definition suits our purposes better than the stronger “standard” definition that requires every transition eventually to be fireable from every reachable marking. We only require some transition to be fireable from each reachable marking.
[2] The language of a Petri net with final markings can be defined in several ways, each which may result in different languages. It is not obvious which of these definitions is most reasonable, see Peterson (1981). Thus, we refrain from introducing final markings, even though it could be valuable, particularly for specification purposes.