Home Up Questions?

Chapter 4. Analysis of Petri Nets

In the last chapter we demonstrated the modeling power of Petri nets. Petri nets are capable of modeling a large variety of systems, properly representing the interactions between the various actions which can occur. The major strength of Petri nets is, of course, in the modeling of systems which may exhibit concurrency; concurrency is modeled in a natural and convenient way. A Petri net model can be used to represent and communicate the design of a concurrent system.

However, modeling by itself is of little use. It is necessary to analyze the modeled system. This analysis will hopefully lead to important insights into the behavior of the modeled system. Thus, we turn now to presenting analysis techniques for Petri nets. Several techniques have been developed for the analysis of Petri nets, but many problems in the analysis of Petri nets are still open. To better evaluate the usefulness of the analysis techniques which have been developed, we first consider what types of problems may need to be solved for Petri nets. The objective of the analysis of a Petri net is to determine the answer to a question about the Petri net. What types of questions might be asked about Petri nets?

4.1. Analysis Problems for Petri Nets

The following properties and questions have been considered in the literature about Petri nets. We define and illustrate these properties here; we show the appropriate analysis techniques in the second portion of this chapter.

4.1.1. Safeness

For a Petri net which is to model a real hardware device, one of the more important properties is safeness. A place in a Petri net is safe if the number of tokens in that place never exceeds one. A Petri net is safe if all places in the net are safe.

DEFINITION 4.1
A place piP of a Petri net C = (P, T, I, O) with initial marking μ is safe if for all μ′ ∈ R ( C, μ ), μ′ ( pi ) ≤ 1 . A Petri net is safe if each place in that net is safe.
Safeness is a very important property for hardware devices. If a place is safe, then the number of tokens in that place is either 0 or 1. Thus the place can be implemented by a single flip-flop.

The original Petri nets were safe by definition, since a transition could not fire unless all of its output places were empty (and multiple arcs were not allowed). This was motivated by the interpretation of a place as representing a condition. A condition, being a logical statement, is either true (represented by a token in the place) or false (represented by an absence of a token); multiple tokens have no interpretation. Thus, the marking of each place should be safe under an interpretation as conditions and events.

As long as a place is not a multiple input or multiple output of a transition, it is possible to force that place to be safe. A place pi which is to be forced to be safe is supplemented by another place pi′ . Transitions which use pi as an input or output are modified as follows:


The object of this new place pi′ is to represent the condition “ pi is empty.” Thus pi and pi′ are complementary; pi has a token only if pi′ has no token and vice versa. Any transition which removes a token from pi must deposit one in pi′, and any transition which removes a token from pi′ must deposit one in pi. The initial marking must also be modified to provide exactly one token in either pi or pi′ . (We assume that the initial marking is safe.) Notice that this forced safeness is only possible for places which are safe in the initial marking and whose input and output multiplicity is either 0 or 1 for all transitions. A place which has an output multiplicity of two for a transition will receive two tokens when that transition fires and hence cannot be safe. Figure 4.1 is a simple Petri net which has been forced to be safe in Figure 4.2.


Figure 4.1. A Petri net. This net is not safe.





Figure 4.2. The Petri net of Figure 4.1 can be forced to be safe as shown here.


4.1.2. Boundedness

Safeness is a special case of the more general boundedness property. Some thought about the real limitation to implementing places in hardware shows that it is not necessary to require safeness. Safeness allows a place to be implemented with a flip-flop, but, more generally, a counter could be used. However, any such hardware counter would be limited in the maximum number which could be represented. A place is k-safe or k-bounded if the number of tokens in that place cannot exceed an integer k.

DEFINITION 4.2
A place piP of a Petri net C = (P, T, I, O) with an initial marking μ is k-safe if for all μ′ ∈ R ( C, μ ), μ′ ( pi ) ≤ k.

A place which is 1-safe is simply called safe. Notice that the bound k on the number of tokens which can be in a place may be a function of the place (e.g., place p1 may be 3-safe while place p2 is 8-safe). However, if a place pi is k -safe, then it is also k′ -safe for all k′ ≥ k. Since there are only a finite number of places, we can pick k to be the maximum of the bounds of each place and define a Petri net to be k -safe if every place of the net is k -safe.

We may sometimes be concerned only with whether or not the number of tokens in a place is bounded or not, but we are not concerned with the specific value of the bound. A place is bounded if it is k -safe for some k; a Petri net is bounded if all places are bounded. A bounded Petri net could be realized in hardware, while a Petri net with an unbounded place could not in general be implemented in hardware. (Remember that these definitions are independent of interpretation. In implementation a place might represent some entity which is bounded, although the net structure itself does not reflect this fact.)

4.1.3. Conservation

Petri nets can be used to model resource allocation systems. For example, a Petri net can model the requests, allocations, and releases of input/output devices in a computer system. In these systems some tokens may represent the resources. A set of three line printers is represented by a place with an initial marking of three tokens. A request for a line printer is a transition which has this place as an input; the line printer is later released by a transition with an output to the line printer place.

For these types of Petri nets, among others, conservation is an important property. We would like to show that tokens which represent resources are neither created nor destroyed. The simplest way to do this would be to require that the total number of tokens in the net remain constant.

DEFINITION 4.3
A Petri net C = (P, T, I, O) with initial marking μ is strictly conservative if for all μ′ ∈ R ( C, μ ),

Σ μ′(pi) = Σ μ(pi).
piP     piP  

Strict conservation is a very strong relationship. For example, one can immediately show that the number of inputs to each transition must equal the number of outputs, | I ( tj ) | = | O ( tj ) | . If this were not the case, firing transition tj would change the number of tokens in the net.

For a broader view, however, consider Figure 4.3. Figure 4.3 is not strictly conservative since the firing of either transition t1 or t3 will decrease the number of tokens by one, while firing transition t2 or t4 will add a token to the marking. We could, however, convert the Petri net of Figure 4.3 to the net of Figure 4.4, which is strictly conservative.



Figure 4.3. A Petri net which is not strictly conservative.





