Home Up Questions?

Chapter 5. Complexity and Decidability

In Chapter 4 we presented a number of problems which have been defined for Petri nets. These problems concern various properties of Petri net structure and behavior which, under appropriate circumstances, would be of interest to users of Petri nets.

Two solution techniques were also presented: the reachability tree and matrix equation approaches. These two techniques allow properties of safeness, boundedness, conservation, and coverability to be determined for Petri nets. Also, a necessary condition for reachability was established. However, these analysis techniques are not sufficient to solve several other problems, especially liveness, reachability, and equivalence. In this chapter we explore these problems, either to find solutions to them or at least to learn more about the properties of Petri nets.

Section 5.1. Reducibility Between Analysis Problems

A fundamental concept which we use is reducibility [Karp 1972]. Solving a problem involves reducing it to another problem which we already know how to solve. For example, in the previous chapter, the problem of determining if a Petri net is conservative was reduced to solving a set of simultaneous linear equations. The problem of solving sets of simultaneous linear equations has in turn been reduced to a defined sequence of arithmetic operations (addition, subtraction, multiplication, division, and comparisons). Thus, since the simpler arithmetic operations can be computed, conservation can be determined.

Another example concerns the equality problem and subset problem for reachability sets.

DEFINITION 5.1 Equality Problem
Given two marked Petri nets  C sub {1} = (P sub {1}, T sub {1}, I sub {1}, O sub {1} ) with marking  mu sub {1} and  C sub {2} = (P sub {2}, T sub {2}, I sub {2}, O sub {2} ) with marking  mu sub {2} , is  R ( C sub {1}, mu sub {1} ) = R ( C sub {2}, mu sub {2} ) ?
DEFINITION 5.2 Subset Problem
Given two marked Petri nets  C sub {1} = (P sub {1}, T sub {1}, I sub {1}, O sub {1} ) with marking  mu sub {1} and  C sub {2} = (P sub {2}, T sub {2}, I sub {2}, O sub {2} ) with marking  mu sub {2} , is  R ( C sub {1}, mu sub {1} ) \(ib R ( C sub {2}, mu sub {2} ) ?
These two problems can be very important if Petri nets are to be ``optimized'' or if the nets of two systems are to be compared. However, notice that if a solution to the subset problem can be found, the equality problem is also solved. If we wish to determine if  R ( C sub {1}, mu sub {1} ) = R ( C sub {2}, mu sub {2} ) , we can first use the subset problem algorithm to determine if  R ( C sub {1}, mu sub {1} ) \(ib R ( C sub {2}, mu sub {2} ) , and then use the same algorithm to determine if  R ( C sub {2}, mu sub {2} ) \(ib R ( C sub {1}, mu sub {1} ) .  R ( C sub {1}, mu sub {1} ) = R ( C sub {1}, mu sub {2} ) if and only if  R ( C sub {1}, mu sub {1} ) \(ib R ( C sub {2}, mu sub {2} ) and  R ( C sub {2}, mu sub {2} ) \(ib R ( C sub {1}, mu sub {1} ) . Thus, we can reduce the equality problem to the subset problem.

Two other considerations are of importance when considering analysis problems and reducibility. First, in trying to find a solution, we must consider the possibility that a problem has no solution technique; it is undecidable. Second, if a solution technique exists, we need to consider its cost: How much time and memory space are needed? For Petri nets to gain widespread general use, analysis problems must be solvable and by algorithms which are not excessively expensive in computer time or space.

Reducibility plays a role in both of these problems. Reducibility between problems is commonly used to show that a problem is decidable or undecidable. Our approach to decidability theory [Davis 1958; Minsky 1967] is based mainly on the work of Turing and on his model of computations, the Turing machine. The importance of the Turing machine is that it is a reasonable representation of a limited computing machine and that it can be shown that no algorithm exists which can solve certain Turing machine problems, especially the halting problem. From this basis, a collection of undecidable problems has been found. The importance of this theory is that it is not possible to produce a computer program which solves these problems. Thus, for practical analysis, these undecidable problems must be avoided, or the analysis questions will be unanswerable.

(An important distinction here is that undecidable problems produce questions which are not simply unanswered but unanswerable. Questions can be unanswered but still answerable; this merely means that no one has yet found an answer but that the answer does exist. A famous example is Fermat's last theorem: Does the equation  x sup {n} + y sup {n} = z sup {n} have solutions for  n > 2 and nontrivial integer  x ,  y , and  z ? This question has not been answered, but it is answerable. The answer is either yes or no. One way to answer the question is to produce numbers  x ,  y ,  z , and  n which satisfy the theorem. The other way would be to prove (logically deduce) that no such  x ,  y ,  z , and  n can exist. No one has yet done so.

However, assume that the problem were undecidable. Then it is not possible to decide whether  x ,  y ,  z , and  n exist which solve the equation. This means we could not logically deduce their nonexistence from the axioms of mathematics and that we cannot produce  x ,  y ,  z , and  n which solve the equation. But if we cannot produce  x ,  y ,  z , and  n , then they must not exist. If they did exist, we could set a computer to searching for them, and, eventually, it would find them. But if  x ,  y ,  z , and  n do not exist, then the answer to the question is no, and we have decided it. This contradicts our assumption that the question is undecidable, so the question is decidable.)

Now assume that a problem  A is reducible to a problem  B : An instance of problem  A can be transformed into an instance of problem  B . If problem  B is decidable, then problem  A is decidable, and the algorithm for problem  B can be used to solve problem  A . An instance of problem  A can be solved by transforming it to an instance of problem  B and applying the algorithm for problem  B to determine the solution. Thus, if problem  A is reducible to problem  B and problem  B is decidable, then problem  A is decidable.

The contrapositive is also true: If problem  A is reducible to problem  B and problem  A is undecidable, then problem  B is undecidable; for if problem  B were decidable, the above procedure is a decision technique for problem  A , contradicting its undecidability. These two facts are central to most decidability techniques. To show that a problem is decidable, reduce it to a problem which is known to be decidable; to show that a problem is undecidable, reduce a problem which is known to be undecidable to it.

We shall make good use of this approach to reduce the amount of work we must do. For example, since the equality problem for reachability sets is reducible to the subset problem, we want to develop either (1) a solution procedure for the subset problem or (2) a proof that the equality problem is undecidable. If we can show (1), we have a solution technique for both problems; if we show (2), we know both problems are undecidable.

In some cases, we may be able to do even better. Two problems are equivalent if they are mutually reducible. That is, problem  A is equivalent to problem  B if problem  A is reducible to problem  B , and problem  B is reducible to problem  A . In this case, either both problems are decidable or both are undecidable, and we can work on either one. (Notice that this is not true in general. For example, if we were to show that the subset problem for reachability sets is undecidable, this would tell us nothing about the decidability or undecidability of the equality problem.)

The second consideration for investigating analysis problems is that if a solution technique exists it must be reasonably efficient. This requires that the amount of time and memory space needed by an algorithm to solve an instance of the problem not be excessive. The study of the cost of executing an algorithm is a part of complexity theory. Complexity theory deals with the amount of time and space needed to solve a problem. Obviously the amount of time and space will not be constant but will vary with the size of the problem to be solved. For Petri nets, time and space requirements would probably be a function of the number of places and transitions. Other factors which might influence things would be the number of tokens in the initial marking or the number of inputs and outputs for each transition and place (the number of arcs in the graph).

The time and space needed will vary with the particular instance of the problem to be solved. Therefore, complexity results may be in the form of a best case (lower bound) or worst case (upper bound) for an algorithm. Since it is not known in advance whether an instance will be a best case or worst case, the worst case is generally assumed, and the complexity of an algorithm is the worst case time or space requirements, as a function of the size of the input.

Complexity analysis is mainly concerned with the underlying problem complexity, and not concerned with a specific detailed implementation of any particular algorithm. Thus, complexity theory ignores constant factors. Complexity for a problem of size  n is determined to be of order  n sup {2} or  e sup {n} or  n log n allowing for smaller terms and constant factors. In particular two general classes of algorithms are important: those with polynomial complexity ( n ,  n sup {2} ,  n log n ,  n sup {8} , and so on) and those with nonpolynomial complexity (especially exponential,  2 sup {n} , and factorial,  n ! ).

Complexity analysis is generally applied to specific algorithms but can also be applied to general problems. In this case, a lower bound on the complexity of all algorithms to solve a problem is determined. This provides an algorithm-independent complexity result. It also can be useful in showing that a particular algorithm is optimal (within a constant) and when further work may produce a significantly better algorithm to solve a problem. For example, it is well-known that sorting  n numbers is of complexity  n log n . Thus algorithms with  n log n complexity cannot be significantly improved on (in the asymptotic worst case).

Reducibility can be useful in determining complexity. If a problem  A can be reduced to a problem  B and  B has a complexity  f sub {B} ( n ) , then the complexity of  A is at most the complexity of  B plus the cost of the transformation from  A to  B (keeping in mind that the size of the problem may also change in the transformation). The complexity of the transformations is generally constant or linear and so is often ignored. Thus, reducing problem  A to problem  B gives either an upper bound for the complexity of  A (if the complexity of  B is known) or a lower bound for the complexity of  B (if the complexity of  A is known). Again by using as an example the equality and subset problems, the amount of work needed to solve the equality problem is no greater than twice the amount of work for the subset problem. Since this is a constant factor, the complexity of the subset problem should be the same as the complexity of the equality problem.

These two properties of Petri net analysis properties -- decidability and complexity -- are of major concern for the use of Petri nets. In this chapter we present some results which have been obtained. One of the techniques used is to reduce one Petri net problem to another.

Section 5.2. Reachability Problems

The reachability problem is one of the most important problems for Petri net analysis. It is also open to a large amount of variation in definition. The following four reachability problems for a Petri net  C = (P, T, I, O) with initial marking  mu have been posed.

DEFINITION 5.3 The Reachability Problem
Given  mu prime , is  mu prime \(mo R ( C , mu ) ?
DEFINITION 5.4 The Submarking Reachability Problem
For a subset  P prime \(ib P and a marking  mu prime , does there exist  mu prime prime \(mo R ( C , mu ) such that  mu prime prime ( p sub {i} ) = mu prime ( p sub {i} ) for all  p sub {i} \(mo P prime ?
DEFINITION 5.5 The Zero-Reachability Problem
Is  mu prime \(mo R ( C , mu ) with  mu prime ( p sub {i} ) = 0 for all  p sub {i} \(mo P ? [Is  0 \(mo R ( C , mu ) ?]
DEFINITION 5.6 The Single-Place Zero-Reachability Problem
For a given place  p sub {i} \(mo P , does there exist  mu prime \(mo R ( C , mu ) with  mu prime ( p sub {i} ) = 0 ?
The submarking reachability problem restricts the reachability problem to considering only a subset of places, not caring about the markings of other places. The zero-reachability problem asks if the specific marking with zero tokens in all places is reachable. The single-place zero-reachability problem asks if it is possible to empty all the tokens out of a particular place.

Although these four problems are all different, they are all equivalent. Certain relationships are immediately obvious. The zero-reachability problem is reducible to the reachability problem; we simply set  mu prime = 0 for the reachability problem. Similarly the reachability problem is reducible to the submarking reachability problem, by setting the subset  P prime = P . The single-place zero-reachability problem is reducible to the submarking reachability problem by setting  P prime = { p sub {i} } and  mu prime = 0 . More difficult to show is that the submarking reachability problem is reducible to the zero-reachability problem and that the zero-reachability problem is reducible to the single-place zero-reachability problem. This entire set of relationships is shown in Figure 5.1.


Figure 5.1 . Reducibility among reachability problems. An arc from one problem to another indicates that the first is reducible to the second.


First, we show that the submarking reachability problem is reducible to the zero-reachability problem. Assume we are given a Petri net  C sub {1} = (P sub {1}, T sub {1}, I sub {1}, O sub {1} ) with initial marking  mu sub {1} , a subset of places  P prime \(ib P sub {1} , and a marking  mu prime . We want to know if there exists  mu prime prime \(mo R ( C sub {1}, mu sub {1} ) with  mu prime ( p sub {i} ) = mu prime prime ( p sub {i} ) for all  p sub {i} \(mo P prime . Our approach is to create a new Petri net  C sub {2} = (P sub {2}, T sub {2}, I sub {2}, O sub {2} ) with initial marking  mu sub {2} such that there exists  mu prime prime \(mo R ( C sub {1}, mu sub {1} ) with  mu prime ( p sub {i} ) = mu prime prime ( p sub {i} ) for all  p sub {i} \(mo P prime if and only if  0 \(mo R ( C sub {2}, mu sub {2} ) .

The construction of  C sub {2} from  C sub {1} is quite straightforward. We start with  C sub {2} the same as  C sub {1} . To allow any place  p sub {i} not in  P prime to become empty we add a transition  t sub {i} prime with input  { p sub {i} } and null output. This transition can fire whenever there is a token in  p sub {i} to drain off any tokens which may reside here. This allows us to ignore these places, being sure that they can always reach a zero marking.

For places  p sub {i} in  P prime , we must assure that exactly  mu prime ( p sub {i} ) tokens are in  p sub {i} . To assure this we create a new place  p sub {i} prime for each  p sub {i} \(mo P prime with an initial marking of  mu prime ( p sub {i} ) tokens and a transition  t sub {i} prime with input  { p sub {i}, p sub {i} prime } and null output. If there are exactly  mu prime ( p sub {i} ) tokens in  p sub {i} , then this transition can fire exactly  mu prime ( p sub {i} ) times, reducing the markings of  p sub {i} and  p sub {i} prime to zero. If the number of tokens in  p sub {i} is not  mu prime ( p sub {i} ) , then the transition  t sub {i} prime can only fire the minimum of the two markings, and so tokens will be left in either  p sub {i} or  p sub {i} prime , preventing the zero marking from being reached.


Figure 5.2 . A Petri net showing that the submarking reachability problem can be reduced to the zero-reachability problem. The subset of places  P prime will have the marking  mu in the original net if and only if the zero marking is reachable in the net as modified here.


Figure 5.2 illustrates the two types of transitions introduced. Formally we define  C sub {2} by








with an initial marking



THEOREM 5.1
The submarking reachability problem is reducible to the zero-reachability problem.

Proof :
We show that for the Petri net  C sub {2} constructed above from  C sub {1}, 0 \(mo R ( C sub {2}, mu sub {2} ) if and only if  mu prime prime \(mo R ( C sub {1}, mu sub {1} ) with  mu prime prime ( p sub {i} ) = mu prime ( p sub {i} ) for all  p sub {i} \(mo P prime .

To show that  0 \(mo R ( C sub {2}, mu sub {2} ) if and only if there exists a  mu prime prime \(mo R ( C sub {1}, mu sub {1} ) with  mu prime prime ( p sub {i} ) = mu prime ( p sub {i} ) for  p sub {i} \(mo P prime , assume first that  mu prime prime exists in  R ( C sub {1}, mu sub {1} ) . Then in  C sub {2} we can also reach the marking  mu prime prime in the places  p sub {i} \(mo P sub {1} by firing only those transitions from  T sub {1} . Now for each  p sub {i} \(mo P prime , we can fire  t sub {i} prime exactly  mu prime ( p sub {i} ) times, reducing both  p sub {i} and  p sub {i} prime to zero. Then we can fire  t sub {i} prime for each  p sub {i} \(\o'\(sl\(mo' P prime as many times as necessary to put these to zero, so  0 \(mo R ( C sub {2}, mu sub {2} ) .

Now assume  0 \(mo R ( C sub {2}, mu sub {2} ) ; then there exists a sequence of transition firings  sigma which leads from  mu sub {2} to 0. This sequence will contain exactly  mu prime ( p sub {i} ) firings of  t sub {i} prime for  p sub {i} \(mo P prime (to remove the tokens from  p sub {i} prime ) and some number of firings of  t sub {i} prime for  p sub {i} \(\o'\(sl\(mo' P prime . Note that these transition firings only remove tokens from  C sub {1} , and since  delta ( mu prime , t sub {j} ) is defined whenever  delta ( mu , t sub {j} ) is defined for  mu prime >= mu (extra tokens never hurt), the sequence  sigma with all  t sub {i} prime firings removed is also legal and will lead to a marking  mu prime prime with exactly  mu prime ( p sub {i} ) tokens in  p sub {i} for  p sub {i} \(mo P prime . Thus if  0 \(mo R ( C sub {2}, mu sub {2} ) , then  mu prime prime \(mo R ( C sub {1}, mu sub {1} ) with  mu prime prime ( p sub {i} ) = mu prime ( p sub {i} ) for  p sub {i} \(mo P prime . Q.E.D.

Our next task is to show that the zero-reachability problem is reducible to the single-place zero-reachability problem. The proof of this statement again involves a construction. Given a Petri net  C sub {1} = (P sub {1}, T sub {1}, I sub {1}, O sub {1} ) with initial marking  mu sub {1} , we wish to determine if  0 \(mo R ( C sub {1}, mu sub {1} ) . We construct, from  C sub {1} , a new Petri net  C sub {2} with an additional place  s (P sub {2} = P sub {1} union { s } ) such that there exists a marking  mu prime \(mo R ( C sub {2}, mu sub {2} ) with  mu prime ( s ) = 0 if and only if  0 \(mo R ( C sub {1}, mu sub {1} ) .

The construction of  C sub {2} defines  s so that at all times the number of tokens in  s is equal to the sum of the number of tokens in the places of  C sub {1} . Thus if  mu prime ( s ) = 0 , then there are zero tokens in all places of  C sub {1} and vice versa. We define the initial marking  mu sub {2} by



Now for each transition  t sub {j} \(mo T sub {1} , the same transition is in  C sub {2} but augmented by arcs to the place  s . Define


Then  d sub {j} is the change in the number of tokens which results from firing transition  t sub {j} . Now if  d sub {j} > 0 , then  d sub {j} tokens must be added to place  s , so we add  d sub {j} arcs from  t sub {j} to  s ; if  d sub {j} < 0 , then we remove  - d sub {j} tokens from  s by  - d sub {j} arcs from  s to  t sub {j} .
With this construction, any sequence of transition firings which leads  C sub {1} to the marking 0 will lead  C sub {2} to a marking  mu prime with  mu prime ( s ) = 0 [ mu prime ( p sub {i} ) = 0 also] and vice versa.
THEOREM 5.2
The zero-reachability problem is reducible to the single-place zero-reachability problem.

Proof :
The formal proof, based on the above construction, is left to the reader. Q.E.D.
With these two theorems, and the obvious observations, we can now conclude the following.
THEOREM 5.3
The following reachability problems are equivalent

  1. The reachability problem

  2. The zero-reachability problem

  3. The submarking reachability problem

  4. The single-place zero-reachability problem
These theorems and their proofs are mainly due to Hack [1975c].

Section 5.3. Limited Petri Net Structures

The early work on Petri nets, and some current work, defined Petri nets in somewhat more restricted ways than the definition in Chapter 2. In particular, the following two restrictions are sometimes enforced.

RESTRICTION 5.1
The multiplicity of any place is limited to be less than or equal to 1. That is,  # ( p sub {i}, I ( t sub {j} )) <= 1 and  # ( p sub {i}, O ( t sub {j} )) <= 1 for all  p sub {i} \(mo P and  t sub {j} \(mo T . This restricts the input and output bags to be sets.
RESTRICTION 5.2
No place may be both an input and an output of the same transition.  I ( t sub {j} ) inter O ( t sub {j} ) = \(es . This is often stated as  # ( p sub {i}, I ( t sub {j} )) cdot # ( p sub {i}, O ( t sub {j} )) = 0 , for all  p sub {i} and  t sub {j} .
Petri nets which satisfy Restriction 1 are called ordinary Petri nets. Petri nets which satisfy Restriction 2 are called self-loop-free Petri nets or nonreflexive Petri nets. Petri nets satisfying both restrictions are called restricted Petri nets. These classes of Petri nets are related as shown in Figure 5.3.

Figure 5.3 . The relationships among the classes of Petri nets. An arc indicates containment; reducibility arcs would be directed in the opposite direction.


These subclasses of the general Petri net model have been considered for several reasons. A major reason is that the propagation of Petri net concepts was informal in its earlier theory. The need for multiple arcs or self-loops did not occur in early modeling. Also, it was probably felt that the theory would be easier without these additional complications to the theory. As the theory has developed, however, it has become evident that the more general definitions have not been more difficult to work with. Current work using models with these restrictions is thus either the result of unnecessary timidity on the part of the researcher or the need for quicker exposition leading to simpler definitions.

However, these restrictions add nothing to our ability to analyze Petri nets. Consider the reachability problem for these classes of nets. To show the essential equivalence of these four classes of Petri nets, we prove the following.

THEOREM 5.4
The following reachability problems are equivalent.

  1. General Petri nets

  2. Ordinary Petri nets

  3. Self-loop-free Petri nets

  4. Restricted Petri nets

Proof :
The following reducibilities are obvious from the definitions.

  1. The reachability problem for ordinary Petri nets is reducible to the reachability problem for general Petri nets.

  2. The reachability problem for self-loop-free Petri nets is reducible to the reachability problem for general Petri nets.

  3. The reachability problem for restricted Petri nets is reducible to both the reachability problem for ordinary Petri nets and the reachability problem for self-loop-free Petri nets.

We show that general Petri nets can be transformed into restricted Petri nets in such a way as to reduce the reachability problem for general Petri nets to the reachability problem for restricted Petri nets. This then shows that these four reachability problems are equivalent.

To transform a general Petri net into a restricted Petri net, we use the following basic approach. Every place in the general Petri net is replaced by a ring of places in the restricted Petri net. Figure 5.4 shows the general form of a ring of places. Notice that a collection of tokens placed in the ring can freely move around the ring to any position at any time; they can all group into place  p sub {i,1} or spread out uniformly to cover all  k sub {i} places in the ring. Thus a transition which needs three tokens from place  p sub {i} can pick up one from each of  p sub {i,1} ,  p sub {i,2} , and  p sub {i,3} rather than all three from  p sub {i} . Similarly a transition which uses  p sub {i} both as an input and as an output (a self-loop) may input from  p sub {i,1} and output to  p sub {i,2} , eliminating the self-loop.


Figure 5.4 . A ring of places to be used in a restricted Petri net to represent a place in a general Petri net. The number of places  k sub {i} representing a place  p sub {i} is determined by the sum of the maximum multiplicities of the place.


Formally, for a general Petri net  C sub {1} = (P sub {1}, T sub {1}, I sub {1}, O sub {1} ) with marking  mu sub {1} , we define a restricted Petri net  C sub {2} = (P sub {2}, T sub {2}, I sub {2}, O sub {2} ) with marking  mu sub {2} as follows. First define, for each  p sub {i} \(mo P sub {1} , an integer  k sub {i} by


The restricted Petri net  C sub {2} is defined by



The input and output functions for ``normal'' transitions are defined such that





while for the ``ring'' transitions,



The marking  mu sub {2} is defined by



By construction, for any marking  mu which is reachable in  C sub {1} , there exists a marking  mu prime of  C sub {2} such that


In particular it is possible to move all tokens from  p sub { i , h } to  p sub {i,1} in  C sub {2} at any time. Thus, we can define a marking  mu prime by



and  mu prime is reachable in the restricted Petri net  C sub {2} if and only if  mu is reachable in  C sub {1} . Q.E.D.

Thus, from the point of view of analysis, general Petri nets and these three restricted classes of the general Petri net -- ordinary Petri nets, self-loop-free Petri nets, and restricted Petri nets -- are equivalent, each can be transformed into a similar net of another class, allowing a reachability problem in one to be reduced to a reachability problem in another. The constructions in this section are due to Hack [1974a].


Figure 5.5 . Reducibility of the reachability problem among classes of limited Petri nets.


Section 5.4. Liveness and Reachability

Reachability is an important problem, but not the only remaining problem for Petri nets. Liveness is another problem which has received much attention in the Petri net literature. As pointed out in Section 4.1.4, liveness is related to deadlock. Two liveness problems for a Petri net  C = (P, T, I, O) with initial marking  mu are of concern here. A Petri net is live if each transition is live. A transition  t sub {j} is live in a marking  mu if for each  mu prime \(mo R ( C , mu ) there exists a sequence  sigma such that  t sub {j} is enabled in  delta ( mu prime , sigma ) . A transition  t sub {j} is dead in a marking  mu if there is no reachable marking in which it can fire.

DEFINITION 5.7 Liveness Problem
For all transitions  t sub {j} \(mo T , is  t sub {j} live?
DEFINITION 5.8 Single-Transition Liveness Problem
Given  t sub {j} \(mo T , is  t sub {j} live?

The liveness problem is obviously reducible to the single-transition liveness problem. To solve the liveness problem, we simply solve the single-transition liveness problem for each  t sub {j} \(mo T ; if  | T | = m , then we must solve  m single-transition liveness problems.

The reachability problem can also be reduced to the liveness problem. Since the many variants of the reachability problem are equivalent, we use the single-place zero-reachability problem. If we have any of the other reachability problems, they can be reduced to the single-place zero-reachability problem as shown in Section 5.2. Now, if we wish to determine if place  p sub {i} can be zero in any reachable marking for a Petri net  C sub {1} = (P sub {1}, T sub {1}, I sub {1}, O sub {1} ) with initial marking  mu sub {1} , we construct a Petri net  C sub {2} = (P sub {2}, T sub {2}, I sub {2}, O sub {2} ) with initial marking  mu sub {2} , which is live if and only if the zero marking is not reachable from  mu sub {1} .

The Petri net  C sub {2} is constructed from  C sub {1} by the addition of two places,  r sub {1} and  r sub {2} , and three transitions,  s sub {1} ,  s sub {2} , and  s sub {3} . We first modify all transitions of  T sub {1} to include  r sub {1} as both an input and an output. The initial marking  mu sub {2} will include a token in  r sub {1} . The place  r sub {1} is a ``run'' place; as long as the token remains in  r sub {1} the transitions of  T sub {1} can fire normally. Thus any marking which is reachable in the places of  P sub {1} in  C sub {1} is also reachable in  C sub {2} . Transition  s sub {1} is defined to have  r sub {1} as its input and a null output. This allows the token in  r sub {1} to be removed, disabling all transitions in  T sub {1} and ``freezing'' the marking of  P sub {1} . (Note that all transitions of  T sub {1} are in conflict and, by construction if not by definition, that no more than one transition can fire at a time.)

The place  r sub {1} and transition  s sub {1} allow the net  C sub {1} to reach any reachable marking and then for  s sub {1} to fire and freeze the net at that marking. Now we need to see if place  p sub {i} is zero. We introduce a new place  r sub {2} and a transition  s sub {2} which has  p sub {i} as its input and  r sub {2} as its output. If  p sub {i} can ever become zero, this transition is not live; in fact the entire net is dead if transition  s sub {1} fires in that marking. Hence if  p sub {i} can be zero, the net is not live. If  p sub {i} cannot be zero, then  s sub {2} can always fire, putting a token in  r sub {2} . In this case we must put a token back in  r sub {1} and assure that all transitions in  C sub {2} are live. We must be sure that  C sub {2} is live even if  C sub {1} is not live. This is accomplished by a transition  s sub {3} which ``floods'' the net  C sub {2} with tokens, assuring that every transition is live if a token is ever put in  r sub {2} . Transition  s sub {3} has  r sub {2} as its input and every place of  C sub {2} (all  p sub {i} in  C sub {1} and  r sub {1} and  r sub {2} ) as output. This construction is illustrated in Figure 5.6.


Figure 5.6 . A construction converting the single-place zero-reachability problem [is a marking reachable with  mu ( p sub {i} ) = 0 ?] to the liveness problem [is this net live?].


Now, if a marking  mu is reachable in  R ( C sub {1}, mu sub {1} ) with  mu ( p sub {i} ) = 0 , then the net  C sub {2} can also reach this marking on the place of  P sub {1} by executing the same sequence of transition firings. Then  s sub {1} can fire, freezing the  C sub {1} subset. Since  mu ( p sub {i} ) = 0 , transition  s sub {2} cannot fire and  C sub {2} is dead. Thus if  p sub {i} can become zero, then  C sub {2} is not live.

Conversely, if  C sub {2} is not live then, a marking  mu must be reachable in which  mu ( r sub {2} ) = 0 and there is no reachable state in which  r sub {2} has a token. [If  r sub {2} has a token,  s sub {3} is enabled, and  s sub {3} can be fired repeatedly enough times to enable any (or all) transitions, and so the net is live.] If  r sub {2} has no token and cannot get any, then the marking of  p sub {i} must also be zero. Thus if  C sub {2} is not live, then a marking is reachable in which the marking of  p sub {i} is zero.

On the basis of this construction, we have the following.

THEOREM 5.5
The reachability problem is reducible to the liveness problem.

Now we need to show the following.

THEOREM 5.6
The single-transition liveness problem is reducible to the reachability problem.

The proof that the single-transition liveness problem is reducible to the reachability problem rests on testing for the reachability of any of a finite set of maximal  t sub {j} -dead submarkings. A Petri net is not live for a transition  t sub {j} if and only if any marking is reachable in which the transition  t sub {j} is not fireable and cannot become fireable. A marking of this sort is called  t sub {j} -dead. For any marking  mu we can test if it is  t sub {j} -dead by constructing the reachability tree with  mu as the root and testing if transition  t sub {j} can fire anywhere in the tree. If it cannot then  mu is  t sub {j} -dead. Checking for liveness of  t sub {j} then requires checking if any  t sub {j} -dead marking is reachable.

In general, however, there may be an infinite number of  t sub {j} -dead markings and an infinite set of markings in which to find the  t sub {j} -dead markings. The set of markings which must be checked for reachability is reduced to a finite number by noting two properties. First, if a marking  mu is  t sub {j} -dead, then any marking  mu prime <= mu is also  t sub {j} -dead. (Any firing sequence possible from  mu prime is also possible from  mu , so if  mu prime could lead to the firing of  t sub {j} , so could  mu .) Second, the markings of some places will not affect the  t sub {j} -deadness of a marking, and so the markings of these places are ``don't-cares''; they can be arbitrary. Borrowing from the reachability tree construction, we replace these ``don't-care'' components by  omega to indicate that an arbitrarily large number of tokens can be in this place without affecting the  t sub {j} -deadness of the marking. Now since any  mu prime <= mu is  t sub {j} -dead if  mu is  t sub {j} -dead, we need not consider those places  p sub {i} with  mu ( p sub {i} ) = omega . This means we use the submarking reachability problem with  P prime = { p sub {i} | mu ( p sub {i} ) \(!= omega } .

As an example, consider the Petri net of Figure 5.7. The markings (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (0, 3), ... are  t sub {j} -dead, but they can be finitely represented by the set  { (0, omega ), (2, 0), (1, 0) } .


Figure 5.7 . A Petri net to illustrate  t sub {j} -dead markings.


Hack [1974c; 1975c] has shown that there exists for a Petri net  C a finite set  D sub {t} of markings (extended to include  omega ) such that  C is live if and only if no marking in  D sub {t} is reachable. If a marking of  D sub {t} contains  omega , submarking reachability is implied.

Further,  D sub {t} can be effectively computed. Since  D sub {t} is finite, the non- omega -components of the markings have an upper bound  b . This bound  b is characterized as the smallest number such that for any marking  mu with  mu ( p sub {i} ) <= b + 1 for all  p sub {i} , if  mu is  t sub {j} -dead, then the submarking  mu prime , with  mu prime ( p sub {i} ) = mu ( p sub {i} ) if  mu ( p sub {i} ) <= b and  mu prime ( p sub {i} ) = omega if  mu ( p sub {i} ) = b + 1 , is  t sub {j} -dead. With this characterization of  b , we can construct  D sub {t} as follows.

  1. Compute  b . Start with  b = 0 , and increase  b until the first  b is found which satisfies the characterization of the bound defined above. Testing for  b requires checking all  ( b + 2 ) sup {n} markings with components less than or equal to  b + 1 .

  2. Compute  D sub {t} by testing all markings and submarkings with components less than or equal to  b or equal to  omega .  D sub {t} is the set of  t sub {j} -dead markings from this set of  ( b + 2 ) sup {n} -vectors.

Once we have constructed  D sub {t} , we then apply the submarking reachability problem for each element of  D sub {t} . If any element of  D sub {t} is reachable from the initial marking, the Petri net is not live; if no element of  D sub {t} is reachable, the Petri net is live.

From these two theorems, we have the following.

THEOREM 5.7
The following problems are equivalent:

  1. The reachability problem

  2. The liveness problem

  3. The single-transition liveness problem

More formal proofs of the reducibility of liveness to reachability can be found in [Hack 1974c; Hack 1975c].

Section 5.5. Undecidable Results

In Section 5.4 we have shown that a number of problems in reachability and liveness are equivalent, but no result has been obtained yet on the decidability of these problems. To show decidability, it is necessary to reduce a Petri net problem to a problem with a known solution, or to show undecidability, to reduce a problem which is known to be undecidable to a Petri net problem. The first important result of this kind was by Rabin [Baker 1973b]. Rabin showed that for two Petri nets  C sub {1} with marking  mu sub {1} and  C sub {2} with marking  mu sub {2} it is undecidable if  R ( C sub {1}, mu sub {1} ) \(ib R ( C sub {2}, mu sub {2} ) . Hack [1975a] later strengthened this to show that it is undecidable if  R ( C sub {1}, mu sub {1} ) = R ( C sub {2}, mu sub {2} ) . The proof of these statements is based on Hilbert's tenth problem. (In 1900, D. Hilbert presented 23 problems to a conference of mathematicians; this was the tenth in his list.)

DEFINITION 5.9 Hilbert's Tenth Problem
Given a polynomial  P over  n variables with integer coefficients, does there exist a vector of integers,  ( x sub {1}, x sub {2}, ..., x sub {n} ) such that


The equation  P ( x sub {1}, x sub {2}, ..., x sub {n} ) = 0 is a Diophantine equation. In general it will be a sum of terms



Diophantine equations include  x sub {1} = 0 ,  3 x sub {1} cdot x sub {2} + 6 x sub {3} = 0 , and so on.

In 1970, Matijasevic proved that Hilbert's tenth problem was undecidable [Davis 1973; Davis and Hersh 1973]: There is no general algorithm to determine if an arbitrary Diophantine equation has a root (a set of values for which the polynomial is zero). This forms the basis of the proof that the equality problem for Petri net reachability sets is undecidable. The strategy is to construct for a Diophantine polynomial a Petri net which (in some sense) computes all values of the polynomial.

5.5.1. The Polynomial Graph Inclusion Problem

The proof of the undecidability of the equality problem is in three parts (Figure 5.8). First, Hilbert's tenth problem is reduced to the polynomial graph inclusion problem. Then the polynomial graph inclusion problem is reduced to the subset problem for Petri net reachability sets. Finally, the subset problem for Petri net reachability sets is reduced to the equality problem for Petri net reachability sets. This shows that Hilbert's tenth problem, known to be undecidable, is reducible to the equality problem, which must therefore also be undecidable.


Figure 5.8 . The reducibilities showing that the equality (and subset) problem for Petri net reachability sets is undecidable.


DEFINITION 5.10
The graph  G ( P ) of a Diophantine polynomial  P ( x sub {1}, ..., x sub {n} ) with nonnegative coefficients is the set


DEFINITION 5.11
The polynomial graph inclusion problem is to determine for two Diophantine polynomials  A and  B if  G ( A ) \(ib G ( B ) .
We first show that Hilbert's tenth problem is reducible to the polynomial graph inclusion problem. This proves the following.
THEOREM 5.8
The polynomial graph inclusion problem is undecidable.

Proof :

  1. We limit our proof to problems with nonnegative solutions. If  ( x sub {1}, ..., x sub {n} ) is a solution to  P ( x sub {1}, ..., x sub {n} ) = 0 , with  x sub {i} < 0 , then  ( x sub {1}, ..., - x sub {i}, ..., x sub {n} ) is a solution to  P ( x sub {1}, ..., - x sub {i}, ..., x sub {n} ) = 0 . Thus, for an arbitrary polynomial, we need only test each of the  2 sup {n} polynomials which result from changing the sign of some subset of variables for nonnegative solutions to determine the solution for the arbitrary polynomial.

  2. Similarly, since  P sup {2}( x sub {1}, ..., x sub {n} ) = 0 if and only if  P ( x sub {1}, x sub {2}, ..., x sub {n} ) = 0 , we need only consider polynomials whose value is nonnegative.

  3. Now we can separate any polynomial  P ( x sub {1}, x sub {2}, ..., x sub {n} ) into two polynomials  Q sub {1}( x sub {1}, ..., x sub {n} ) and  Q sub {2}( x sub {1}, ..., x sub {n} ) such that  P ( x sub {1}, ..., x sub {n} ) = Q sub {1}( x sub {1}, x sub {2}, ..., x sub {n} ) - Q sub {2}( x sub {1}, ..., x sub {n} ) by putting all terms with positive coefficients in  Q sub {1} and all terms with negative coefficients in  Q sub {2} . Now since  P ( x sub {1}, ..., x sub {n} ) >= 0 (by 2 above), we have  Q sub {1}( x sub {1}, ..., x sub {n} ) >= Q sub {2}( x sub {1}, ..., x sub {n} ) and  P ( x sub {1}, ..., x sub {n} ) = 0 if and only if  Q sub {1}( x sub {1}, x sub {2}, ..., x sub {n} ) = Q sub {2}( x sub {1}, ..., x sub {n} ) .

  4. Consider the two polynomial graphs



    Now,  G ( Q sub {2} + 1) \(ib G ( Q sub {1} ) if and only if for all nonnegative  x sub {1}, ..., x sub {n} and  y ,  y <= 1 + Q sub {2}( x sub {1}, ..., x sub {n} ) implies that  y <= Q sub {1}( x sub {1}, ..., x sub {n} ) . This is true if and only if there does not exist  x sub {1}, ..., x sub {n} and  y such that


    But from 3 above,  Q sub {1} >= Q sub {2} so that


    and, since all quantities are integers,


    which is true if and only if  Q sub {1} = Q sub {2} . Thus, we see that  G ( Q sub {2} + 1) \(ib G ( Q sub {1} ) if and only if there does not exist  x sub {1}, ..., x sub {n} such that  Q sub {1}( x sub {1}, ..., x sub {n} ) = Q sub {2}( x sub {1}, ..., x sub {n} ) , which is to say there does not exist  x sub {1}, ..., x sub {n} such that  P ( x sub {1}, ..., x sub {n} ) = 0 .

  5. Therefore to determine that the equation  P ( x sub {1}, x sub {2}, ..., x sub {n} ) = 0 has a solution, we need only to show that it is not the case that  G ( Q sub {2} + 1) \(ib G ( Q sub {1} ) .
Q.E.D.

5.5.2. Weak Computation

Now we need to show that Petri nets can (in some sense) compute the value of a polynomial  Q ( x sub {1}, x sub {2}, ..., x sub {n} ) . We have carefully limited the polynomial  Q to having a nonnegative value, nonnegative coefficients, and nonnegative variables. This allows us to encode the values of the variables and the value of the polynomial as the number of tokens in places in a Petri net. Figure 5.9 shows the general scheme. The input values  x sub {1}, ..., x sub {n} are encoded by  x sub {i} tokens in  p sub {i} for  i = 1, ..., n . Initially a token also resides in the ``run'' place. The execution of the net will terminate by placing a token in the ``quit'' place. At this time the ``output'' place will have  y tokens, where  y <= Q ( x sub {1}, ..., x sub {n} ) .


Figure 5.9 . Basic structure of a Petri net to weakly compute the value of a polynomial,  Q ( x sub {1}, x sub {2}, ..., x sub {n} ) .


This Petri net will weakly compute the value  Q ( x sub {1}, ..., x sub {n} ) . Weak computation means that the value computed will not exceed  Q ( x sub {1}, ..., x sub {n} ) but may be any (nonnegative) value less than  Q ( x sub {1}, ..., x sub {n} ) . Weak computation is necessary for Petri nets because of the permissive nature of transition firings; a Petri net cannot be forced to finish. The definition of a polynomial graph  G ( Q ) was made specifically with this in mind.

What we show now is that subnets can be constructed which weakly compute the function of (binary) multiplication. From this, we can construct a composite net which weakly computes the value of each term of a polynomial by successive multiplication subnets. The output of the subnet for each term will be deposited in the output place for the polynomial. Thus the number of tokens in the output place will be the sum of the outputs for each term.

The multiplication subnet is shown in Figure 5.10. This net will weakly compute the product of the numbers,  x and  y , of tokens in its two inputs and place this many tokens in its output. The operation of the net is quite simple. To compute the product of  x and  y , transition  t sub {1} first fires, moving one token from  p sub {x} to  p sub {2} . This token enables transition  t sub {3} , which can now copy  y tokens from place  p sub {y} , putting them in  p sub {3} and putting  y tokens in  p sub { x cdot y } , the output place. Now  t sub {2} can fire, putting the token in  p sub {2} back into  p sub {1} . This enables  t sub {4} , which can copy the  y tokens from  p sub {3} back into  p sub {y} . This entire process can be repeated exactly  x times, each time putting  y tokens in  p sub { x cdot y } . Then the marking of place  p sub {x} has been reduced to zero, and the net must stop. The total number of tokens in place  p sub { x cdot y } is then the product of  x and  y .


Figure 5.10 . A multiplier subnet. This subnet weakly computes the product of  x and  y .


The above case is the best case, in the sense that the number of output tokens is exactly  x cdot y . However, the token in  p sub {2} enables both transitions  t sub {3} and  t sub {2} , and it is possible for  t sub {2} to fire before all  y tokens have been copied from  p sub {y} to  p sub {3} and been added to  p sub { x cdot y } . In this case, the number of tokens deposited in  p sub { x cdot y } will be less than  x cdot y . Since  t sub {3} can fire no more than  y times for each firing of  t sub {1} and  t sub {1} can fire no more than  x times, we can guarantee that the number of tokens in  p sub { x cdot y } never exceeds  x cdot y , but because of the permissive nature of transition firings, we cannot guarantee that the number of tokens in  p sub { x cdot y } will actually equal  x cdot y ; it could be less. Thus, this Petri net weakly computes the product of  x and  y . Now to weakly compute a term  R sub {i} which is the product  a sub {i} x sub { s sub {1}} x sub { s sub {2}} ... x sub { s sub {h}} we construct a Petri net of the form shown in Figure 5.11. Since each subnet weakly computes the product of two terms, the entire subnet weakly computes the value of the term  R sub {i} .


Figure 5.11 . A Petri net structure to weakly compute a term of a Diophantine polynomial. Each box is a net of the form of Figure 5.10.


Figure 5.12 then shows how a polynomial  P = R sub {1} + R sub {2} + ... + R sub {k} can be weakly computed. Each subnet is of the form of Figure 5.11 and weakly computes the value of one term. The outputs of the  k subnets for each term have been merged together, giving a total value which is the sum of each term.


Figure 5.12 . A Petri net to weakly compute  P ( x sub {1}, x sub {2}, ..., x sub {n} ) by using a collection of subnets of the form in Figure 5.11.


Now some control transitions and places are added to create the specific reachability sets needed. First we need to be able to produce an arbitrary value for each of the variables  ( x sub {1}, ..., x sub {n} ) and record that value in the places  p sub {1}, ..., p sub {n} . A transition  t sub {i} is created for each  p sub {i} with null input and outputs to  p sub {i} and every place which is an input corresponding to  x sub {i} in a term  R sub {j} which uses  x sub {i} . Thus, in the polynomial  x sub {1} + x sub {1} x sub {2} we would have a transition  t sub {1} with outputs to  p sub {1} and to the  x sub {1} inputs of the two terms,  x sub {1} and  x sub {1} x sub {2} , which use  x sub {1} ;  t sub {2} would output to  p sub {2} and to the  x sub {2} input of the term  x sub {1} x sub {2} .

These transitions can fire an arbitrary number of times, creating any value in  p sub {1}, ..., p sub {n} . Thus, for every  y <= P ( x sub {1}, ..., x sub {n} ) a marking  mu is reachable with  mu ( p sub {1} ) = x sub {1}, ...,   mu ( p sub {n} ) = x sub {n} and  mu ( output ) = y . The value  y = P ( x sub {1}, ..., x sub {n} ) can be achieved by first firing  t sub {1} x sub {1} times, putting  x sub {1} tokens in  p sub {1} , then firing  t sub {2} x sub {2} times, and so on until  t sub {n} has fired  x sub {n} times. The subnet for each term  R sub {i} of the polynomial can then execute, with the resulting polynomial value put in the output place.

To reduce the polynomial graph inclusion problem to the subset problem for Petri net reachability sets, we perform the following steps. For polynomials  A and  B , we wish to determine if  G ( A ) \(ib G ( B ) .

  1. We construct the Petri net  C sub {A} which weakly computes  A ( x sub {1}, ..., x sub {n} ) and the Petri net  C sub {B} which weakly computes  B ( x sub {1}, ..., x sub {n} ) .

  2. If the number of places in the two nets is not equal, we add places to the smaller to equalize the number of places. These places are initially unmarked and are not used by any of the transitions in the net.

  3. Now we must eliminate the effects of all internal places on the reachability sets. A set of  n + 1 places are distinguished in both  C sub {A} and  C sub {B} , the places corresponding to the values of  x sub {1}, ..., x sub {n} and the output of each net. All other places are internal places, whose markings are unimportant. However, we may find that for an internal place  p sub {i} in  C sub {A} and corresponding  p sub {i} prime in  C sub {B} that there exists a marking  mu in  R ( C sub {A}, mu sub {A} ) with no equal marking  mu prime in  R ( C sub {B}, mu sub {B} ) , because  mu ( p sub {i} ) \(!= mu prime prime ( p sub {i} ) for all  mu prime prime in  R ( C sub {B}, mu sub {B} ) .

    To prevent this problem we add two new places  q and  r to  C sub {A} (giving  C sub {A} prime ) and  q prime and  r prime to  C sub {B} (giving  C sub {B} prime ). In  C sub {A} prime ,  q , and  r are not used for any transitions, and initially  r is empty and  q is marked with one token. In  C sub {B} prime ,  r prime is a ``run'' place. It is initially marked, and every transition in  C sub {B} prime is modified to include  r prime as both an input and an output. Thus, as long as the token remains in  r prime , the net  C sub {B} prime can function as before. A new transition transfers the enabling token from  r prime to  q prime , disabling all transitions in  C sub {B} prime and ``freezing'' the marking. Now we add two new transitions for each internal place in  C sub {B} prime .

    For each internal place  p sub {i} whose marking is unimportant, one transition has places  q prime and  p sub {i} as inputs and only  q prime as an output (allowing the marking in  p sub {i} to be decreased by one), and another transition has  q prime as input and both  q prime and  p sub {i} as outputs (allowing the marking in  p sub {i} to be increased by one). These transitions allow the marking of each internal place to be made arbitrary by an appropriate sequence of increasing or decreasing firings.

  4. The new construction is illustrated in Figure 5.13. For these two Petri nets,  C sub {A} prime and  C sub {B} prime with initial marking  mu sub {A} prime and  mu sub {B} prime , respectively,  G ( A ) \(ib G ( B ) if and only if  R ( C sub {A} prime , mu sub {A} prime ) \(ib R ( C sub {B} prime , mu sub {B} prime ) .

    Figure 5.13 . The constructed Petri nets to test for polynomial graph inclusion.


    The reachability sets of  C sub {A} prime and  C sub {B} prime are as follows. For  C sub {A} prime ,


    For  C sub {B} prime ,


    Thus, if  G ( A ) \(ib G ( B ) , then  R ( C sub {A} prime , mu sub {A} prime ) \(ib R ( C sub {B} prime , mu sub {B} prime ) , and conversely, if  R ( C sub {A} prime , mu sub {A} prime ) \(ib R ( C sub {B} prime , mu sub {B} prime ) , then  G ( A ) \(ib G ( B ) .

This concludes our demonstration of the following.

THEOREM 5.9
The polynomial graph inclusion problem is reducible to the subset problem for Petri net reachability sets.
This proof is from [Hack 1975a; Hack 1975c].

5.5.3. The Equality Problem

We now have only to show that the subset problem for Petri net reachability sets is reducible to the equality problem.

Assume that we have two Petri nets  A and  B and wish to determine if  R ( A, mu sub {A} ) \(ib R ( B, mu sub {B} ) (the subset problem). We now show that two Petri nets  D and  E can be defined such that  R ( A, mu sub {A} ) \(ib R ( B, mu sub {B} ) if and only if  R ( D, mu sub {D} ) = R ( E, mu sub {E} ) . The basis for this construction is the fact that


Both  D and  E are constructed from a common subnet,  C . The net  C encodes the reachability sets of both  A and  B in such a way as to produce their union. Figure 5.14 illustrates the basic construction. The  n places  p sub {1}, ..., p sub {n} act as either the  n places of net  A or the  n places of net  B . Originally they are unmarked. Two new places  r sub {A} and  r sub {B} are added as ``run'' places for net  A and net  B , respectively. All transitions of net  A are modified to include  r sub {A} as both an input and an output; all transitions of net  B are modified to include  r sub {B} as both an input and an output.


Figure 5.14 . The construction of Petri nets  C ,  D , and  E from  A , and  B . This construction is used to show that the subset problem is reducible to the equality problem for reachability sets.


Now, one more place,  s , is added and two new transitions,  t sub {A} and  t sub {B} . The initial marking for this entire net (including  A and  B as subnets with shared places; places  r sub {A} ,  r sub {B} , and  s ; and transitions  t sub {A} and  t sub {B} ) is one token in  s and zero tokens elsewhere. Transition  t sub {A} has place  s as its input and as output produces the initial marking for net  A plus a token in  r sub {A} ; transition  t sub {B} has place  s as its input and produces the initial marking for net  B plus a token in  r sub {B} . Thus, if  t sub {A} fires, then the subnet  A has its initial marking, and all of its transitions can fire as normal since there is a token in  r sub {A} . However, subnet  B is completely disabled, since there is no token in  r sub {B} . If  t sub {B} fires first, then the subnet  B can operate, and  A is disabled. The set of firing sequences for  C is then any sequence of the form


or any sequence of the form


The net  D is obtained from  C by adding one new transition,  q sub {B} . Transition  q sub {B} has place  r sub {B} as its input and no output. Notice that  q sub {B} can fire only if transition  t sub {B} was the first to fire; if transition  t sub {A} fires first, then  r sub {B} will be empty, and  t sub {B} cannot fire.

The net  E is constructed from  D by adding a new transition,  q sub {A} . Transition  q sub {A} has place  r sub {A} as its input and no output. Transition  q sub {A} can fire only if  t sub {A} was the first to fire: Notice that net  E is constructed from  D , not (directly) from  C . So  E has both transition  q sub {A} and transition  q sub {B} .

Now let us examine the reachability sets of the Petri nets  C ,  D , and  E . The reachability set of  C is all markings of the form


Petri net  D adds one other class of markings to this set:


And Petri net  E adds one more class to this:


Now, if  R ( A, mu sub {A} ) \(ib R ( B, mu sub {B} ) , the last class in  R ( E, mu sub {E} ) [markings of the form  (0, 0, 0, mu ) with  mu \(mo R ( A, mu sub {A} ) ] is included in the last class of  R ( D, mu sub {D} ) [markings of the form  (0, 0, 0, mu ) with  mu \(mo R ( B, mu sub {B} ) ]. Since all other markings are the same,


Similarly, if  R ( D, mu sub {D} ) = R ( E, mu sub {E} ) , then we must have  R ( A, mu sub {A} ) \(ib R ( B, mu sub {B} ) , since for each  (0, 0, 0, mu ) with  mu \(mo R ( A, mu sub {A} ) in  R ( E, mu sub {E} ) there must exist an equal marking in  R ( D, mu sub {D} ) . But all markings with  mu ( s , r sub {A}, r sub {B} ) = (0, 0, 0) are of the form  (0, 0, 0, mu ) with  mu \(mo R ( B, mu sub {B} ) , so  R ( A, mu sub {A} ) \(ib R ( B, mu sub {B} ) .

Thus, this construction shows the following.

THEOREM 5.10
The subset problem for Petri net reachability sets is reducible to the equality problem for Petri net reachability sets.
These three theorems then lead to the following.
THEOREM 5.11
The following problems are undecidable.

  1. The polynomial graph inclusion problem

  2. The subset problem for Petri net reachability sets

  3. The equality problem for Petri net reachability sets
These theorems and their proofs are due to Hack [1975a; 1975c].

Section 5.6. Complexity of the Reachability Problem

The undecidability of the subset and equality problems for Petri net reachability sets creates the possibility that the reachability problem itself is also undecidable. However, at the moment, the decidability (or undecidability) of the reachability problem is open. There is currently neither an algorithm to solve the reachability problem nor a proof that such an algorithm cannot exist.

In 1977, a ``proof'' of the decidability of the reachability problem was presented at the ACM Symposium on Theory of Computing [Sacerdote and Tenney 1977]. However, this ``proof'' has several serious flaws, and attempts to correct them, to produce a correct proof, have been unsuccessful. Still the prevailing feeling is that the reachability problem is decidable -- it is believed that an algorithm does exists and will be discovered in time.

Assuming that an algorithm to solve the reachability problem does exist, it is likely to be very complex. The obvious question is, If an algorithm to solve the reachability problem exists, how complex must it be? Some bounds on this complexity can be established without reference to any specific algorithm

Lipton [1976] has shown that any algorithm to solve the reachability problem will require at least an exponential ( 2 sup { c cdot n } ) amount of space for storage and an exponential amount of time. The exponent ( n ) is a measure of the size of the problem and in Lipton's case reflects the number of places and their interconnections to transitions.

Lipton proved that exponential space is necessary by showing that a Petri net can be constructed in which a place acts as a counter of the numbers  0, 1, ..., 2 sup {2 sup {n}} . Representing this in the reachability problem algorithm would require at least  roman log sub {2} (2 sup {2 sup {n}} ) = 2 sup {n} bits. Just as important is that his construction uses at most  h cdot n places (for some constant  h ).

Lipton's proof hinges on the ability to create a net to count to  2 sup {2 sup {n}} in only  h cdot n places. Part of the constraints is a need to test this place for zero. Petri nets, of course, have been designed so that there is no direct way to test for zero. However, a common technique used with Petri nets to allow zero testing is to use two places  p and  p prime such that  mu ( p ) + mu ( p prime ) is a constant. If we know that  mu ( p ) + mu ( p prime ) = k , then we can test for  mu ( p ) being zero by testing if  mu ( p prime ) has  k tokens; if  mu ( p prime ) has  k tokens, then  mu ( p ) has zero tokens and vice versa. A place can be tested for nonzero by using it in a self-loop. Note that to maintain this ability we must maintain the constant nature of  mu ( p ) + mu ( p prime ) ; that is, the net must be conservative, at least with respect to these two places.

For small numbers  k one can test if the marking of a place is  k by having the place be an input to a transition  k times (Figure 5.15). However, these arcs contribute to the size of the problem, and so we cannot do this in general. Lipton showed that if the constant sum of two places  ( p sub {k}, p sub {k} prime ) is  k and  k is a product of two smaller integer factors  k = k sub {1} cdot k sub {2} which are the constant sums of two other pairs of places ( p sub { k sub {1}}, p sub { k sub {1}} prime and  p sub { k sub {2}}, p sub { k sub {2}} prime ) and we can test  mu ( p sub { k sub {1}} ) = 0 and  mu ( p sub { k sub {2}} ) = 0 , then we can test if  mu ( p sub {k} ) = 0 . This allowed Lipton to build subnets such as Figure 5.16. These nets are then used to control multiplication nets, similar to the nets used to weakly compute the polynomial graph (see Figure 5.10). The test-for-zero subnet allows the Petri net to compute the exact product (not a weak product which is merely bounded by the real product).


Figure 5.15 . Testing a bounded place for a marking of 0, 1 or 2. All transitions must maintain the sum of the markings of  p and  p prime at 2.




Figure 5.16 . The form of the Petri nets which Lipton uses to construct a larger net which can test a larger counter for zero.


These simple nets allow Lipton to build a net, for a given  n , which can generate exactly  2 sup {2 sup {n}} tokens in a place ( p ) with zero tokens in  p prime and the ability to test  mu ( p ) for zero. The number of places used is only a constant factor times  n . The existence of a Petri net like this shows that the reachability problem requires exponential time and space and hence will be very expensive to solve.

The construction of a Petri net which can count up to  2 sup {2 sup {n}} has a very important corollary, too. The Petri net which is constructed is bounded, since the number of tokens in any given place cannot exceed  2 sup {2 sup {n}} . This means that any algorithm to determine boundedness of a Petri net must also require exponential time and space. Thus, even simple problems for Petri nets, while decidable, may require large amounts of time and space for solution.

It should be remembered that these are lower bounds on the worst-case behavior of an algorithm. It may be the case that many interesting problems can be decided for most Petri nets relatively efficiently. These complexity results show that even if an algorithm works very well most of the time there exists a Petri net which will take lots of time and space to analyze.

Although these are worst-case complexity results (which means the average case may be much better), they are also lower-bound results. We know that the reachability problem requires exponential space, at least. It may be that reachability is even worse than exponential. Rackoff [1976] has developed an algorithm for determining boundedness in exponential time, so the boundedness problem is known to be of exponential complexity. However, the reachability problem is simply known to be at least exponentially complex (and may not even be decidable).

A recent result by Mayr [1977] showed that the subset and equality problems for bounded Petri net reachability sets are of nonprimitive recursive complexity. These results indicate that some problems for Petri nets, while decidable, are computationally intractable.

Exercises

  1. Show that the reachability problem for ordinary Petri nets is equivalent to the single-place zero-reachability problem for self-loop-free Petri nets.

  2. For a Petri net  C sub {1} = (P sub {1}, T sub {1}, I sub {1}, O sub {1} ) , define a new Petri net  C sub {2} = (P sub {2}, T sub {2}, I sub {2}, O sub {2} ) with





    This introduces one extra place as an output of each transition.

    1. What is the meaning of the number of tokens in each of these places? For a live Petri net, what is the bound on the marking of these places?

    2. Suppose we add one extra transition with each  p sub {j} prime as an input and no output. Show that the net is live if and only if this new transition is live.

Section 5.7. Further Reading

Computability theory is an early part of the theory of computation and developed from the work of Turing, Kleene, Godel, and Church. Davis [1958] and Minsky [1967] offer good explanations of this work. Karp [1972] shows how reducibility can be used for decidability and complexity results.

The reachability problem first arose in [Karp and Miller 1968]; it was reported as a research question in [Nash 1973]. Preliminary results were reported in [Van Leeuwen 1974; Hopcroft and Pansiot 1976], but these do not generalize.

Most of the results in this chapter are due to the work of Hack [1974a; 1974c; 1975a; 1975c]. Hack has been one of the major researchers on decision problems for Petri nets. Other work on decision properties includes [Araki and Kasami 1976; Araki and Kasami 1977; Mayr 1977]. Complexity results have been produced by Lipton [1976], Rackoff [1976], and Jones et al. [1976] among others. Some related work not directly tied to Petri nets is [Cardoza 1975; Cardoza et al. 1976].

Section 5.8. Topics for Further Study

  1. A Petri net is reversible if for every transition  t sub {j} \(mo T there exists  t sub {k} \(mo T such that



    That is, for every transition there is another transition with inputs and outputs reversed. This allows any sequence of transitions to be ``undone'' by firing their complementary transitions in the opposite order. It has been stated [Hopcroft and Pansiot 1976] that the reachability and equivalence problems are decidable for reversible Petri nets. This theorem is based on work with commutative semigroups [Cardoza 1975]. Follow this statement up, showing the relationship between reversible Petri nets and commutative semigroups, and establish the decidability of reachability and equivalence for reversible Petri nets. Also consider the liveness problem, complexity issues, and the languages of reversible Petri nets to develop a theory of reversible Petri nets.

  2. There would seem to be a very useful connection between Petri nets and Presburger arithmetic. Presburger arithmetic is a theory of arithmetic using addition and subtraction with integers. It has been shown that it is possible to determine the truth or falseness of all statements formed from first-order quantifiers, equality, the operations of addition and subtraction, and integers. The original proof was presented in [Presburger 1929] and has been used as the basis of theorem-proving programs [Davis 1957; Cooper 1971]. The connection of Presburger arithmetic to semilinear sets was mentioned in [Ginsburg 1966; Ginsburg and Spanier 1966], and the relationship of semilinear sets to Petri net reachability has been mentioned in [Van Leeuwen 1974; Crespi-Reghizzi and Mandrioli 1974; Landweber and Robertson 1975; Hopcroft and Pansiot 1976; Jaffe 1977]. I suspect that Presburger arithmetic can be used to solve analysis problems for Petri nets. Investigate the usefulness of Presburger arithmetic in the analysis of Petri nets.
Home   Comments?