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?

Section 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  p sub {i} \(mo P of a Petri net  C = (P, T, I, O) with initial marking  mu is safe if for all  mu prime \(mo R ( C , mu ), mu prime ( p sub {i} ) <= 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  p sub {i} which is to be forced to be safe is supplemented by another place  p sub {i} prime . Transitions which use  p sub {i} as an input or output are modified as follows:


The object of this new place  p sub {i} prime is to represent the condition `` p sub {i} is empty.'' Thus  p sub {i} and  p sub {i} prime are complementary;  p sub {i} has a token only if  p sub {i} prime has no token and vice versa. Any transition which removes a token from  p sub {i} must deposit one in  p sub {i} prime , and any transition which removes a token from  p sub {i} prime must deposit one in  p sub {i} . The initial marking must also be modified to provide exactly one token in either  p sub {i} or  p sub {i} prime . (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  p sub {i} \(mo P of a Petri net  C = (P, T, I, O) with an initial marking  mu is k-safe if for all  mu prime \(mo R ( C , mu ), mu prime ( p sub {i} ) <= 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  p sub {1} may be 3-safe while place  p sub {2} is 8-safe). However, if a place  p sub {i} is  k -safe, then it is also  k prime -safe for all  k prime >= 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  mu is strictly conservative if for all  mu prime \(mo R ( C , mu ) ,


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 ( t sub {j} ) | = | O ( t sub {j} ) | . If this were not the case, firing transition  t sub {j} 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  t sub {1} or  t sub {3} will decrease the number of tokens by one, while firing transition  t sub {2} or  t sub {4} 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 = ( w sub {1}, w sub {2}, ..., w sub {n} ) defines a weight  w sub {i} for each place  p sub {i} \(mo P .

DEFINITION 4.4
A Petri net  C = (P, T, I, O) with initial marking  mu , is conservative with respect to a weighting vector  w ,  w = ( w sub {1}, w sub {2}, ..., w sub {n} ) ,  n = | P | ,  w sub {i} >= 0 , if for all  mu prime \(mo R ( C , mu ) ,


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,  w sub {i} > 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  p sub {4} ] and r [modeled by  p sub {5} ]).


The initial marking indicates resources  q ( p sub {4} ) and  r ( p sub {5} ) are available and processes  a and  b are ready. One execution of this net is  t sub {1} t sub {2} t sub {3} t sub {4} t sub {5} t sub {6} ; another is  t sub {4} t sub {5} t sub {6} t sub {1} t sub {2} t sub {3} . Neither of these executions results in deadlock. However, consider the sequence which starts  t sub {1} t sub {4} : 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  t sub {2} and  t sub {5} 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  t sub {j} of a Petri net  C is potentially fireable in a marking  mu if there exists a marking  mu prime \(mo R ( C , mu ) and  t sub {j} is enabled in  mu prime . A transition is live in a marking  mu if it is potentially fireable in every marking in  R ( C , mu ) . 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  mu 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  t sub {0} can never fire; it is dead. Transition  t sub {1} can fire exactly once; it is live at level 1. Transition  t sub {2} can be made to fire an arbitrary number of times, but the number of times is dependent on the number of times that  t sub {3} fires. If we want to fire  t sub {2} five times, we fire  t sub {3} five times, then  t sub {1} , and then  t sub {2} five times. However, once  t sub {1} fires (and  t sub {1} must fire before  t sub {2} can fire), the number of times  t sub {2} can fire is fixed. Thus,  t sub {2} is live at level 2, but not at level 3. Transition  t sub {3} , 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  t sub {1} fires  t sub {3} , 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  mu and a marking  mu prime , is  mu prime \(mo R ( C , mu ) ?

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  p sub {4} and  p sub {9} are expected to be mutually exclusive. We wish to know if any state is reachable with  p sub {4} = 1 and  p sub {9} = 1 . This problem is similar to reachability but is slightly different; it is called the coverability problem. A marking  mu prime prime covers a marking  mu prime if  mu prime prime >= mu prime .

DEFINITION 4.6 The Coverability Problem
Given a Petri net  C with initial marking  mu and a marking  mu prime , is there a reachable marking  mu prime prime \(mo R ( C , mu ) such that  mu prime prime >= mu prime ?


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  p sub {4} and  p sub {9} ; 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  t sub {j} 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  t sub {3} t sub {9} can occur, or if  t sub {4} t sub {10} can occur, or, more generally, if  t sub {3} sigma t sub {9} can occur, where  sigma is any sequence of firings not including  t sub {4} . 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.

Section 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:  t sub {1} and  t sub {2} . 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  t sub {1} [giving (1, 2, 0)] and  t sub {2} [giving (0, 2, 1)]; from (0, 1, 1) we can fire  t sub {3} [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  t sub {3} in (0, 2, 1) is (0, 1, 1); the marking (0, 1, 1) was also produced directly from the initial marking by firing  t sub {2} .


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  t sub {1} t sub {2} t sub {3} does not produce any further nodes in the tree, since it occurred earlier in the tree as a result of the sequence  t sub {2} from the initial marking.

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

We represent the infinite number of markings which result from these types of loops by using a special symbol,  omega , 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





These are the only operations on  omega 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  mu [ i ] ; the marking is extended to allow the number of tokens in a place to be either a nonnegative integer or the  omega 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,  mu [ x ] = mu [ y ] , then node  x is a duplicate node.

  2. If no transitions are enabled for the marking  mu [ x ] , [i.e.,  delta ( mu [ x ], t sub {j} ) is undefined for all  t sub {j} \(mo T ], then  x is a terminal node.

  3. For all transitions  t sub {j} \(mo T which are enabled in  mu [ x ] , [i.e.,  delta ( mu [ x ], t sub {j} ) is defined], create a new node  z in the reachability tree. The marking  mu [ z ] associated with this new node is, for each place  p sub {i} ,

    1. If  mu [ x ] sub {i} = omega , then  mu [ z ] sub {i} = omega .

    2. If there exists a node  y on the path from the root node to  x with  mu [ y ] < delta ( mu [ x ], t sub {j} ) and  mu [ y ] sub {i} < delta ( mu [ x ], t sub {j} ) sub {i} , then  mu [ z ] sub {i} = omega .

    3. Otherwise,  mu [ z ] sub {i} = delta ( mu [ x ], t sub {j} ) sub {i} .

    An arc, labeled  t sub {j} , 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  x sub {0} . Since there are only a finite number of direct successors to  x sub {0} , but the total number of nodes in the tree is infinite, at least one of the direct successors of  x sub {0} must be the root of an infinite subtree. (If all the subtrees of direct successors of  x sub {0} were finite, then the tree of  x sub {0} would be finite.) Pick a node  x sub {1} which is a direct successor of  x sub {0} with an infinite subtree. Now one of its direct successors is also the root of an infinite subtree; pick  x sub {2} to be such a direct successor. Continuing in this manner, we produce the infinite path  x sub {0}, x sub {1}, x sub {2} , ... 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  x sub {0} be such an element. The infinite subsequence,  x sub {0}, x sub {0}, x sub {0}, ... is an infinite nondecreasing subsequence.

  2. If no element occurs infinitely often, then each element occurs only a finite number of times. Let  x sub {0} be an arbitrary element of the sequence. There are at most  x sub {0} integers which are nonnegative and less than  x sub {0} [ 0, ..., x sub {0} - 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  x sub {1} with  x sub {1} >= x sub {0} . Similarly, there must exist an  x sub {2} farther on in the sequence with  x sub {2} >= x sub {1} , and so on. This defines an infinite nondecreasing subsequence,  x sub {0}, x sub {1}, x sub {2}, ... .

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  omega ) 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  ( omega ) vectors in the sequence, then they form an infinite nondecreasing sequence. If not, then the infinite sequence formed by deleting the finite number of  ( omega ) 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  omega 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  omega , 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  x sub {0}, x sub {1}, x sub {2}, ... from the root ( x sub {0} ). (The number of successors for each node in the tree is limited by  m , the number of transitions.) Then  mu [ x sub {0}], mu [ x sub {1}], mu [ x sub {2}], ... is an infinite sequence of  n -vectors over  N union { omega } and by Lemma 4.3 has an infinite nondecreasing subsequence  mu [ x sub { i sub {0}}] <=   mu [ x sub { i sub {1}}] <=   mu [ x sub { i sub {2}}] <= ... . But by construction, we cannot have  mu [ x sub {i}] = mu [ x sub {j}] , since then one would be a duplicate node and would have no successors. Thus, we must have an infinite strictly increasing sequence  mu [ x sub { i sub {0}}] < mu [ x sub { i sub {1}}] < ... . But, again by construction, since  mu [ x sub {i}] < mu [ x sub {j}] , we would replace at least one component of  mu [ x sub {i}] which is not  omega by an  omega in  mu [ x sub {j}] . Thus,  mu [ x sub { i sub {1}}] has at least one component which is  omega , mu [ x sub { i sub {2}}] has at least two  omega -components, and  mu [ x sub { i sub {n}}] has at least  n  omega -components. Since the markings are  n -dimensional,  mu [ x sub { i sub {n}}] has all components  omega . But then  mu [ x sub { i sub { n + 1}}] cannot be greater than  mu [ x sub { i sub {n}}] . 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  omega never appears in its reachability tree. The appearance of the symbol  omega 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  omega appears, the net is unbounded. In addition, the  omega 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  omega must occur to represent the infinite number of reachable markings.

If the Petri net is bounded, and the  omega 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  omega symbol must be carefully considered in the evaluation of conservation. If a marking has  omega as the marking for place  p sub {i} , then the weight of that place must be 0 for the net to be conservative. Remember that the  omega 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  omega -component. Hence, if any marking with nonzero weight is  omega , 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  w sub {i} > 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 = ( w sub {1}, w sub {2}, ..., w sub {n} ) , exist. For each marking  mu [ x ] of the reachability tree we must have


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


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  mu prime , if a marking  mu prime prime >= mu prime is reachable. This problem can be solved by inspection of the reachability tree. Given an initial marking  mu , we construct the reachability tree. Then we search for any node  x , with  mu [ x ] >= mu prime . If no node is found, the marking  mu prime is not covered by any reachable marking; if such a node is found,  mu [ x ] gives a reachable marking which covers  mu prime .

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  omega should be treated as representing an infinite set of values. If a component of the covering marking is  omega , 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  omega , 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  t sub {1} followed by  t sub {2} followed by some number of  t sub {3} . The problem is to determine how many  t sub {1} and  t sub {3} . Since we want 14 tokens in  p sub {2} and  t sub {1} puts a token in  p sub {2} , we might try  14 t sub {1} . However, we need  7 t sub {3} , and each  t sub {3} removes a token from  p sub {2} , so we actually need at least  21 t sub {1} , then  t sub {2} , and then at least  7 t sub {3} (but not so many  t sub {3} as to empty  p sub {2} 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  omega symbol. The  omega 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  p sub {2} is always an even number (until  t sub {1} fires), whereas in Figure 4.21 it may be an arbitrary integer. The  omega 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  p sub {2} while this Petri net has an arbitrary integer marking for place  p sub {2} .




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  t sub {1} t sub {2} t sub {3} , 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  mu prime 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 sup {-} and  D sup {+} 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 sup {-} [ j , i ] = # ( p sub {i}, I ( t sub {j} )) and  D sup {+} [ j , i ] = # ( p sub {i}, O ( t sub {j} )) .  D sup {-} defines the inputs to the transitions and,  D sup {+} defines the outputs.

The matrix definitional form of a Petri net  (P, T, D sup {-}, D sup {+} ) 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  t sub {j} is represented by the unit  m -vector  e [ j ] .

Now a transition  t sub {j} is enabled in a marking  mu if


and the result of firing transition  t sub {j} in marking  mu , if it is enabled, is




where we have defined the composite change matrix  D = D sup {+} - D sup {-} .

Now for a sequence of transition firings  sigma = t sub {j sub {1}} t sub {j sub {2}} ... t sub {j sub {k}} , we have





The vector  f ( sigma ) = e [ j sub {1}] + e [ j sub {2}] + ... + e [ j sub {k}] is called the firing vector of the sequence  t sub {j sub {1}} t sub {j sub {2}} ... t sub {j sub {k}} . The  i th element of  f ( sigma ) ,  f ( sigma ) sub {i} , is the number of times that transition  t sub {i} fires in the sequence  t sub {j sub {1}} t sub {j sub {2}} ... t sub {j sub {k}} . The firing vector is thus a vector of nonnegative integers. (The vector  f ( sigma ) is the Parikh mapping of the sequence  sigma [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 times 1 column vector. Then if  mu is the initial marking and  mu prime is an arbitrary reachable marking, we need


Now since  mu prime is reachable, there exists a sequence  sigma of transition firings which takes the net from  mu to  mu prime . So,



Thus,




and so


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


Thus a Petri net is conservative if and only if there exists a positive vector  w such that  D cdot w = 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  mu prime is reachable from a marking  mu . Then there exists a sequence  sigma (possibly null) of transition firings which will lead from  mu to  mu prime . This means that  f ( sigma ) is a solution, in nonnegative integers, for  x in the following matrix equation.


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

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 sup {-} and  D sup {+} are



and the  D matrix is


With an initial marking  mu = (1, 0, 1, 0) , transition  t sub {3} is enabled and leads to marking  mu prime , where




The sequence  sigma = t sub {3} t sub {2} t sub {3} t sub {2} t sub {1} is represented by the firing vector  f ( sigma ) = (1, 2, 2) and produces the marking  mu prime ,




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



which has a solution  x = (0, 4, 5) . This corresponds to the sequence  sigma = t sub {3} t sub {2} t sub {3} t sub {2} t sub {3} t sub {2} t sub {3} t sub {3} .

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



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 sup {-} and  D sup {+} matrices and so will cancel out in the  D = D sup {+} - D sup {-} matrix. This was reflected in the previous example by place  p sub {1} and transition  t sub {1} .


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


This equation does not have a unique solution but reduces to the set of solutions  { sigma | f ( sigma ) = (1, x sub {2}, x sub {6} - 1, 2 x sub {6}, x sub {6} - 1, x sub {6} ) } . This defines the relationships between the firings of the transitions. If we let  x sub {6} = 1 and  x sub {2} = 1 , we have  f ( sigma ) = (1, 1, 0, 2, 0, 1) , but both the sequence  t sub {1} t sub {2} t sub {4} t sub {4} t sub {6} and the sequence  t sub {1} t sub {4} t sub {2} t sub {4} t sub {6} 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


This equation has the solution  f ( sigma ) = (1, 1) , corresponding to the two sequences  t sub {1} t sub {2} or  t sub {2} t sub {1} . But neither of these two transition sequences are possible, since neither  t sub {1} nor  t sub {2} 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].

Section 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].

Section 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  mu [ z ] = mu [ 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  omega symbol. The  omega symbol is introduced when we come to a marking  mu prime with a marking  mu on the path from the root to  mu prime , with  mu prime > mu . In this case, we can reach all markings of the form  mu + n ( mu prime - mu ) . Investigate the possibility of using an expression  a + b cdot n sub {i} rather than  omega 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  SIGMA sub {f} be the sum over all components of a firing vector  f . That is, if  f = ( f sub {1}, f sub {2}, ..., f sub {m} ) , then  SIGMA sub {f} = f sub {1} + f sub {2} + ... + f sub {m} . Now consider that if a sequence  sigma exists which will take a Petri net from a marking  mu to a marking  mu prime , then Equation (4.1) has a solution which is the firing vector  f ( sigma ) for  sigma . The sequence  sigma can be determined from the firing vector  f ( sigma ) by simply enumerating all possible sequences of length equal to  SIGMA sub { f ( sigma ) } and trying each to determine if it (1) is legal and (2) leads from  mu to  mu prime . For a Petri net with  m transitions, there are at most  m sup { SIGMA sub {f} } possible sequences of length  SIGMA sub {f} . This can, in fact, be reduced further. Since we know how many times transition  t sub {1} fires  ( f sub {1} ) , how many times  t sub {2} fires  ( f sub {2} ) , and so on, we need examine no more than the  SIGMA sub {f} ! possible orderings of  f sub {1} firings of  t sub {1} ,  f sub {2} firings of  t sub {2} , and so on.

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

    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?