Figure 4.4. A strictly conservative Petri net which is equivalent to the net of Figure 4.3.


A Petri net should conserve the resources which it is modeling. However, there is no one-to-one mapping between tokens and resources. Some tokens represent program counters or other items; other tokens may represent several resources with one token. This token is later used to create multiple tokens (one per resource) by firing a transition with more outputs than inputs. In general, we would like to define a weighting of tokens. The weighted sum for all reachable markings should be constant. Tokens which are not important can be assigned a weight of 0; other tokens can be assigned weights of 1, 2, 3, or any other integer. (Rational numbers would be acceptable since the weightings could be multiplied by a common denominator to define an integer weighting. Irrational weights would not seem to be needed.)

A token is defined by its place in the net, and all tokens in a place are indistinguishable. Thus the weights are associated with each place of the Petri net. A weighting vector w = ( w1, w2, …, wn ) defines a weight wi for each place piP.

DEFINITION 4.4
A Petri net C = (P, T, I, O) with initial marking μ, is conservative with respect to a weighting vector w, w = ( w1, w2, …, wn ), n = | P |, wi ≥ 0, if for all μ′ ∈ R ( C, μ ),

Σ wi ⋅ μ′(pi) = Σ wi ⋅ μ(pi).
i i

A strictly conservative Petri net is conservative with respect to the weighting vector (1, 1, …, 1). All Petri nets are conservative with respect to the weighting vector (0, 0, …, 0). The latter observation is disturbing since we would like to define a Petri net as conservative if it is conservative with respect to some weighting vector. However, since every Petri net is conservative with respect to the zero vector, this would not be satisfactory. Thus, a Petri net is conservative if it is conservative with respect to some positive nonzero weighting vector, w > 0 (with positive nonzero weights, wi > 0 ).

The Petri net of Figure 4.3 is therefore conservative since it is conservative with respect to (1, 1, 2, 2, 1). The Petri net of Figure 4.5 is not conservative.



Figure 4.5. A nonconservative Petri net.


4.1.4. Liveness

The motivation for considering conservation in a Petri net was resource allocation in a computer operating system. Another problem which may arise in resource allocation for a computer system is deadlock. Deadlock has been the subject of a number of studies in computer science [Hebalkar 1970]. A simple example can best illustrate the problem: Consider a system with two different resources q and r and two processes a and b. If both processes need both resources, it will be necessary to share them. To accomplish this we require each process to request a resource and later release it. Now suppose process a first requests resource q and then resource r and finally releases both q and r. Process b is similar but first requests r and then q. Figure 4.6 illustrates these two processes and the resource allocation with a Petri net.



Figure 4.6. Resource allocation for two processes ( a and b ) and two resources (q [modeled by p4 ] and r [modeled by p5 ]).


The initial marking indicates resources q ( p4 ) and r ( p5 ) are available and processes a and b are ready. One execution of this net is t1 t2 t3 t4 t5 t6; another is t4 t5 t6 t1 t2 t3. Neither of these executions results in deadlock. However, consider the sequence which starts t1 t4: Process a has q and wants r; process b has r and wants q. The system is deadlocked; neither process can proceed.

A deadlock in a Petri net is a transition (or a set of transitions) which cannot fire. In Figure 4.6, deadlock occurs if transitions t2 and t5 cannot fire. A transition is live if it is not deadlocked. This does not mean that the transition is enabled but rather that it can be enabled. A transition tj of a Petri net C is potentially fireable in a marking μ if there exists a marking μ′ ∈ R ( C, μ ) and tj is enabled in μ′ . A transition is live in a marking μ if it is potentially fireable in every marking in R ( C, μ ) . Thus if a transition is live, it is always possible to maneuver the Petri net from its current marking to a marking which would allow the transition to fire.

There are other concepts, related to liveness, which have been considered in studies of deadlock [Commoner 1972]. These can be categorized as levels of liveness and can be defined for a Petri net C with marking μ as


A transition which is live at level 0 is dead. A transition which is live at level 4 is live. A Petri net is live at level i if every transition is live at level i.

As an example of these levels of liveness, consider Figure 4.7. Transition t0 can never fire; it is dead. Transition t1 can fire exactly once; it is live at level 1. Transition t2 can be made to fire an arbitrary number of times, but the number of times is dependent on the number of times that t3 fires. If we want to fire t2 five times, we fire t3 five times, then t1, and then t2 five times. However, once t1 fires (and t1 must fire before t2 can fire), the number of times t2 can fire is fixed. Thus, t2 is live at level 2, but not at level 3. Transition t3, on the other hand, can be fired an infinite number of times and so is live at level 3, but not at level 4, since once t1 fires t3, can no longer fire.



Figure 4.7. A Petri net to illustrate different levels of liveness.


4.1.5. Reachability and Coverability

Most of the problems which have been mentioned so far are concerned with reachable markings. Perhaps the simplest problem (to state) is the reachability problem.

DEFINITION 4.5 The Reachability Problem
Given a Petri net C with marking μ and a marking μ′, is μ′ ∈ R ( C, μ ) ?

The reachability problem is perhaps the most basic Petri net analysis problem; many other analysis problems can be stated in terms of the reachability problem. For example, for the Petri net of Figure 4.6, deadlock can occur if the state (0, 1, 0, 0, 0, 0, 1, 0) is reachable.

Figure 4.8 shows a Petri net which purports to solve the mutual exclusion problem -- places p4 and p9 are expected to be mutually exclusive. We wish to know if any state is reachable with p4 = 1 and p9 = 1 . This problem is similar to reachability but is slightly different; it is called the coverability problem. A marking μ′′ covers a marking μ′ if μ′′ ≥ μ′ .

DEFINITION 4.6 The Coverability Problem
Given a Petri net C with initial marking μ and a marking μ′, is there a reachable marking μ′′ ∈ R ( C, μ ) such that μ′′ ≥ μ′ ?



Figure 4.8. A Petri net representation of Hyman's "solution" to the mutual exclusion problem [Hyman 1966]. Due to the constant use of the place k0, k1, b1, and b0, these are repeated in the graph to make it easier to read. All places labeled k0 are the same place.


