Home Up Questions?

Chapter 7. Extended and Restricted Petri Net Models

In Chapter 3 we demonstrated that Petri nets can be used to model a wide variety of systems: computer hardware and software, chemical, social, and so on. However, this large set of examples only shows that Petri nets can model some systems; there may be systems which cannot be properly modeled as Petri nets. That is, there may be limits on the modeling power of Petri nets.

In addition, in Chapter 5 we have shown that not all analysis questions are decidable for Petri nets. The inclusion and equivalence problems for Petri net reachability sets and for Petri net languages are undecidable, but these problems may be very important for producing optimal Petri nets. Even those analysis questions which are decidable are very difficult, meaning that they require large amounts of computation.

In this chapter, we investigate the suggestions which have been made to overcome these two limitations on Petri nets: limitations on Petri net modeling power and limitations on Petri net decision power. We look first at some of the extensions to the Petri net model which have been suggested. Extending the Petri net model should increase the modeling power of Petri nets but may also decrease the decision power. The effects of any extension on the decision power of the extended model must be carefully considered.

Having then seen that extending the Petri net model may tend to reduce decision power, we also consider how decision power can be increased by restricting the Petri net model. Various subclasses of the Petri net model have been suggested. These models are produced by restrictions on the structure of the Petri net. We must examine the effect of these restrictions on both modeling power and decision power.

This investigation shows how modeling and decision power can be traded, one for the other, and also indicates the limits of both for the Petri net model.

Section 7.1. Limitations of Modeling with Petri Nets

Several researchers who have used Petri nets to model systems have found them too simple and limited to easily model real systems. Thus, there has been a marked tendency to extend the model to make it easier to use. These extensions have been of several types.

Patil [1970a] suggested extension of Petri nets to include constraints. A constraint is a set of places. The firing rule is modified to allow a transition to fire if and only if the resulting marking does not have all of the places which are in a constraint simultaneously marked. For example, if  { p sub {1}, p sub {4} } is a constraint set, then either  p sub {1} or  p sub {4} must be empty at all times; if  p sub {1} is marked, then a token cannot be put in  p sub {4} until all tokens in  p sub {1} are removed and vice versa.

Noe, in his model of the CDC 6400 operating system [Noe 1971], introduced a different extension: the exclusive-OR transition (Figure 7.1). Normally, a Petri net transition fires when all of its inputs have tokens; this is called AND logic, since we must have tokens in the first input and tokens in the second input and tokens in the third input and so on. The exclusive-OR transition can fire if and only if exactly one of its inputs has tokens and all the others have zero tokens. Thus, the enabling rule is that the first input have a token or the second input have a token (but not both). When the transition fires, it removes a token only from the input with tokens.


Figure 7.1 . An exclusive-OR transition. Transition  t sub {j} can fire only if either  p sub {i} or  p sub {k} has a token and the other does not.


A similar extension was used by Baer in his model of a compiler [Baer 1973b]. Baer introduced switches (Figure 7.2). A switch is a special transition with a special input called the switch input and exactly two outputs (one labeled  e for empty and the other labeled  f for full). A switch transition fires when it is enabled (ignoring the state of the special switch input). When it fires a token is put in the output labeled  e if the switch input is empty and a token is put in the output labeled  f if the switch input is full. Thus, firing a switch transition will result in either one of two markings, depending on the state of the switch. A token is removed from the switch input if it had one, so that the switch input is empty after the switch transition is fired.


Figure 7.2 . Firing a switch transition. The box-shaped place is the switch input. (a) Empty switch. (b) Full switch.


These extensions to Petri nets were created for solving specific problems which the researchers encountered in their attempts to model real systems. However, the emphasis of their work was modeling, not the theoretical power of Petri nets, so no attempt was made to show that these extensions were either necessary or sufficient to handle general modeling problems. In fact, in all of these cases, the nets involved were safe, and hence the reachability set is finite, meaning that these nets could be represented by finite state machines, which we have seen (Section 3.3.1) can be easily represented as ordinary Petri nets. Thus, in these cases, these ``extensions'' were not necessary, merely convenient. We have also seen, in Section 5.3, that many ``extensions'' to the restricted Petri net model, such as multiple arcs and self-loops, are not in fact extensions but merely convenient.

