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.
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
have solutions for
and
nontrivial integer
,
,
and
?
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
,
,
,
and
which satisfy the theorem. The other way would be to prove (logically deduce)
that no such
,
,
,
and
can
exist. No one has yet done so.
However, assume that the problem were undecidable. Then it is not possible to
decide whether ,
,
,
and
exist which solve the equation. This means we could not logically deduce their
nonexistence from the axioms of mathematics and that we cannot produce
,
,
,
and
which solve the equation. But if we cannot produce
,
,
,
and
,
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
,
,
,
and
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 is
reducible to a problem
: An
instance of problem
can
be transformed into an instance of problem
. If
problem
is
decidable, then problem
is
decidable, and the algorithm for problem
can
be used to solve problem
. An
instance of problem
can
be solved by transforming it to an instance of problem
and
applying the algorithm for problem
to
determine the solution. Thus, if problem
is
reducible to problem
and
problem
is
decidable, then problem
is
decidable.
The contrapositive is also true: If problem is
reducible to problem
and
problem
is
undecidable, then problem
is
undecidable; for if problem
were decidable, the above procedure is a decision technique for problem
,
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 is
equivalent to problem
if
problem
is
reducible to problem
,
and problem
is
reducible to problem
. 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 is
determined to be of order
or
or
allowing for smaller terms and constant factors. In particular two general
classes of algorithms are important: those with polynomial complexity (
,
,
,
,
and so on) and those with nonpolynomial complexity (especially exponential,
,
and factorial,
).
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
numbers is of complexity
.
Thus algorithms with
complexity cannot be significantly improved on (in the asymptotic worst case).
Reducibility can be useful in determining complexity. If a problem can
be reduced to a problem
and
has
a complexity
,
then the complexity of
is
at most the complexity of
plus the cost of the transformation from
to
(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
to
problem
gives either an upper bound for the complexity of
(if
the complexity of
is
known) or a lower bound for the complexity of
(if
the complexity of
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 with
initial marking
have
been posed.
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 for
the reachability problem. Similarly the reachability problem is reducible to the
submarking reachability problem, by setting the subset
.
The single-place zero-reachability problem is reducible to the submarking
reachability problem by setting
and
.
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.
First, we show that the submarking reachability problem is reducible to the
zero-reachability problem. Assume we are given a Petri net
with initial marking
, a
subset of places
,
and a marking
. We
want to know if there exists
with
for
all
.
Our approach is to create a new Petri net
with initial marking
such that there exists
with
for
all
if
and only if
.
The construction of
from
is
quite straightforward. We start with
the
same as
. To
allow any place
not
in
to
become empty we add a transition
with input
and
null output. This transition can fire whenever there is a token in
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 in
, we
must assure that exactly
tokens are in
. To
assure this we create a new place
for
each
with an initial marking of
tokens and a transition
with input
and
null output. If there are exactly
tokens in
,
then this transition can fire exactly
times, reducing the markings of
and
to
zero. If the number of tokens in
is
not
,
then the transition
can
only fire the minimum of the two markings, and so tokens will be left in either
or
,
preventing the zero marking from being reached.
Figure 5.2 illustrates the two types of transitions introduced. Formally we
define by
To show that
if and only if there exists a
with
for
,
assume first that
exists in
.
Then in
we can also reach the marking
in the places
by firing only those transitions from
.
Now for each
,
we can fire
exactly
times, reducing both
and
to zero. Then we can fire
for each
as many times as necessary to put these to zero, so
.
Now assume ;
then there exists a sequence of transition firings
which leads from
to 0. This sequence will contain exactly
firings of
for
(to remove the tokens from
)
and some number of firings of
for
.
Note that these transition firings only remove tokens from
,
and since
is defined whenever
is defined for
(extra tokens never hurt), the sequence
with all
firings removed is also legal and will lead to a marking
with exactly
tokens in
for
.
Thus if
,
then
with
for
.
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
with initial marking
, we
wish to determine if
. We
construct, from
, a
new Petri net
with an additional place
such that there exists a marking
with
if
and only if
.
The construction of
defines
so
that at all times the number of tokens in
is
equal to the sum of the number of tokens in the places of
.
Thus if
,
then there are zero tokens in all places of
and
vice versa. We define the initial marking
by
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.
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.
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
or spread out uniformly to cover all
places in the ring. Thus a transition which needs three tokens from place
can pick up one from each of
,
,
and
rather than all three from
.
Similarly a transition which uses
both as an input and as an output (a self-loop) may input from
and output to
,
eliminating the self-loop.
Formally, for a general Petri net
with marking
,
we define a restricted Petri net
with marking
as follows. First define, for each
,
an integer
by
By construction, for any marking
which is reachable in
,
there exists a marking
of
such that
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].
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 with
initial marking
are
of concern here. A Petri net is live if each transition is live. A transition
is
live in a marking
if
for each
there exists a sequence
such that
is
enabled in
. A
transition
is
dead in a marking
if
there is no reachable marking in which it can fire.
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 ; if
,
then we must solve
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 can
be zero in any reachable marking for a Petri net
with initial marking
, we
construct a Petri net
with initial marking
,
which is live if and only if the zero marking is not reachable from
.
The Petri net is
constructed from
by
the addition of two places,
and
,
and three transitions,
,
,
and
. We
first modify all transitions of
to
include
as
both an input and an output. The initial marking
will include a token in
.
The place
is
a ``run'' place; as long as the token remains in
the
transitions of
can
fire normally. Thus any marking which is reachable in the places of
in
is
also reachable in
.
Transition
is
defined to have
as
its input and a null output. This allows the token in
to
be removed, disabling all transitions in
and
``freezing'' the marking of
.
(Note that all transitions of
are
in conflict and, by construction if not by definition, that no more than one
transition can fire at a time.)
The place and
transition
allow the net
to
reach any reachable marking and then for
to
fire and freeze the net at that marking. Now we need to see if place
is
zero. We introduce a new place
and
a transition
which has
as
its input and
as
its output. If
can
ever become zero, this transition is not live; in fact the entire net is dead if
transition
fires in that marking. Hence if
can
be zero, the net is not live. If
cannot be zero, then
can
always fire, putting a token in
. In
this case we must put a token back in
and
assure that all transitions in
are
live. We must be sure that
is
live even if
is
not live. This is accomplished by a transition
which ``floods'' the net
with tokens, assuring that every transition is live if a token is ever put in
.
Transition
has
as
its input and every place of
(all
in
and
and
) as
output. This construction is illustrated in Figure 5.6.
Now, if a marking is
reachable in
with
,
then the net
can
also reach this marking on the place of
by
executing the same sequence of transition firings. Then
can
fire, freezing the
subset. Since
,
transition
cannot fire and
is
dead. Thus if
can
become zero, then
is
not live.
Conversely, if is
not live then, a marking
must
be reachable in which
and
there is no reachable state in which
has
a token. [If
has
a token,
is
enabled, and
can
be fired repeatedly enough times to enable any (or all) transitions, and so the
net is live.] If
has
no token and cannot get any, then the marking of
must
also be zero. Thus if
is
not live, then a marking is reachable in which the marking of
is
zero.
On the basis of this construction, we have the following.
Now we need to show the following.
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 -dead
submarkings. A Petri net is not live for a transition
if
and only if any marking is reachable in which the transition
is
not fireable and cannot become fireable. A marking of this sort is called
-dead.
For any marking
we
can test if it is
-dead
by constructing the reachability tree with
as
the root and testing if transition
can
fire anywhere in the tree. If it cannot then
is
-dead.
Checking for liveness of
then
requires checking if any
-dead
marking is reachable.
In general, however, there may be an infinite number of -dead
markings and an infinite set of markings in which to find the
-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
is
-dead,
then any marking
is
also
-dead.
(Any firing sequence possible from
is
also possible from
, so
if
could lead to the firing of
, so
could
.)
Second, the markings of some places will not affect the
-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
to
indicate that an arbitrarily large number of tokens can be in this place without
affecting the
-deadness
of the marking. Now since any
is
-dead
if
is
-dead,
we need not consider those places
with
.
This means we use the submarking reachability problem with
.
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 -dead,
but they can be finitely represented by the set
.
Hack [1974c; 1975c] has shown that there exists for a Petri net a
finite set
of
markings (extended to include
)
such that
is
live if and only if no marking in
is
reachable. If a marking of
contains
,
submarking reachability is implied.
Further, can
be effectively computed. Since
is
finite, the non-
-components
of the markings have an upper bound
.
This bound
is
characterized as the smallest number such that for any marking
with
for
all
, if
is
-dead,
then the submarking
,
with
if
and
if
, is
-dead.
With this characterization of
, we
can construct
as
follows.
From these two theorems, we have the following.
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
with marking
and
with marking
it
is undecidable if
.
Hack [1975a] later strengthened this to show that it is undecidable if
.
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.)
The equation is
a Diophantine equation. In general it will be a sum of terms
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.
Now we need to show that Petri nets can (in some sense) compute the value of
a polynomial . We
have carefully limited the polynomial
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
are
encoded by
tokens in
for
.
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
tokens, where
.
This Petri net will weakly compute the value .
Weak computation means that the value computed will not exceed
but
may be any (nonnegative) value less than
.
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
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, and
, 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
and
,
transition
first fires, moving one token from
to
.
This token enables transition
,
which can now copy
tokens from place
,
putting them in
and
putting
tokens in
,
the output place. Now
can
fire, putting the token in
back
into
.
This enables
,
which can copy the
tokens from
back into
.
This entire process can be repeated exactly
times, each time putting
tokens in
.
Then the marking of place
has
been reduced to zero, and the net must stop. The total number of tokens in place
is
then the product of
and
.
The above case is the best case, in the sense that the number of output
tokens is exactly .
However, the token in
enables both transitions
and
, and
it is possible for
to
fire before all
tokens have been copied from
to
and
been added to
. In
this case, the number of tokens deposited in
will be less than
.
Since
can
fire no more than
times for each firing of
and
can
fire no more than
times, we can guarantee that the number of tokens in
never exceeds
,
but because of the permissive nature of transition firings, we cannot guarantee
that the number of tokens in
will actually equal
; it
could be less. Thus, this Petri net weakly computes the product of
and
.
Now to weakly compute a term
which is the product
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
.
Figure 5.12 then shows how a polynomial 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
subnets for each term have been merged together, giving a total value which is
the sum of each term.
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 and
record that value in the places
. A
transition
is
created for each
with
null input and outputs to
and
every place which is an input corresponding to
in
a term
which uses
.
Thus, in the polynomial
we
would have a transition
with outputs to
and
to the
inputs of the two terms,
and
,
which use
;
would output to
and
to the
input of the term
.
These transitions can fire an arbitrary number of times, creating any value
in .
Thus, for every
a
marking
is
reachable with
and
.
The value
can
be achieved by first firing
times, putting
tokens in
,
then firing
times, and so on until
has
fired
times. The subnet for each term
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
and
, we
wish to determine if
.
To prevent this problem we add two new places
and
to
(giving
)
and
and
to
(giving
).
In
,
,
and
are not used for any transitions, and initially
is empty and
is marked with one token. In
,
is a ``run'' place. It is initially marked, and every transition in
is modified to include
as both an input and an output. Thus, as long as the token remains in
,
the net
can function as before. A new transition transfers the enabling token from
to
,
disabling all transitions in
and ``freezing'' the marking. Now we add two new transitions for each internal
place in
.
For each internal place
whose marking is unimportant, one transition has places
and
as
inputs and only
as an output (allowing the marking in
to
be decreased by one), and another transition has
as input and both
and
as
outputs (allowing the marking in
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.
The reachability sets of
and
are as follows. For
,
This concludes our demonstration of the following.
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 and
and
wish to determine if
(the subset problem). We now show that two Petri nets
and
can
be defined such that
if
and only if
.
The basis for this construction is the fact that
Both and
are
constructed from a common subnet,
. The
net
encodes the reachability sets of both
and
in
such a way as to produce their union. Figure 5.14 illustrates the basic
construction. The
places
act
as either the
places of net
or
the
places of net
.
Originally they are unmarked. Two new places
and
are
added as ``run'' places for net
and
net
,
respectively. All transitions of net
are
modified to include
as
both an input and an output; all transitions of net
are
modified to include
as
both an input and an output.
Now, one more place, , is
added and two new transitions,
and
.
The initial marking for this entire net (including
and
as
subnets with shared places; places
,
,
and
;
and transitions
and
) is
one token in
and
zero tokens elsewhere. Transition
has
place
as
its input and as output produces the initial marking for net
plus
a token in
;
transition
has
place
as
its input and produces the initial marking for net
plus a token in
.
Thus, if
fires, then the subnet
has
its initial marking, and all of its transitions can fire as normal since there
is a token in
.
However, subnet
is
completely disabled, since there is no token in
. If
fires first, then the subnet
can
operate, and
is
disabled. The set of firing sequences for
is
then any sequence of the form
The net is
obtained from
by
adding one new transition,
.
Transition
has
place
as
its input and no output. Notice that
can
fire only if transition
was
the first to fire; if transition
fires first, then
will be empty, and
cannot fire.
The net is
constructed from
by
adding a new transition,
.
Transition
has
place
as
its input and no output. Transition
can
fire only if
was
the first to fire: Notice that net
is
constructed from
,
not (directly) from
. So
has
both transition
and
transition
.
Now let us examine the reachability sets of the Petri nets ,
,
and
.
The reachability set of
is
all markings of the form
Now, if ,
the last class in
[markings of the form
with
] is
included in the last class of
[markings of the form
with
].
Since all other markings are the same,
Thus, this construction shows the following.
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 ()
amount of space for storage and an exponential amount of time. The exponent
(
) 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 .
Representing this in the reachability problem algorithm would require at least
bits. Just as important is that his construction uses at most
places (for some constant
).
Lipton's proof hinges on the ability to create a net to count to in
only
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
and
such that
is
a constant. If we know that
,
then we can test for
being zero by testing if
has
tokens; if
has
tokens, then
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
;
that is, the net must be conservative, at least with respect to these two
places.
For small numbers one
can test if the marking of a place is
by
having the place be an input to a transition
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
is
and
is
a product of two smaller integer factors
which are the constant sums of two other pairs of places (
and
)
and we can test
and
,
then we can test if
.
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).
These simple nets allow Lipton to build a net, for a given ,
which can generate exactly
tokens in a place (
)
with zero tokens in
and
the ability to test
for
zero. The number of places used is only a constant factor times
. 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 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
.
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
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