Another possible use of reachability-type problems would be to ignore the contents of some places, concentrating only on matching or covering the contents of a few important places. For example, in the Petri net of Figure 4.8, our interest is confined to places p4 and p9; the markings of the remaining places are not important. Thus, we can consider reachability or coverability modulo a set of places. These problems are called the submarking reachability and submarking coverability problems.

These problems can be further complicated by wanting to know reachability or coverability for a set of markings, the set reachability and set coverability problems. However, if the set is finite, the set problems can obviously be solved by repeated solutions of the reachability and coverability problems for one marking.

4.1.6. Firing Sequences

Another approach to analysis which has been suggested concentrates on sequences of transition firings rather than on states. This is related to liveness, since we may ask, Can transition tj be fired (i.e., is it dead)? But more generally we may want to determine if a specific sequence of transition firings is possible or if any of a set of firing sequences is possible. In Figure 4.8, for example, mutual exclusion would be violated if the sequence t3 t9 can occur, or if t4 t10 can occur, or, more generally, if t3 σ t9 can occur, where σ is any sequence of firings not including t4. These analysis questions introduce the concept of languages of Petri nets and will be investigated in more detail in Chapter 6.

4.1.7. Equivalence and Subset Problems

A final class of problems arises from optimization considerations. If a Petri net exhibits a certain behavior, as indicated by its set of transition firing sequences and its reachability set, can the Petri net be changed (optimized) without affecting its behavior? This may involve deleting dead transitions (which can never be fired) and dead places (which can never be marked) or perhaps the redefinition of some transitions. Can we show that two different marked Petri nets with the same number of transitions (but perhaps different numbers of places) will generate the same sequence of transition firings or that two different marked Petri nets with the same number of places (but perhaps different numbers of transitions) will generate the same reachability set? This might allow us to modify Petri nets to increase parallelism, decrease the cost of implementation, or other optimizations.

In these cases, we are concerned with determining if two Petri nets are equivalent or if one is a subset of the other. We must be careful with these problems to define the notion of equivalence or containment carefully. If we define equivalence as equal reachability sets, then we cannot change the number of places, while if we require equality of sets of transition firing sequences, we may not be able to change transitions. Our definition of the problem is therefore quite important.

4.2. Analysis Techniques

There are other problems that can be considered, but those presented here are the most common problems mentioned in the literature; we mention others as it becomes necessary to introduce them. You can see that there are a number of problems which may need solution for Petri nets. Can we develop analysis techniques to solve these problems? In particular, of course, we want to develop techniques which can be easily implemented on a computer, to allow automatic analysis of modeled systems.

Two major Petri net analysis techniques have been suggested, and we present these in this section. These techniques provide solution mechanisms for some of the above problems. The major analysis technique which has been used with Petri nets is the reachability tree; the other technique involves matrix equations. We discuss each of these in turn.

4.2.1. The Reachability Tree

The reachability tree represents the reachability set of a Petri net. As an example, consider the marked Petri net of Figure 4.9. The initial marking is (1, 0, 0). In this initial marking two transitions are enabled: t1 and t2. Since we wish to consider the entire reachability set, we define new nodes in the reachability tree for the (reachable) markings which result from firing both transitions. An arc, labeled by the transition fired, leads from the initial marking to each of the new markings (Figure 4.10). This (partial) tree shows all markings which are immediately reachable from the initial marking.



Figure 4.9. A marked Petri net for illustrating the construction of a reachability tree.





Figure 4.10. The first steps in building a reachability tree.


Now we must consider all markings reachable from these new markings. From marking (1, 1, 0), we can again fire t1 [giving (1, 2, 0)] and t2 [giving (0, 2, 1)]; from (0, 1, 1) we can fire t3 [giving (0, 0, 1)]. This produces the tree of Figure 4.11. With the three new markings, we must repeat this process, producing new markings to add to the tree as shown in Figure 4.12. Notice that the marking (0, 0, 1) is dead; no transitions are enabled, and so no new markings are produced in the tree by this dead marking. Also notice that the marking produced by firing t3 in (0, 2, 1) is (0, 1, 1); the marking (0, 1, 1) was also produced directly from the initial marking by firing t2.



Figure 4.11. The second step in building a reachability tree.





Figure 4.12. The third step in building a reachability tree.


If this procedure is repeated over and over, every reachable marking will eventually be produced. However, the resulting reachability tree might well be infinite. Every marking in the reachability set will be produced, and so for any Petri net with an infinite reachability set, the corresponding tree would also be infinite. Even a Petri net with a finite reachability set can have an infinite tree (Figure 4.13). The tree represents all possible sequences of transition firings. Every path in the tree, starting at the root, corresponds to a legal transition sequence. If the tree is going to be a useful analysis tool, we must find a means to limit it to a finite size. (Notice that if the representation of an infinite set is finite, then an infinite number of markings must be mapped onto the same representation. This will, in general, result in a loss of information, which may mean that some properties of Petri nets cannot be determined, but this depends on how the representation is done.)



Figure 4.13. A simple Petri net with an infinite reachability tree.


The reduction to a finite representation is accomplished by several means. We must find a means of limiting the new markings (called frontier nodes) introduced at each step. This is helped by dead markings -- markings in which no transition is enabled. These dead markings are known as terminal nodes. Another class of markings are those markings which have previously appeared in the tree. These duplicate markings are known as duplicate nodes, and no successors of a duplicate node need be considered; all these successors will be produced from the first occurrence of the marking in the tree. Thus in the tree of Figure 4.12, the marking (0, 1, 1) which results from the sequence t1 t2 t3 does not produce any further nodes in the tree, since it occurred earlier in the tree as a result of the sequence t2 from the initial marking.