So the question remains as to what, if any, are the limitations of Petri nets. The answer to this question was found as the result of asking similar questions about Dijkstra's P and V operations on semaphores.

Dijkstra defined his P and V operations on semaphores to facilitate synchronization and communication in systems of cooperating processes [Dijkstra 1968]. A semaphore can be thought of as an integer variable which only takes on nonnegative values. A V operation on a semaphore  S increases the value of the semaphore by one,  S = S + 1 . A P operation, on the other hand, decrements  S by one as long as the result is nonnegative; the process must wait until  S can be decremented before it continues. The relationship between semaphores and Petri nets was examined in Section 3.4.8.

Since P and V operations were proposed as the mechanism for solving all synchronization problems between programs, questions naturally arose as to their completeness, that is, their ability to solve all possible coordination problems. Patil [1971] set out to prove that P and V operations are not powerful enough to solve all coordination problems. His approach was quite simple: He created a synchronization problem which cannot be solved with P and V operations. The problem posed was the cigarette smokers' problem.

The cigarette smokers' problem consists of (at least) four processes: an agent and three smokers. Each smoker continuously makes a cigarette and smokes it. But to make a cigarette, three ingredients are needed: tobacco, paper, and matches. One of the processes has paper, another tobacco and the third has matches. The agent has an infinite supply of all three. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient can then make and smoke a cigarette, signaling the agent upon completion. The agent then puts out another two of the three ingredients and the cycle repeats.

In terms of semaphores, the problem is posed by associating a semaphore with each ingredient. These semaphores are initially zero. The agent will increment two of the three semaphores by V operations, and then wait on a done semaphore. The appropriate smoker process must decrement the two semaphores (by P operations), make and smoke the cigarette, and increment the done semaphore. The problem is to define the code for the smoker processes to determine which of the three processes should proceed; the agent is fixed and cannot be changed.

Figure 7.3 illustrates the obvious ``solution.'' The problem with this ``solution'' is quite simple: Suppose the agent puts out tobacco and paper [ V(t); V(p) ]. Then the smoker with paper may grab the tobacco [ P (t) ] and the smoker with tobacco may grab the paper [ P (p) ], resulting in a deadlock.


Figure 7.3 . The cigarette smokers' problem.


Patil proved that no sequence of P and V operations can correctly solve this problem. This was shown by proving that all P and V ``solutions'' can be modeled as Petri nets of a certain kind (each transition has at most two inputs) but that the solution is a Petri net of another kind, and there is no way to convert a net of one kind into a net of the other kind without introducing the danger of deadlock.

There were some problems with Patil's solution -- specifically dealing with arrays of semaphores (see [Parnas 1972]) -- but the concept is correct. Kosaraju [1973] and Agerwala and Flynn [1973] followed up on Patil's work to produce a problem which cannot be solved by P and V operations or by Petri nets. This same limitation had been earlier discovered by Keller [1972].

The problem posed by Kosaraju and Agerwala and Flynn is quite real. Assume that we have two producer processes and two consumer processes. One producer process  P sub {1} creates items for the first consumer process  C sub {1} , and the other producer  P sub {2} produces for the other consumer  C sub {2} . Items which are produced but not yet consumed are placed in a buffer, buffer  B sub {1} for  (P sub {1}, C sub {1} ) and  B sub {2} for  (P sub {2}, C sub {2} ) . The transmission from the buffers to the consumers is over a shared channel. The channel can only transmit one item at a time but can transmit from either buffer to either consumer. The producers merely put items into the buffers; the consumers must coordinate the use of the channel between themselves. The controlling consumer tells the channel to fetch an item from the appropriate buffer. This is sketched in Figure 7.4.