One final means is used to reduce the reachability tree to a finite representation. Consider a sequence of transition firings σ which starts at a marking μ and ends at a marking μ′ with μ′ > μ . The marking μ′ is the same as the marking μ except that it has some “extra” tokens in some places, that is, μ′ = μ + ( μ′ − μ ) and ( μ′ − μ ) > 0 . Now, since transition firings are not affected by extra tokens, the sequence σ can be fired again, starting in μ′, leading to a marking μ′′ . Since the effect of the sequence of transitions σ was to add μ′ − μ tokens to the marking μ, it will also add μ′ − μ tokens to the marking μ′, so μ′′ = μ′ + ( μ′ − μ ) or μ′′ = μ + 2 ( μ′ − μ ) . In general, we can fire the sequence σ n times to produce a marking μ + n ( μ′ − μ ) . Thus, for those places which gained tokens from the sequence σ, we can create an arbitrarily large number of tokens simply by repeating the sequence σ as often as desired. In the Petri net of Figure 4.9, for example, we can fire transition t1 as many times as we want to build up an arbitrary number of tokens in p2.

We represent the infinite number of markings which result from these types of loops by using a special symbol, ω, which can be thought of as “infinity” and which represents a number of tokens which can be made arbitrarily large. For any constant a, we define

ω + a = ω
ω − a = ω
a < ω
ω ≤ ω

These are the only operations on ω which are necessary for the construction of the reachability tree.

The actual algorithm to construct the reachability tree can now be precisely stated. Each node i in the tree is associated with an extended marking μ [ i ] ; the marking is extended to allow the number of tokens in a place to be either a nonnegative integer or the ω symbol. Each node is also classified as either a frontier node, a terminal node, a duplicate node, or an internal node. Frontier nodes are nodes which have not yet been processed by the algorithm; they are converted by the algorithm to terminal, duplicate, or interior nodes.

The algorithm begins by defining the initial marking to be the root of the tree and, initially, a frontier node. As long as frontier nodes remain, they are processed by the algorithm.

Let x be a frontier node to be processed.

  1. If there exists another node y in the tree which is not a frontier node, and has the same marking associated with it, μ [ x ] = μ [ y ], then node x is a duplicate node.

  2. If no transitions are enabled for the marking μ [ x ], [i.e., δ ( μ [ x ], tj ) is undefined for all tjT ], then x is a terminal node.

  3. For all transitions tjT which are enabled in μ [ x ], [i.e., δ ( μ [ x ], tj ) is defined], create a new node z in the reachability tree. The marking μ [ z ] associated with this new node is, for each place pi,

    1. If μ [ x ]i = ω, then μ [ z ]i = ω .

    2. If there exists a node y on the path from the root node to x with μ [ y ] < δ ( μ [ x ], tj ) and μ [ y ]i < δ ( μ [ x ], tj )i, then μ [ z ]i = ω .

    3. Otherwise, μ [ z ]i = δ ( μ [ x ], tj )i.

    An arc, labeled tj, is directed from node x to node z. Node x is redefined as an interior node; node z becomes a frontier node.

When all nodes have been classified as terminal, duplicate, or interior, the algorithm halts.

Figure 4.14 is the reachability tree of the Petri net of Figure 4.9. Figure 4.15 is the reachability tree of the Petri net of Figure 4.16.



Figure 4.14. The reachability tree of the Petri net of Figure 4.9.





Figure 4.15. A Petri net to illustrate the construction of a reachability tree.





Figure 4.16. The reachability tree of the Petri net of Figure 4.15.


A very important property of the algorithm to construct a reachability tree is the fact that it terminates. To prove this we must show that the algorithm cannot continue to create new frontier nodes forever. The proof of this property requires three lemmas.

LEMMA 4.1 Konig's Infinity Lemma
In any infinite directed tree in which each node has only a finite number of direct successors, there is an infinite path leading from the root.

Proof :
Start at the root with node x0. Since there are only a finite number of direct successors to x0, but the total number of nodes in the tree is infinite, at least one of the direct successors of x0 must be the root of an infinite subtree. (If all the subtrees of direct successors of x0 were finite, then the tree of x0 would be finite.) Pick a node x1 which is a direct successor of x0 with an infinite subtree. Now one of its direct successors is also the root of an infinite subtree; pick x2 to be such a direct successor. Continuing in this manner, we produce the infinite path x0, x1, x2, … in the tree. Q.E.D.
LEMMA 4.2
Every infinite sequence of nonnegative integers contains an infinite nondecreasing subsequence.

Proof :
There are two cases:

  1. If any element of the sequence occurs infinitely often, then let x0 be such an element. The infinite subsequence, x0, x0, x0, … is an infinite nondecreasing subsequence.

  2. If no element occurs infinitely often, then each element occurs only a finite number of times. Let x0 be an arbitrary element of the sequence. There are at most x0 integers which are nonnegative and less than x0 [ 0, …, x0 − 1 ], and each of these occurs only a finite number of times in the sequence. Thus, by continuing far enough in the sequence, we must encounter an element x1 with x1x0. Similarly, there must exist an x2 farther on in the sequence with x2x1, and so on. This defines an infinite nondecreasing subsequence, x0, x1, x2, … .

In either case, an infinite nondecreasing sequence exists. Q.E.D.
LEMMA 4.3
Every infinite sequence of n -vectors over the extended nonnegative integers (the nonnegative integers plus the symbol ω ) contains an infinite nondecreasing subsequence.

Proof :
By induction on n, the dimension of the vector space.

  1. Base case ( n = 1) . If there are an infinite number of ( ω ) vectors in the sequence, then they form an infinite nondecreasing sequence. If not, then the infinite sequence formed by deleting the finite number of ( ω ) vectors has an infinite nondecreasing subsequence by Lemma 4.2.

  2. Induction hypothesis. (Assume the lemma is true for n, prove for n + 1 .) Consider the first coordinate. If there are infinitely many vectors with ω as their first coordinate, then select this infinite subsequence which is nondecreasing (constant) in the first coordinate. If there are only a finite number of vectors with a first coordinate of ω, then consider the infinite sequence of integers which are the first coordinates. By Lemma 4.2, this sequence has an infinite nondecreasing subsequence. This defines an infinite subsequence of vectors which are nondecreasing in their first coordinate.

    In either case, we have a sequence of vectors that are nondecreasing in their first coordinates. Apply the induction hypothesis on the sequence of n -vectors which result from ignoring the first component of the n + 1 -vectors. The infinite subsequence which is selected in this manner is nondecreasing in each coordinate.

Q.E.D.

Now we can prove the following theorem.

THEOREM 4.1
The reachability tree of a Petri net is finite.

Proof :
The proof is by contradiction. Assume there exists an infinite reachability tree. Then by Lemma 4.1 there is an infinite path x0, x1, x2, … from the root ( x0 ). (The number of successors for each node in the tree is limited by m, the number of transitions.) Then μ [ x0], μ [ x1], μ [ x2], … is an infinite sequence of n -vectors over N ∪ { ω } and by Lemma 4.3 has an infinite nondecreasing subsequence μ [ x i0] ≤ μ [ x i1] ≤ μ [ x i2] ≤ ⋯ . But by construction, we cannot have μ [ xi] = μ [ xj], since then one would be a duplicate node and would have no successors. Thus, we must have an infinite strictly increasing sequence μ [ x i0] < μ [ x i1] < ⋯ . But, again by construction, since μ [ xi] < μ [ xj], we would replace at least one component of μ [ xi] which is not ω by an ω in μ [ xj] . Thus, μ [ x i1] has at least one component which is ω, μ [ x i2] has at least two ω -components, and μ [ x in] has at least n ω -components. Since the markings are n -dimensional, μ [ x in] has all components ω . But then μ [ x i n + 1] cannot be greater than μ [ x in] . This is a contradiction, proving that our assumption that an infinite reachability tree existed was incorrect. Q.E.D.
The construction of the reachability tree was first described by Karp and Miller [1968]. A variant has been given by Keller [1972]. The proof of the finiteness of the tree given here is taken from Hack [1974a], who based his proof on the proof of Karp and Miller [1968].

The reachability tree is an extremely useful tool for the analysis of Petri nets. In the following sections, we show how it can be used to solve several of the problems presented in Section 4.1.

4.2.1.1. Safeness and Boundedness

A Petri net is safe if the number of tokens in each place cannot exceed one; a Petri net is bounded if there exists an integer k such that the number of tokens in any place cannot exceed k. Both of these properties can be tested using the reachability tree. A Petri net is bounded if and only if the symbol ω never appears in its reachability tree. The appearance of the symbol ω as part of a reachability tree means that the number of tokens is potentially unbounded; there exists a sequence of transition firings which can be repeated arbitrarily many times to increase the number of tokens to an arbitrary, unbounded number. Thus, if the symbol ω appears, the net is unbounded. In addition, the ω symbol indicates by its position which places are unbounded.

Conversely, if the Petri net is unbounded, then the number of reachable markings is infinite. Since the reachability tree is finite, the symbol ω must occur to represent the infinite number of reachable markings.

If the Petri net is bounded, and the ω symbol is not in the reachability tree, then the Petri net represents a finite state system. The reachability tree then is essentially a state graph and will contain a node corresponding to every reachable marking. This allows any, and all, other analysis questions to be solved by simply the exhaustive examination of the finite set of all reachable markings. For example, to determine the bound on a particular place, generate the reachability tree and scan the tree for the largest value of the component of the markings corresponding to that place. This is the bound on the number of tokens for this place. If the bound for all places is 1, then the net is safe.

Figure 4.17 demonstrates using the reachability tree to determine boundedness.



Figure 4.17. Determining boundedness for a Petri net using the reachability tree.


Notice that even for Petri nets which are not bounded (because some place is unbounded) it is possible to determine the bounds for those places which are bounded from the reachability tree. Thus the reachability tree effectively solves the analysis of Petri nets to determine boundedness or safeness for individual places or entire nets.

4.2.1.2. Conservation

A Petri net is conservative if it does not lose or gain tokens but merely moves them around. Since two tokens may be encoded as one token which later causes a transition to fire, creating two tokens, a vector of weights defines the value of a token in each place; the weights are nonnegative. A Petri net is conservative with respect to a weighting vector if the weighted sum of tokens is constant over all reachable markings.

Conservation can be effectively tested using the reachability tree. Since the reachability tree is finite, the weighted sum can be computed for each marking. If the sums are the same for each reachable marking, the net is conservative with respect to the given weight. If the sums are not equal, the net is not conservative.

The ω symbol must be carefully considered in the evaluation of conservation. If a marking has ω as the marking for place pi, then the weight of that place must be 0 for the net to be conservative. Remember that the ω symbol represents an infinite set of values. Since all weights are nonnegative, either the weight must be zero (indicating that the value of the number of tokens in this place is unimportant) or positive. If the weight is positive, then the sum will vary for two markings which differ in their ω -component. Hence, if any marking with nonzero weight is ω, the net is not conservative.

The above considerations refer to conservation with respect to a defined weighting. A Petri net is conservative if it is conservative with respect to some weight vector w, with wi > 0 . The reachability tree can be used to determine if a Petri net is conservative by finding a positive weight vector w, if one exists. To determine a positive weight vector with respect to which a Petri net is conservative, first note that the net must be bounded. As pointed out above, an unbounded place must have a weight of zero, which is not possible in a net with positive weight vector. (If we wish to allow zero components, we simply set the weights of all unbounded places to zero and consider further only the remaining components.) Now if the net is conservative, a weighted sum, call it s, and a weight vector, w = ( w1, w2, …, wn ), exist. For each marking μ [ x ] of the reachability tree we must have

w1 ⋅ μ[x]1 + w2 ⋅ μ[x]2 + ⋯ + wn ⋅ μ[x]n = s

This defines, for k nodes in the reachability tree, a set of k linear equations in n + 1 unknowns. Add to this the constraints

wi > 0, i = 1, …, n

and we have defined the constraints on the weight vector.

Solution of this system of linear equations is a well-known problem with many algorithms for solution. It can be considered a linear programming problem or simply a system of linear equations. In either case, if a solution exists, it can be computed. (The solutions from these techniques will in general be rational, not integer, but the weights can be multiplied by a common denominator to produce an integer solution.)