Figure 7.4 . The buffered producer/consumer with a shared channel.


The major problem with this system is the allocation of the channel. The producer/consumer pair  (P sub {1}, C sub {1} ) are required to have priority over  (P sub {2}, C sub {2} ) for use of the channel. Specifically, the channel is never to transmit items from buffer  B sub {2} to consumer  C sub {2} as long as buffer  B sub {1} is nonempty. This priority rule prevents this system from being modeled as a Petri net.

The proof is relatively straightforward. Assume that we are in a state  mu with items in both buffer  B sub {1} and buffer  B sub {2} . Now, if producer  P sub {1} takes a break, then all items from buffer  B sub {1} will eventually be transmitted to consumer  C sub {1} , and buffer  B sub {1} will be empty. This will allow an item from buffer  B sub {2} to be moved to consumer  C sub {2} . Thus there exists a path from  mu to a state  mu prime in which consumer  C sub {2} can use the channel. Now, if instead the producer  P sub {1} produces an extra  k items, then we will be in state  mu + k rather than  mu . But because of the permissive nature of Petri net firings, the sequence of firings which took us from  mu to  mu prime will still be enabled and will take us from  mu + k to  mu prime + k . And since consumer  C sub {2} could use the channel in  mu prime and Petri nets are permissive, consumer  C sub {2} can still use the channel, despite the presence of  k items in buffer  B sub {1} . Thus, the permissive nature of Petri net firings does not allow this priority system to be modeled correctly.

More specifically, the limitation on Petri net modeling is precisely the inability to test for exactly a specific marking in an unbounded place and take action on the outcome of the test. This is commonly stated as an inability to test for a zero marking in a place, and so this property is known as zero testing [Keller 1972]. Petri nets cannot test an unbounded place for zero. [If the place is bounded, zero can be tested. For a bounded place  p sub {i} with bound  k , we can create a complement place  p sub {i} prime such that the sum  mu ( p sub {i} ) + mu ( p sub {i} prime ) is constant at  k for all reachable markings. This allows us to test if  mu ( p sub {i} ) is zero by testing if  mu ( p sub {i} prime ) is  k .]

Exercises

  1. Draw a Petri net model of the ``solution'' to the cigarette smokers' problem of Figure 7.3. Show that this net is not live. Create a Petri net which can solve the cigarette smokers' problem. How does this second net differ from the first?

Section 7.2. Extensions

How does this limitation of Petri net modeling power relate to the extensions of Petri nets which have been suggested? All of the suggested extensions are directed at creating an ability in Petri nets for zero testing.

The simplest extension to Petri nets which allows zero testing is inhibitor arcs. An inhibitor arc is illustrated in Figure 7.5. An inhibitor arc from a place  p sub {i} to a transition  t sub {j} has a small circle rather than an arrowhead at the transition. This notation is borrowed from switching theory where the small circle means ``not.'' The firing rule is changed as follows: A transition is enabled when tokens are in all of its (normal) inputs and zero tokens are in all of its inhibitor inputs. The transition fires by removing tokens from all of its (normal) inputs.


Figure 7.5 . An extended Petri net with an inhibitor arc.


Thus in the extended Petri net of Figure 7.5, transition  C sub {2} can fire only if there is a token in  b sub {2} and  p sub {4} and zero tokens in  b sub {1} . This net is a solution to the priority shared channel problem which Kosaraju defined to show the limitations of Petri nets.

Petri nets with inhibitor arcs are intuitively the most direct approach to increasing the modeling power of Petri nets. It is also the case that all other extensions to Petri nets which have been suggested either are not true extensions (that is, they are in fact equivalent to ordinary Petri nets) or are equivalent to Petri nets with inhibitor arcs. We discuss several suggested extensions below to illustrate this point.

7.2.1. Constraints