If the weights are overly constrained and hence no weighting vector exists, this will be determined. In either case, it can be determined whether or not the Petri net is conservative, and if so, a weight vector is produced.

4.2.1.3. Coverability

A final problem which can be solved with the aid of the reachability tree is the coverability problem. For the coverability problem, we wish to determine, for a given marking μ′, if a marking μ′′ ≥ μ′ is reachable. This problem can be solved by inspection of the reachability tree. Given an initial marking μ, we construct the reachability tree. Then we search for any node x, with μ [ x ] ≥ μ′ . If no node is found, the marking μ′ is not covered by any reachable marking; if such a node is found, μ [ x ] gives a reachable marking which covers μ′ .

The path from the root to the covering marking defines the sequence of transitions which leads from the initial marking to the covering marking, and the marking associated with that node defines the covering marking. Again, of course, the symbol ω should be treated as representing an infinite set of values. If a component of the covering marking is ω, then a “loop” will exist in the path from the root to the covering marking. It will be necessary to repeat this loop enough times to raise the corresponding components to not less than the given marking.

Note that if there are several components in the covering marking which are ω, there may be an interaction between the marking changes which result from the loops. Consider the Petri net of Figure 4.18 and its reachability tree given in Figure 4.19. According to the analysis given, the marking (0, 14, 1, 7) is covered in the reachability set. The path to generate a covering marking consists of some number of t1 followed by t2 followed by some number of t3. The problem is to determine how many t1 and t3. Since we want 14 tokens in p2 and t1 puts a token in p2, we might try 14 t1. However, we need 7 t3, and each t3 removes a token from p2, so we actually need at least 21 t1, then t2, and then at least 7 t3 (but not so many t3 as to empty p2 too much). Karp and Miller [1968] give an algorithm which will determine the minimal number of transition firings needed to cover a given marking.



Figure 4.18. A Petri net with the reachability tree of Figure 4.19.





Figure 4.19. The reachability tree of the Petri net of Figure 4.18.


4.2.1.4. Limitations of the Reachability Tree

As we have seen, the reachability tree can be used to solve the safeness, boundedness, conservation and coverability problems. Unfortunately, it cannot, in general, be used to solve the reachability or liveness problems or to define or determine which firing sequences are possible. These problems are limited by the existence of the ω symbol. The ω symbol is a loss of information; the individual numbers are discarded, with only the existence of the large number of them being remembered.

Consider, for example, the Petri nets of Figures 4.20 and 4.21 whose reachability tree is given in Figure 4.22. The same reachability tree represents these two similar (but different) Petri nets. The reachability sets are not the same, however. In the Petri net of Figure 4.20, the number of tokens in place p2 is always an even number (until t1 fires), whereas in Figure 4.21 it may be an arbitrary integer. The ω symbol does not allow this kind of information to be detected, preventing the use of the reachability tree to solve the reachability problem.



Figure 4.20. A Petri net whose reachability tree is shown in Figure 4.22.





Figure 4.21. A second Petri net whose reachability tree is shown in Figure 4.22. The Petri net of Figure 4.20 whose reachability tree is in Figure 4.22 has only even numbers of tokens in place p2 while this Petri net has an arbitrary integer marking for place p2.





Figure 4.22. The reachability tree of the Petri nets of Figures 4.21 and 4.20.


A similar problem exists for the liveness problem. Figures 4.23 and 4.24 are two Petri nets whose reachability tree is given in Figure 4.25. However, the net in Figure 4.23 can deadlock (the sequence t1 t2 t3, for example), while the net in Figure 4.24 cannot. Again, however, the reachability tree cannot distinguish between these two cases.



Figure 4.23. A Petri net with a possible deadlock.





Figure 4.24. A Petri net which cannot deadlock. This net is live, yet its reachability tree (Figure 4.25) is identical to the reachability tree of the nonlive Petri net of Figure 4.23.





Figure 4.25. The reachability tree of the Petri nets of Figures 4.23 and 4.24.


Note that although the reachability tree does not necessarily contain enough information to always solve the reachability or liveness problems, it is the case that the tree may have sufficient information to solve many such problems. A net whose reachability tree has a terminal node (one with no successors) is not live (since some reachable marking has no successors). Similarly, a marking μ′ of a reachability problem may appear in the reachability tree, and if so, it is reachable. Also, if a marking is not covered by some node of the reachability tree, then it is not reachable.

These conditions are sufficient to solve some reachability and liveness problems, but they do not solve these problems in general. Thus, to solve these two problems, other approaches are needed.

Exercises

  1. Construct the reachability trees for the marked Petri nets of Figures 4.1 and 4.2.

  2. Write a computer program to construct the reachability tree from a Petri net description and an initial marking.

  3. Most statements of the algorithm for constructing the reachability tree allow a node to be classified as a duplicate node only if the first node occurs on the path from the root to the duplicate node. Thus nodes in separate subtrees which represent the same markings continue to be processed by the algorithm. This change increases the size of the subtree, but it will not affect the (eventual) termination of the algorithm. Prove that the algorithm will terminate even if duplicate markings must be in the same subtree as the first marking, and prove that allowing duplicate markings to be in separate subtrees will not result in any reachable markings being missed from the tree.

4.2.2. Matrix Equations

A second approach to the analysis of Petri nets is based on a matrix view of Petri nets. An alternative to the (P, T, I, O) definition of Petri nets is to define two matrices D and D+ to represent the input and output functions. (These are equivalent to the F and B functions of Hack's Petri net definition; see Section 2.6.) Each matrix is m rows (one for each transition) by n columns (one for each place). We define D [ j, i ] = # ( pi, I ( tj )) and D+ [ j, i ] = # ( pi, O ( tj )) . D defines the inputs to the transitions and, D+ defines the outputs.

The matrix definitional form of a Petri net (P, T, D, D+ ) is equivalent to the standard form we have used but allows the definitions to be recast in vector and matrix terms. Let e [ j ] be the unit m -vector which is zero everywhere except in the j th component. The transition tj is represented by the unit m -vector e [ j ] .

Now a transition tj is enabled in a marking μ if

μ ≥ e[j] ⋅ D

and the result of firing transition tj in marking μ, if it is enabled, is

δ(μ, tj) = μ − e[j] ⋅ D + e[j] ⋅ D+
= μ + e[j] ⋅(−D + D+)
= μ + e[j] ⋅ D

where we have defined the composite change matrix D = D+D.

Now for a sequence of transition firings σ = tj1 tj2... tjk, we have

δ(μ, σ) = δ(μ, tj1 tj2... tjk)
= μ + e[j1] ⋅ D + e[j2] ⋅ D + ⋯ + e[jk] ⋅ D
= μ + (e[j1] + e[j2] + ⋯ + e[jk]) ⋅ D
= μ + f(σ) ⋅ D

The vector f ( σ ) = e [ j1] + e [ j2] + ⋯ + e [ jk] is called the firing vector of the sequence tj1 tj2... tjk. The i th element of f ( σ ), f ( σ )i, is the number of times that transition ti fires in the sequence tj1 tj2... tjk. The firing vector is thus a vector of nonnegative integers. (The vector f ( σ ) is the Parikh mapping of the sequence σ [Parikh 1966]).

To show an example of the usefulness of this matrix approach to Petri nets, consider the conservation problem: Given a marked Petri net, is it conservative? To show conservation, it is necessary to find a (nonzero) weighting vector for which the weighted sum over all reachable markings is constant. Let w be an n ⨯ 1 column vector. Then if μ is the initial marking and μ′ is an arbitrary reachable marking, we need

μ ⋅ w = μ′ ⋅ w

Now since μ′ is reachable, there exists a sequence σ of transition firings which takes the net from μ to μ′ . So,

μ′ = δ(μ, σ)
= μ + f(σ) ⋅ D

Thus,

μ ⋅ w = μ′ ⋅ w
= (μ + f(σ) ⋅ D) ⋅ w
= μ ⋅ w + f(σ) ⋅ Dw

and so

f(σ) ⋅ Dw = 0

Since this must be true for all f ( σ ), we must have

Dw = 0

Thus a Petri net is conservative if and only if there exists a positive vector w such that Dw = 0 . This provides a simple test for conservation and also produces the weighting vector, w.

The development of this matrix Petri net theory provides a useful tool for attacking the reachability problem. Assume that a marking μ′ is reachable from a marking μ . Then there exists a sequence σ (possibly null) of transition firings which will lead from μ to μ′ . This means that f ( σ ) is a solution, in nonnegative integers, for x in the following matrix equation.

μ′ = μ + xD

Thus, if μ′ is reachable from μ, then Equation (4.1) has a solution in nonnegative integers; if Equation (4.1) has no solution, then μ′ is not reachable from μ .


Figure 4.26. A Petri net for illustrating matrix equation analysis.


As an example, consider the marked Petri net of Figure 4.26. The matrices D and D+ are

D- = &leftbigbracket;
1 1 1 0
0 0 0 1
0 0 1 0
&rightbigbracket;
D+ = &leftbigbracket;
1 0 0 0
0 2 1 0
0 0 0 1
&rightbigbracket;

and the D matrix is

D = &leftbigbracket;
0 -1 -1 0
0 +2 +1 -1
0 0 -1 +1
&rightbigbracket;

With an initial marking μ = (1, 0, 1, 0), transition t3 is enabled and leads to marking μ′, where

μ′ = (1, 0, 1, 0) + (0, 0, 1) ⋅ &leftbigbracket;
0 -1 -1 0
0 +2 +1 -1
0 0 -1 +1
&rightbigbracket;
= (1, 0, 1, 0) + (0, 0, −1, +1)
= (1, 0, 0, 1)

The sequence σ = t3 t2 t3 t2 t1 is represented by the firing vector f ( σ ) = (1, 2, 2) and produces the marking μ′,

μ′ = (1, 0, 1, 0) + (1, 2, 2) ⋅ &leftbigbracket;
0 -1 -1 0
0 +2 +1 -1
0 0 -1 +1
&rightbigbracket;
= (1, 0, 1, 0) + (0, 3, −1, 0)
= (1, 3, 0, 0)

To determine if the marking (1, 8, 0, 1) is reachable from the marking (1, 0, 1, 0), we have the equation

(1, 8, 0, 1) = (1, 0, 1, 0) + x ⋅ &leftbigbracket;
0 -1 -1 0
0 +2 +1 -1
0 0 -1 +1
&rightbigbracket;
(0, 8, -1, 1) = x ⋅ &leftbigbracket;
0 -1 -1 0
0 +2 +1 -1
0 0 -1 +1
&rightbigbracket;

which has a solution x = (0, 4, 5) . This corresponds to the sequence σ = t3 t2 t3 t2 t3 t2 t3 t3.

We can further show that marking (1, 7, 0, 1) is not reachable from the marking (1, 0, 1, 0), since the matrix equation

(1, 7, 0, 1) = (1, 0, 1, 0) + x ⋅ &leftbigbracket;
0 -1 -1 0
0 +2 +1 -1
0 0 -1 +1
&rightbigbracket;
(0, 7, -1, 1) = x ⋅ &leftbigbracket;
0 -1 -1 0
0 +2 +1 -1
0 0 -1 +1
&rightbigbracket;

has no solution.

The matrix approach to the analysis of Petri nets has great promise but also has some severe problems. First notice that the matrix D by itself does not properly reflect the structure of the Petri net. Transitions which have both inputs and outputs from the same place (self-loops) will be represented in the same position of the D and D+ matrices and so will cancel out in the D = D+D matrix. This was reflected in the previous example by place p1 and transition t1.



Figure 4.27. Another Petri net for matrix analysis.


Another problem is the lack of sequencing information in the firing vector. Consider the Petri net of Figure 4.27. Assume we wish to determine if the marking (0, 0, 0, 0, 1) is reachable from (1, 0, 0, 0, 0). Then one equation is

(0, 0, 0, 0, 1) = (1, 0, 0, 0, 0, 0) + x ⋅ &leftbigbracket;
-1 2 1 0 0
0 0 0 0 0
0 0 1 0 0
0 -1 0 1 0
0 2 0 0 -1
0 0 -1 -1 1
&rightbigbracket;

This equation does not have a unique solution but reduces to the set of solutions { σ | f ( σ ) = (1, x2, x6 − 1, 2 x6, x6 − 1, x6 ) } . This defines the relationships between the firings of the transitions. If we let x6 = 1 and x2 = 1, we have f ( σ ) = (1, 1, 0, 2, 0, 1), but both the sequence t1 t2 t4 t4 t6 and the sequence t1 t4 t2 t4 t6 correspond to this firing vector. Thus, although we know the number of transition firings, we do not know the order of transition firings.


Figure 4.28. A Petri net showing that a solution to the matrix equation is a necessary but not a sufficient condition for reachability.


Another problem is that although a solution to Equation (4.1) is necessary for reachability, it is not sufficient. Consider the simple Petri net of Figure 4.28. If we wish to determine if (0, 0, 0, 1) is reachable from (1, 0, 0, 0) we must solve the equation

(0, 0, 0, 1) = (1, 0, 0, 0) + f(σ) ⋅ &leftbigbracket;
-1 +1 -1 0
0 -1 +1 +1
&rightbigbracket;

This equation has the solution f ( σ ) = (1, 1), corresponding to the two sequences t1 t2 or t2 t1. But neither of these two transition sequences are possible, since neither t1 nor t2 is enabled in (1, 0, 0, 0). Thus a solution to Equation (4.1) is not sufficient to prove reachability.

The possibility of spurious solutions to Equation (4.1) -- solutions which do not correspond to possible transition sequences -- has resulted in only limited research on the matrix representation of Petri nets. The best research on this approach has been by Murata [1975; 1977a; 1977b].

4.3. Further Reading

Holt et al. [1968] and Holt and Commoner [1970] defined some of the early analysis problems for Petri nets -- liveness and safeness -- and these have continued as major problems for analysis. Liveness has been studied by Commoner [1972], Lautenbach [1975], and Lien [1976a]. Keller [1972] also considered liveness plus other problems. Lien [1976a] defined the conservation problem.

Karp and Miller [1968] first described the reachability tree construction and proved that it was finite. The coverability and reachability problems were defined by them, as were the equivalence and containment problems. These later problems were the subject of [Baker 1973b], while [Nash 1973] is a brief statement of the reachability problem. Hack [1974a] brings most of these problems together in one place and shows how the reachability tree can be used for some of them.

The matrix approach was considered by Peterson [1973] but was found to be of limited usefulness. Murata, with a better background in linear algebra, has done quite a bit more with this approach in [Murata and Church 1975; Murata 1975; Murata et al. 1975; Murata 1977a; Murata 1977b].

4.4. Topics for Further Study

  1. Consider constructing a reachability graph rather than a tree. If a node x produces a successor z with μ [ z ] = μ [ y ] for some nonfrontier node y, simply create an arc, labeled appropriately, from x to y. Note that a path from the root to a node need no longer be unique. Define the algorithm to construct the reachability graph, show that it terminates, and investigate its properties relative to the reachability tree.

  2. The reachability tree cannot be used to solve the reachability problem because of the loss of information which results from the ω symbol. The ω symbol is introduced when we come to a marking μ′ with a marking μ on the path from the root to μ′, with μ′ > μ . In this case, we can reach all markings of the form μ + n ( μ′ − μ ) . Investigate the possibility of using an expression a + bni rather than ω to represent the value of the components. If you can define a reachability tree where all marking vectors are represented by expressions, then the reachability problem is simply the solution of a set of equations.

  3. Extend the definition of conservation to allow negative weights. What would be a reasonable interpretation of a negative weight? Is it decidable if a Petri net is conservative if negative weights are allowed?

  4. Use the matrix analysis approach to develop an algorithm for determining boundedness of a Petri net. (See [Crespi-Reghizzi and Mandrioli 1974].)

  5. The major problem with matrix analysis is the lack of sequencing information and the existence of spurious solutions. However, the reachability problem is the most important problem for Petri nets, and it is important to show that this problem is decidable, even if the solutions are computationally expensive. If the problem is decidable, then we can search for more efficient solution techniques, but we first need to show that a solution technique exists.

    With this motivation, let Σf be the sum over all components of a firing vector f. That is, if f = ( f1, f2, …, fm ), then Σf = f1 + f2 + ⋯ + fm. Now consider that if a sequence σ exists which will take a Petri net from a marking μ to a marking μ′, then Equation (4.1) has a solution which is the firing vector f ( σ ) for σ . The sequence σ can be determined from the firing vector f ( σ ) by simply enumerating all possible sequences of length equal to Σ f ( σ ) and trying each to determine if it (1) is legal and (2) leads from μ to μ′ . For a Petri net with m transitions, there are at most m Σf possible sequences of length Σf. This can, in fact, be reduced further. Since we know how many times transition t1 fires ( f1 ), how many times t2 fires ( f2 ), and so on, we need examine no more than the Σf ! possible orderings of f1 firings of t1, f2 firings of t2, and so on.

    This would seem to provide a decision procedure for determining if μ′ is reachable from μ . First solve the matrix equation μ′ = μ + fD. If there is no solution, μ′ is not reachable from μ . If a solution f exists, then examine all Σf ! possible orderings of the transitions. If any of these transition sequences is legal, then μ′ is reachable from μ, and we have the sequence of transitions which takes us from μ to μ′ .

    There is only one hitch. The solution f may not be unique but may be a (infinite) set of firing vectors represented by a set of expressions (as illustrated above for the analysis of Figure 4.27). Research is needed to determine if it can be shown that it is possible to determine reachability in this case. In the easiest case, it may be that either all solutions represented by an expression firing vector correspond to legal solutions, or none of the solutions do. In this case, we merely pick any solution and follow the above procedure of checking all possible orderings. More likely, however, some solutions may work while others fail. Since we cannot try all solutions (possibly infinite number), research must be done to determine which solutions should be tried.

Home   Comments?