Constraints were proposed by Patil [1970a] to improve the modeling power of Petri nets. In Patil's context, constraints were only meant to make the modeling easier but not to increase modeling power, because the places in Patil's work were all bounded. However, the definition of constraints is not limited to bounded Petri nets, and for the more general class of Petri nets, they are equivalent to inhibitor arcs.

To show the equivalence of constraints and inhibitor arcs, assume we have a Petri net  C = (P, T, I, O) with a constraint  Q \(ib P . We must guarantee that all places in  Q are not marked in any reachable marking. The only way this could happen would be for a transition  t sub {j} to fire putting tokens in those places of the constraint which were not marked before the transition fired. Thus, for each transition  t sub {j} with output places which are in the constraint, we must guarantee that at least one of the members of the constraint will not be marked after the transition fires. To assure this, we create a new transition  t sub {j,k} for every place  p sub {k} in the constraint  Q but not in  O ( t sub {j} ) . The transition  t sub {j,k} is identical to  t sub {j} except that it also has an inhibitor arc from  p sub {k} to  t sub {j,k} . The effect of firing  t sub {j,k} is the same as firing  t sub {j} , and if  t sub {j} can be fired without violating a constraint, then at least one of the  t sub {j,k} can fire.

As an example of this construction, consider the Petri net of Figure 7.6. If we impose the constraint  { p sub {3}, p sub {7} } (that is, no marking should have  p sub {3} and  p sub {7} simultaneously marked), then the equivalent Petri net with inhibitor arcs is shown in Figure 7.7.


Figure 7.6 . A Petri net with a constraint  { p sub {3}, p sub {7} } . The constraint means that tokens are not allowed in both  p sub {3} and  p sub {7} in any reachable marking.




Figure 7.7 . A Petri net with inhibitor arcs corresponding to the Petri net with constraints of Figure 7.6. The inhibitor arcs assure that tokens cannot simultaneously be in places  p sub {3} and  p sub {7} .


The transformation from inhibitor arcs to constraints is somewhat more difficult. We cannot simply insist that no output of a transition can be marked at the same time as an inhibitor input, since tokens can be placed in the output by other transitions. We must concentrate on the transition. This requires splitting each transition  t sub {j} into two transitions  t sub {j} prime and  t sub {j} prime prime and a place  p sub {j} prime . We define  I ( t sub {j} prime ) = I ( t sub {j} ) (without the inhibitor arcs) and  O ( t sub {j} prime prime ) = O ( t sub {j} ) . The place  p sub {j} prime represents the firing of  t sub {j} , so  O ( t sub {j} prime ) = { p sub {j} prime } = I ( t sub {j} prime prime ) . This is illustrated in Figure 7.8. Now, for each place  p sub {i} which is an inhibitor input to  t sub {j} , we define a constraint  { p sub {i}, t sub {j} prime } . This assures that the transition cannot fire if the marking of  p sub {i} is nonzero.


Figure 7.8 . Converting a transition into a start and end transition with a place representing the transition firing.


7.2.2. Exclusive-OR Transitions and Switches

An exclusive-OR transition  t sub {j} with input  I ( t sub {j} ) requires that one and only one of its inputs be nonzero to enable the transition. This is equivalent to a set of transitions, one for each element in  I ( t sub {j} ) . Each transition has one (normal) input, and the rest of the inputs are inhibitor arcs. Figure 7.9 gives an example.


Figure 7.9 . Converting from (a) exclusive-OR transitions to (b) inhibitor arcs.


Switches can also be easily transformed into inhibitor arcs. See Figure 7.10.


Figure 7.10 . Converting (a) switches into Petri nets with (b) inhibitor arcs.


It is not immediately obvious how inhibitor arcs can be converted into either switches or exclusive-OR transitions, but it is certainly the case that they can be.

7.2.3. Other Extensions

Two other major extensions to Petri nets have been suggested. Priorities can be associated with the transition such that if  t sub {i} and  t sub {k} are both enabled, then the transition with the highest priority will fire first [Hack 1975c]. Time Petri nets [Merlin 1974] associate with each transition  t sub {j} two times  tau sub {1,j} and  tau sub {2,j} . A transition  t sub {j} can fire only if it has been enabled for at least time  tau sub {1,j} , and it must fire before  tau sub {2,j} if it is enabled. Both of these extensions can be used to test for zero.

In the case of priorities, we can easily test if a place  p sub {i} is zero. This is shown in Figure 7.11. If we put a token into place  p sub {i} = 0 ? and define the priority of transition  t sub {1} to be higher than the priority of transition  t sub {2} , then we will get a token in one of the two places at the right depending on the marking of place  p sub {i} . This results from the fact that transition  t sub {1} can fire only if it is enabled, and it is enabled only if place  p sub {i} has a token. If  t sub {1} cannot fire because  p sub {i} is empty, then, and only then, will transition  t sub {2} fire.


Figure 7.11 . Using priorities to test if the marking of a place  p is zero or nonzero. Transition  t sub {1} has priority over transition  t sub {2} .


Hack has shown complete constructions for converting Petri nets with priorities to Petri nets with inhibitor arcs and vice versa [Hack 1975c]. Time Petri nets can also test a place for zero by simulating priorities. If we have two transitions  t sub {j} and  t sub {k} and we set  tau sub {2,j} < tau sub {1,k} , then transition  t sub {j} has priority over transition  t sub {k} since  t sub {j} must fire (if it is enabled) before  t sub {k} would be allowed to fire.

Section 7.3. Extended Petri Nets and Register Machines

We have shown that the suggested extensions to the Petri net model all allow a place to be tested for zero. How is this important to the decision power of a Petri net? Does it affect our ability to analyze Petri nets?

Zero testing decreases the decision power of Petri nets. Agerwala [1974a], Hack [1975c], Thomas [1976], and others have shown that adding the ability to test for zero to a Petri net model allows a Petri net to simulate a Turing machine. Thus a Petri net with zero testing, produces a modeling scheme which can model any system. Also, however, almost all analysis questions for Petri nets become undecidable, since they are undecidable for Turing machines.

The proof of the equivalence of extended Petri nets and Turing machines is relatively simple. It is easiest to give in terms of the register machines of Shepardson and Sturgis [1963] or the program machines of Minsky [1967].

A register machine is a computer-like machine with a number of registers which are used to store arbitrarily large numbers. A program is written to manipulate the registers. The program is a sequence of instructions such as ``increase register  n by 1,'' ``decrease register  n by 1 (only if register  n is not 0),'' ``jump to statement  s if register  n is not zero,'' and so on. For example, the following is a program to add the contents of register 2 to register 1.

  1. If register 2 is zero, go to instruction 5.

  2. Subtract 1 from register 2.

  3. Add 1 to register 1.

  4. Go to instruction 1.

  5. Halt.

Shepardson and Sturgis have shown that a register machine with the following instructions is equivalent to a Turing machine.

  1.  P ( n ) : Increase register  n by 1.

  2.  D ( n ) : Decrease register  n by 1 (register  n not zero).

  3.  J ( n ) [ s ] : Jump to statement  s if register  n is zero.

Thus, if a register machine can be converted into an equivalent extended Petri net, we see that extended Petri nets are equivalent to register machines. This conversion is relatively straightforward.

To represent a register machine as an extended Petri net, we represent the  n registers used in a program by  n places,  p sub {1} prime , p sub {2} prime , ..., p sub {n} prime . We also use  s + 1 places to represent the position of the program counter either before statement 1 (the initial marking) or after statement  i , for  i = 1, ..., s , in a program with  s statements. Each instruction in the program is represented by a transition. Figure 7.12 shows how each of the three instructions above would be represented as a transition in an extended Petri net. This shows that a register machine can be converted into an extended Petri net and therefore that an extended Petri net is equivalent to a Turing machine. This equivalence to Turing machines destroys any hope of being able to analyze extended Petri nets. However, it does prove that extended Petri nets can model any system (or at least any computable system). Thus we see that an increase in modeling power, in this case, results in a definite decrease in decision power.


Figure 7.12 . Converting an instruction (at location  i ) for a register machine to a transition in an extended Petri net using inhibitor arcs. (a)  P ( n ) : Increase register  n by 1. (b)  D ( n ) : Decrease register  n by 1 (register  n must be nonzero). (c)  J ( n ) [ s ] : Jump to statement  s if register  n is zero.


Also notice that the key point in the proof of equivalence of extended Petri nets and register machines and Turing machines is the ability to test a single place for zero. Thus, all of the extensions which have been suggested -- constraints, exclusive-OR transitions, switches, priorities, timings, and inhibitor arcs -- extend the Petri net model to the level of Turing machines.

There have been other suggestions for extensions which do not raise Petri nets to the level of Turing machines. Self-loops and multiple input and output arcs were first suggested as extensions but, as seen in Section 5.3, are in fact equivalent to restricted Petri nets. Similarly, allowing inclusive-OR inputs, inclusive-OR outputs, or exclusive-OR outputs would not increase the modeling power of Petri nets.

In general, it seems that any extension which does not allow zero testing will not actually increase the modeling power (or decrease the decision power) of Petri nets but merely result in another equivalent formulation of the basic Petri net model. (Modeling convenience may be increased.) At the same time, any extension which does allow zero testing will increase the modeling power to the level of Turing machines and decrease decision power to zero. Thus Petri net extensions would seem to have few practical advantages for analysis.

Section 7.4. Subclasses of Petri Nets

The objective of extending Petri nets is to increase their modeling power; an unfortunate side effect is that the decision power of extended Petri nets is greatly reduced. The decision power of normal Petri nets is of questionable value anyway due to its complexity and expense. (Remember the results of Section 5.8 on the complexity of the reachability and boundedness problems.) This has resulted in some investigations of subclasses of Petri nets. The objective of these studies is to determine reasonable structural restrictions on Petri nets which will increase the decision power of the restricted Petri net models while not overly restricting modeling power.

Much can be done with Petri net subclasses. The goal of this part of Petri net research is quite simple: Define a subclass of Petri nets which can model a large class of systems (all or almost all interesting ones) and yet still has simple analysis procedures (at least for the interesting problems). It is also necessary that there exist a simple test for determining if a Petri net is a member of the defined subclass. The subclasses which have been defined are all syntactic or structural subclasses; one can easily examine a Petri net structure to determine if it is a member of the specified subclass. This is in distinction to subclasses which might be defined according to dynamic properties, such as, for example, persistent Petri nets [Landweber and Robertson 1975] or bounded Petri nets. These subclasses might have very nice properties, but it may be quite difficult to determine if an arbitrary given Petri net is a persistent or bounded Petri net.

Only two major subclasses of the Petri net model have been widely studied: state machines and marked graphs. In addition, Hack [1972] has studied a subclass called free-choice Petri nets and has suggested that another subclass, simple Petri nets, might have good decision properties. We present each of these classes and indicate their major properties, advantages, and disadvantages.

7.4.1. State Machines

A state machine is a Petri net in which each transition is restricted to having exactly one input and one output.

DEFINITION 7.1
A state machine is a Petri net  C = (P, T, I, O) such that for all  t sub {j} \(mo T, | I ( t sub {j} ) | = 1 and  | O ( t sub {j} ) | = 1 .

Several properties of state machines are immediately obvious. First, a state machine is strictly conservative. This means that the number of tokens in the state machine never changes, resulting in a finite system. This implies that the reachability tree for a state machine is finite, and hence all analysis questions are decidable for state machines. In fact, a state machine is equivalent to the finite state machine automata of automata and formal language theory (see Section 3.3.1). Thus, these models are of limited interest despite their high decision power, due to the limited modeling power of finite state machines.

7.4.2. Marked Graphs

Another subclass of Petri nets which is often mentioned in the literature is the class of marked graphs. A marked graph is a Petri net in which each place is an input for exactly one transition and an output of exactly one transition. Alternatively, we can say that each place has exactly one input and one output.

DEFINITION 7.2
A marked graph is a Petri net  C = (P, T, I, O) such that for each  p sub {i} \(mo P, | I ( p sub {i} ) | = | { t sub {j} | p sub {i} \(mo O ( t sub {j} ) } | = 1 and  | O ( p sub {i} ) | = | { t sub {j} | p sub {i} \(mo I ( t sub {j} ) } | = 1 .

Marked graphs are duals of state machines, in the graph-theoretic sense of the word, since transitions have one input and one output in state machines, while places have one input and one output in marked graphs. They are also duals from the point of view of modeling. A state machine can easily represent conflicts by a place with several outputs but cannot model the creation and destruction of tokens needed to model concurrency or the waiting which characterizes synchronization. Marked graphs, on the other hand, can model concurrency and synchronization but cannot model conflict or data-dependent decisions.

The properties which have been investigated for marked graphs have been liveness, safeness, and reachability. In the investigation of these properties, the major structural parts of a marked graph of interest are its cycles. A cycle in a marked graph is a sequence of transitions  t sub {j sub {1}} t sub {j sub {2}} t sub {j sub {3}} ... t sub {j sub {k}} such that for each  t sub {j sub {r}} and  t sub {j sub {r + 1}} in the sequence there is a place  p sub {i sub {r}} with  p sub {i sub {r}} \(mo O ( t sub {j sub {r}} ) and  p sub {i sub {r}} \(mo I ( t sub {j sub {r + 1}} ) and  t sub {j sub {1}} = t sub {j sub {k}} . A cycle is thus a closed path from a transition back to that same transition.

For example, in the marked graph of Figure 7.13, the sequence  t sub {1} t sub {2} t sub {1} is a cycle, as are  t sub {4} t sub {3} t sub {4} and  t sub {2} t sub {4} t sub {3} t sub {1} t sub {2} .


Figure 7.13 . A marked graph.


The importance of cycles for marked graphs derives from the following theorem.

THEOREM 7.1
The number of tokens on a cycle of a marked graph does not change as a result of transition firings.
From this theorem, it is easy to show the following.
THEOREM 7.2
A marking is live if and only if the number of tokens on each cycle of the marked graph is at least one.
THEOREM 7.3
A live marking is safe if and only if every place in the marked graph is in a cycle with a token count of one.
These theorems provide a simple and easy way to inspect the structure of a marked graph and from its structure and its initial marking to determine if the marked graph is live and safe. It is also possible to show that the reachability problem for markings of marked graphs is decidable. For example, note the following.
THEOREM 7.4
A marking  mu prime is reachable from a live marking  mu in a strongly connected marked graph if and only if the total number of tokens in each cycle of the marked graph is the same in both  mu and  mu prime .
The high decision power of marked graphs is evident from the above theorems and the work on marked graphs in [Holt and Commoner 1970; Commoner et al. 1971; Genrich and Lautenbach 1973; Izbicki 1973; Murata 1977b]. However, there is a trade-off between decision power and modeling power, and the high decision power of marked graphs results in part from low modeling power. Thus, investigators have tried to develop other subclasses of Petri nets which retain the high decision power of marked graphs while increasing their modeling power.

7.4.3. Free-choice Petri Nets

Hack, in his Master's thesis at M.I.T. [Hack 1972], defined and investigated one such subclass of Petri nets, the free-choice Petri nets. This subclass allows both the conflicts of state machines and the concurrency of marked graphs but in a more restricted manner than the general Petri net model.

DEFINITION 7.3
A free-choice Petri net is a Petri net  C = (P, T, I, O) such that for all  t sub {j} \(mo T and  p sub {i} \(mo I ( t sub {j} ) , either  I ( t sub {j} ) = { p sub {i} } or  O ( p sub {i} ) = { t sub {j} } .

The importance of this definition is the way in which it allows controlled conflict. Conflict occurs only when one place is an input to several transitions. By the definition of free-choice Petri nets, if a place is an input to several transitions (potential conflict), then it is the only input for all of these transitions. Hence either all of these conflicting transitions are simultaneously enabled, or none of them are. This allows the choice (conflict resolution) as to which transition is to fire to be made freely; the presence of other tokens in other places is not involved in the choice as to which transition fires.

This restricted form of conflict allowed Hack [1972] to prove necessary and sufficient conditions for a marked free-choice Petri net to be live and safe. The liveness condition is related to the markings of traps and deadlocks in the net. A trap is a set of places such that every transition which inputs from one of these places also outputs to one of these places. This means that once any of the places in a trap has a token there will always be a token in one of the places of the trap. Firing transitions may move the token between places but cannot remove a token from the trap. A deadlock is a set of places such that every transition which outputs to one of the places in the deadlock also inputs from one of these places. This means that once all of the places in the deadlock become unmarked, the entire set of places will always be unmarked; no transition can place a token in the deadlock because there is no token in the deadlock to enable a transition which outputs to a place in the deadlock.

Hack proved that a necessary and sufficient condition for liveness in a marked free-choice Petri net is that every deadlock contain a marked trap. This theorem was based on work by Commoner [Commoner 1972; Hack 1972]. Necessary and sufficient conditions for safeness involve showing that the free-choice Petri net is covered by a union of state machines. Details can be found in [Hack 1972].

Unfortunately, no further work has been done on free-choice Petri nets, and so properties of free-choice Petri nets with respect to reachability, equivalence, containment, languages, and so on have not been considered.

7.4.4. Simple Petri Nets

Hack has also defined one other subclass of Petri nets called simple Petri nets [Hack 1972]. Simple nets require that each transition have at most one input place which is shared with another transition and so also serve to restrict the manner in which conflicts can occur. No investigation has been made into the properties of this subclass of Petri nets.


Figure 7.14 . A simple chart showing some of the structural configurations which are allowed or not allowed for some subclasses of Petri nets.


Section 7.5. Further Reading

The proof by Patil [1971] that  P /V systems cannot solve all synchronization problems and the counterproof by Parnas [1972] are short and interesting. They led to the proofs of Kosaraju [1973] and Agerwala and Flynn [1973] that Petri nets cannot model all concurrent systems. These results led Agerwala to investigate what is needed in a model which can model all systems [Agerwala 1974a; Agerwala 1974b].

The major work on restricted Petri net models is in the early [Holt et al. 1968] and [Commoner et al. 1971] and the later [Hack 1972]. Some work has continued on marked graphs [Izbicki 1973; Murata 1977b], but little has been done on the other models. Some encouraging results have been obtained in [Crespi-Reghizzi and Mandrioli 1975] and [Landweber and Robertson 1975] for conflict-free Petri nets in which  | O ( t sub {j} ) | = 1 . Reachability and liveness are decidable for conflict-free nets.

Section 7.6. Topics for Further Study

  1. One suggested extension is to associate information with tokens. This can be phrased as a Petri net with colored tokens. Define a Petri net model with colored tokens. Use this extended model to test the conjecture that either (a) it is equivalent to normal Petri nets, or (b) it is equivalent to Turing machines (by allowing zero testing). The major problem will be defining the actions of transitions with colored inputs.

  2. Investigate further the properties of conflict-free, free-choice, and simple Petri nets.

  3. Characterize the class of Petri nets which are both marked graphs and state machines.

  4. What are the properties of the class of Petri nets whose transition inputs are either disjoint [ I ( t sub {j} ) inter I ( t sub {k} ) = \(es ] or identical [ I ( t sub {j} ) = I ( t sub {k} ) ]? This class of Petri nets properly includes free-choice Petri nets, but we would expect the properties of this new class to be very similar to those for free-choice nets.
Home   Comments?