Home Up Questions?

Chapter 2. Basic Definitions

In this chapter, we give formal definitions for the basic Petri net concepts. These basic concepts are used throughout our study of Petri nets and so are fundamental to a correct understanding of Petri nets.

Our formalisms are based on bag theory, an extension of set theory. If you are not familiar with bag theory, we suggest you read the appendix for the relevant concepts.

The definitions given here are similar in type to definitions in automata theory [Hopcroft and Ullman 1969]. In fact, they define a new class of machines, the Petri net automaton. As we shall see later (Chapters 5, 6, 7, and 8), this point of view can lead to some interesting results in formal language theory and automata theory.

Section 2.1. Petri Net Structure

A Petri net is composed of four parts: a set of places  P , a set of transitions  T , an input function  I , and an output function  O . The input and output functions relate transitions and places. The input function  I is a mapping from a transition  t sub {j} to a collection of places  I ( t sub {j} ) , known as the input places of the transition. The output function  O maps a transition  t sub {j} to a collection of places  O ( t sub {j} ) known as the output places of the transition.

The structure of a Petri net is defined by its places, transitions, input function, and output function.

DEFINITION 2.1
A Petri net structure,  C , is a four-tuple,  C = (P, T, I, O) .  P = { p sub {1}, p sub {2}, ..., p sub {n} } is a finite set of places,  n >= 0 .  T = { t sub {1}, t sub {2}, ..., t sub {m} } is a finite set of transitions,  m >= 0 . The set of places and the set of transitions are disjoint,  P inter T = \(es .  I : T -> P sup {inf} is the input function, a mapping from transitions to bags of places.  O : T -> P sup {inf} is the output function, a mapping from transitions to bags of places.
The cardinality of the set  P is  n , and the cardinality of the set  T is  m . We denote an arbitrary element of  P by  p sub {i} ,  i = 1, ..., n , and an arbitrary element of  T by  t sub {j} ,  j = 1, ..., m .

Examples of Petri net structures are given in Figures 2.1, 2.2, and 2.3.


Figure 2.1 . A Petri net structure represented as a 4-tuple. The tuple consists of a set of places ( P ), a set of transitions ( T ), an input function ( I: T -> P sup {inf} ), and an output function ( O: T -> P sup {inf} ).




Figure 2.2 . A Petri net structure.




Figure 2.3 . A Petri net structure.


A place  p sub {i} is an input place of a transition  t sub {j} if  p sub {i} \(mo I ( t sub {j} ) ;  p sub {i} is an output place if  p sub {i} \(mo O ( t sub {j} ) . The inputs and outputs of a transition are bags of places. A bag is a generalization of sets which allows multiple occurrences of an element in a bag. The appendix contains a description of bag theory. The use of bags, rather than sets, for the inputs and outputs of a transition allows a place to be a multiple input or a multiple output of a transition. The multiplicity of an input place  p sub {i} for a transition  t sub {j} is the number of occurrences of the place in the input bag of the transition,  # ( p sub {i} , I ( t sub {j} )) . Similarly, the multiplicity of an output place  p sub {i} for a transition  t sub {j} is the number of occurrences of the place in the output bag of the transition  # ( p sub {i} , O ( t sub {j} )) . If the input and output functions are sets (rather than bags), then the multiplicity of each place is either zero or one.

The input and output functions can be usefully extended to map places into bags of transitions in addition to mapping transitions into bags of places. We define a transition  t sub {j} to be an input of a place  p sub {i} if  p sub {i} is an output of  t sub {j} . A transition  t sub {j} is an output of place  p sub {i} if  p sub {i} is an input of  t sub {j} .

DEFINITION 2.2
We extend the input function  I and output function  O as follows:



such that



For the Petri net of Figure 2.1, the extended input and output functions are:




Exercises

  1. Give the extended input and output functions for Figures 2.2 and 2.3.

  2. Show that both an input and output function are not needed but that a Petri net can be defined from a set of places, a set of transitions, and an extended input (or output) function. To do this, show how an extended output function can be defined from an extended input function and vice versa.

Section 2.2. Petri Net Graphs

Most theoretical work on Petri nets is based on the formal definition of Petri net structures given above. However, a graphical representation of a Petri net structure is much more useful for illustrating the concepts of Petri net theory. A Petri net graph is a representation of a Petri net structure as a bipartite directed multigraph.

A Petri net structure consists of places and transitions. Corresponding to these, a Petri net graph has two types of nodes. A circle  \(ci represents a place; a bar  | represents a transition. Since the circles represent places, we call the circles places. Similarly, we call the bars transitions.

Directed arcs (arrows) connect the places and the transitions, with some arcs directed from the places to the transitions and other arcs directed from transitions to places. An arc directed from a place  p sub {i} to a transition  t sub {j} defines the place to be an input of the transition. Multiple inputs to a transition are indicated by multiple arcs from the input places to the transition. An output place is indicated by an arc from the transition to the place. Again, multiple outputs are represented by multiple arcs.

A Petri net is a multigraph, since it allows multiple arcs from one node of the graph to another. In addition, since the arcs are directed, it is a directed multigraph. Since the nodes of the graph can be partitioned into two sets (places and transitions), such that each arc is directed from an element of one set (place or transition) to an element of the other set (transition or place), it is a bipartite directed multigraph. We refer to it simply as a Petri net graph.

DEFINITION 2.3
A Petri net graph  G is a bipartite directed multigraph,  G = ( V , A ) , where  V = { v sub {1}, v sub {2}, ..., v sub {s} } is a set of vertices and  A = { a sub {1}, a sub {2}, ..., a sub {r} } is a bag of directed arcs,  a sub {i} = ( v sub {j}, v sub {k} ) , with  v sub {j}, v sub {k} \(mo V . The set  V can be partitioned into two disjoint sets  P and  T such that  V = P union T, P inter T = \(es , and for each directed arc,  a sub {i} \(mo A , if  a sub {i} = ( v sub {j}, v sub {k} ) , then either  v sub {j} \(mo P and  v sub {k} \(mo T or  v sub {j} \(mo T and  v sub {k} \(mo P .

Figures 2.4, 2.5, and 2.6 are Petri net graphs equivalent to the Petri net structures of Figures 2.1, 2.2, and 2.3.


Figure 2.4 . A Petri net graph equivalent to the Petri net structure of Figure 2.1.




Figure 2.5 . A Petri net graph equivalent to the Petri net structure of Figure 2.2.




Figure 2.6 . A Petri net graph equivalent to the Petri net structure of Figure 2.3.


To demonstrate the equivalence of these two representations of a Petri net, the Petri net structure and the Petri net graph, we show how to transform one into the other. Assume we are given a Petri net structure  C = (P, T, I, O) with  P = { p sub {1}, p sub {2}, ..., p sub {n} } and  T = { t sub {1}, t sub {2}, ..., t sub {m} } . Then we can define a Petri net graph as follows,

DEFINITION 2.4
Define  V = P union T . Define  A as a bag of directed arcs such that for all  p sub {i} \(mo P and  t sub {j} \(mo T



 G = ( V , A ) is a Petri net graph which is equivalent to the Petri net structure  C = (P, T, I, O) .

Conversion in the opposite direction (from a Petri net graph to a Petri net structure) is similar, and we leave the detailed description to the reader. One interesting problem arises in the translation from a Petri net graph to a Petri net structure. If the set of vertices is partitioned into the two sets  S and  R , which set should be the places and which set should be the transitions? Both possible selections allow a Petri net to be defined, although the two resulting structures have interchanged places and transitions.

The dual of a Petri net  C = (P, T, I, O) is the Petri net  C bar = (T, P, I, O) which results from interchanging places and transitions. The graph structure is maintained, simply interchanging the circles and bars of the graph to indicate the change in places and transitions (but see Exercise 6). Figure 2.7 is the dual of the Petri net of Figure 2.4. Duality is a commonly used aspect of graph theory and would appear to be an interesting Petri net concept. However, no use has been made of the concept of the dual of a Petri net in Petri net research. This results, most likely, from the difficulty of defining the dual of a marked Petri net. Marked Petri nets are discussed next.


Figure 2.7 . The dual of the Petri net of Figure 2.4.




Exercises

  1. Give the dual of the Petri net graphs of Figures 2.5 and 2.6.

  2. Give the Petri net graph of the following Petri net structure:




  3. Give the Petri net graph of the following Petri net structure:




  4. Show that the dual of the dual of a Petri net structure  C is the same structure  C .

  5. Define the class of Petri nets which are equal to their own duals. Can you give a simple characterization of this class of Petri nets?

  6. If the dual of a Petri net structure,  C = (P, T, I, O) is defined as  C bar = (T, P, I, O) , the input and output functions must first be extended to map both  P and  T . Why? If  C = (P, T, I, O) with nonextended input and output functions, give the definition of  C bar = (T, P, I prime , O prime ) with nonextended input and output functions.

  7. Give the Petri net structure corresponding to the Petri net graph of Figure 2.8. Give the Petri net structure for Figure 2.9.

    Figure 2.8 . A Petri net graph.




    Figure 2.9 . A Petri net graph.


  8. Petri net graphs are multigraphs because a place may be a multiple input or output of a transition. This results in a graph with several arcs between the place and the transition. While this is satisfactory for small multiplicity (up to maybe three), it would be inconvenient for very large multiplicity. Thus, an alternative representation for structures with a large multiplicity is to use a bundle of arcs. A bundle is a special arc which is drawn very thick and labeled with its multiplicity. Figure 2.10 illustrates a transition with input multiplicity 7 and output multiplicity 11. Draw the Petri net graph for the following structure:

    Figure 2.10 . Bundles of arcs. For graphs with large multiplicity, a bundle is used, tagged with the multiplicity, rather than drawing multiple arcs.







  9. The inverse Petri net  -C for a Petri net  C = (P, T, I, O) is defined by interchanging the input and output functions,  -C = (P, T, O, I) . What is the effect on the Petri net graph? How does this differ from the dual of a Petri net? Does it matter if the input and output functions have been extended? Draw the inverse Petri net of Figure 2.7.

Section 2.3. Petri Net Markings

A marking  mu is an assignment of tokens to the places of a Petri net. A token is a primitive concept for Petri nets (like places and transitions). Tokens are assigned to and can be thought to reside in the places of a Petri net. The number and position of tokens may change during the execution of a Petri net. The tokens are used to define the execution of a Petri net.

DEFINITION 2.5
A marking  mu of a Petri net  C = (P, T, I, O) is a function from the set of places  P to the nonnegative integers  N .  mu : P -> N .

The marking  mu can also be defined as an  n -vector,  mu = ( mu sub {1}, mu sub {2}, ..., mu sub {n} ) , where  n = | P | and each  mu sub {i} \(mo N ,  i = 1, ..., n . The vector  mu gives for each place  p sub {i} in a Petri net the number of tokens in that place. The number of tokens in place  p sub {i} is  mu sub {i} ,  i = 1, ..., n . The definitions of a marking as a function and as a vector are obviously related by  mu ( p sub {i} ) = mu sub {i} . The functional notation is somewhat more general and so is more commonly used.

A marked Petri net  M = ( C, mu ) is a Petri net structure  C = (P, T, I, O) and a marking  mu . This is also sometimes written as  M = (P, T, I, O, mu ) .

On a Petri net graph, tokens are represented by small dots  \(bu in the circles which represent the places of a Petri net. Figures 2.11 and 2.12 show examples of a graph representation of a marked Petri net.


Figure 2.11 . A marked Petri net. The Petri net structure is the same as Figures 2.1 and 2.4. The marking is  (1, 2, 0, 0, 1) .




Figure 2.12 . A marked Petri net. The structure is the same as the structure of Figure 2.11, but the marking is different.


Since the number of tokens which may be assigned to a place of a Petri net is unbounded, there are an infinity of markings for a Petri net. The set of all markings for a Petri net with  n places is simply the set of all  n -vectors,  N sup {n} . This set, although infinite, is of course denumerable.

Exercises

  1. For the marked Petri net of Figure 2.12, give the marking, both as a function and as a vector.

  2. For the Petri net structure of Figure 2.2, draw the Petri net graph and indicate on the graph a marking  mu = (1, 0, 1, 1, 0, 0) .

  3. Although the number of tokens in a Petri net which is drawn seldom exceeds 5 or 6, it is possible that a marking might have 10 or 20 or hundreds of tokens assigned to a place. In this case, it would be very inconvenient to actually draw hundreds of tokens in the circles representing the places of a Petri net graph. The convention in this case is to write the number of tokens in the place as in Figure 2.13. Using this convention, draw the Petri net of Figure 2.11 with a marking of  mu = (137, 22, 2, 0, 14) .


Figure 2.13 . A Petri net graph with a very large marking,  (47, 13, 7, 42) .


Section 2.4. Execution Rules for Petri Nets

The execution of a Petri net is controlled by the number and distribution of tokens in the Petri net. Tokens reside in the places and control the execution of the transitions of the net. A Petri net executes by firing transitions. A transition fires by removing tokens from its input places and creating new tokens which are distributed to its output places.

A transition may fire if it is enabled. A transition is enabled if each of its input places has at least as many tokens in it as arcs from the place to the transition. Multiple tokens are needed for multiple input arcs. The tokens in the input places which enable a transition are its enabling tokens. For example, if the inputs to transition  t sub {4} are places  p sub {1} and  p sub {2} , then  t sub {4} is enabled if  p sub {1} has at least one token and  p sub {2} has at least one token. For a transition  t sub {7} with input bag  { p sub {6}, p sub {6}, p sub {6} } , place  p sub {6} must have at least three tokens to enable  t sub {7} .

DEFINITION 2.6
A transition  t sub {j} \(mo T in a marked Petri net  C = (P, T, I, O) with marking  mu is enabled if for all  p sub {i} \(mo P ,


A transition fires by removing all of its enabling tokens from its input places and then depositing into each of its output places one token for each arc from the transition to the place. Multiple tokens are produced for multiple output arcs. A transition  t sub {3} with  I ( t sub {3} ) = { p sub {2} } and  O ( t sub {3} ) = { p sub {7}, p sub {13} } is enabled whenever there is at least one token in place  p sub {2} . Transition  t sub {3} fires by removing one token from place  p sub {2} and depositing one token in place  p sub {7} and one token in place  p sub {13} (its outputs). Extra tokens in place  p sub {2} are not affected by firing  t sub {3} (although they may enable additional firings of  t sub {3} ). A transition  t sub {2} with  I ( t sub {2} ) = { p sub {21}, p sub {23} } and  O ( t sub {2} ) = { p sub {23}, p sub {25}, p sub {25} } fires by removing one token from  p sub {21} and one token from  p sub {23} and then deposits one token in  p sub {23} and two tokens in  p sub {25} (since  p sub {25} has a multiplicity of two).

Firing a transition will in general change the marking  mu of the Petri net to a new marking,  mu prime . Notice that since only enabled transitions may fire, the number of tokens in each place always remains nonnegative when a transition is fired. Firing a transition can never try to remove a token which is not there. If there are not enough tokens in any input place of a transition, then the transition is not enabled and cannot fire.

DEFINITION 2.7
A transition  t sub {j} in a marked Petri net with marking  mu may fire whenever it is enabled. Firing an enabled transition  t sub {j} results in a new marking  mu prime defined by




Figure 2.14 . Illustrating how the marking of a place changes when a transition  t sub {j} fires. Each place may or may not be an input or output of the transition. This figure illustrates only the cases for a multiplicity of zero or one.


As an example, consider the marked Petri net of Figure 2.15. With this marking, three transitions are enabled, transitions  t sub {1} ,  t sub {3} , and  t sub {4} . Transition  t sub {2} is not enabled because there is no token in either place  p sub {2} or  p sub {3} , which are both inputs of transition  t sub {2} . Since transitions  t sub {1} ,  t sub {3} , and  t sub {4} are enabled, any of them may fire. If transition  t sub {4} fires, it removes a token from each input and deposits a token in each output. This removes the token in  p sub {5} , deposits one token in  p sub {3} , and increases the number of tokens in  p sub {4} from two to three. Thus, the new marking which results from firing transition  t sub {4} is shown in Figure 2.16.


Figure 2.15 . A marked Petri net to illustrate the firing rules. Transitions  t sub {1} ,  t sub {3} , and  t sub {4} are enabled.




Figure 2.16 . The marking which results from firing transition  t sub {4} in Figure 2.15.


In the marked Petri net of Figure 2.16, only transitions  t sub {1} and  t sub {3} are enabled. Firing transition  t sub {1} will remove the token in  p sub {1} and deposit tokens in  p sub {2} ,  p sub {3} , and  p sub {4} (two tokens in  p sub {4} since it is a multiple output of transition  t sub {1} ). This produces the marking of Figure 2.17. In this marked Petri net, transitions  t sub {2} and  t sub {3} are enabled. Firing transition  t sub {3} produces the marking of Figure 2.18 where two tokens have been removed from  p sub {4} and one has been added to  p sub {5} .


Figure 2.17 . The marking which results from firing transition  t sub {1} in Figure 2.16.




Figure 2.18 . The marking which results from firing transition  t sub {3} in Figure 2.17.


Transition firings can continue as long as there exists at least one enabled transition. When there are no enabled transitions, the execution halts.

Exercises

  1. What transitions are enabled in the marked Petri net of Figure 2.11? Of Figure 2.12?

  2. What marking results from firing transition  t sub {1} in Figure 2.11? From firing transition  t sub {4} in Figure 2.12? From firing first transition  t sub {2} and then  t sub {4} in Figure 2.12?

  3. What transitions are enabled in Figure 2.13? For each of these transitions, what marking results from firing that transition in Figure 2.13?

  4. Can transitions be fired in Figure 2.19? Which?

    Figure 2.19 . A marked Petri net.


Section 2.5. Petri Net State Spaces

The state of a Petri net is defined by its marking. The firing of a transition represents a change in the state of the Petri net by a change in the marking of the net. The state space of a Petri net with  n places is the set of all markings, that is,  N sup {n} . The change in state caused by firing a transition is defined by a change function  delta called the next-state function. When applied to a marking (state)  mu and a transition  t sub {j} this function yields the new marking (state) which results from firing transition  t sub {j} in marking  mu . Since  t sub {j} can fire only if it is enabled,  delta ( mu , t sub {j} ) is undefined if  t sub {j} is not enabled in marking  mu . If  t sub {j} is enabled, then  delta ( mu , t sub {j} ) = mu prime , where  mu prime is the marking which results from removing tokens from the inputs of  t sub {j} and adding tokens to the outputs of  t sub {j} .

DEFINITION 2.8
The next-state function  delta : N sup {n} times T -> N sup {n} for a Petri net  C = (P, T, I, O) with marking  mu and transition  t sub {j} \(mo T is defined if and only if


for all  p sub {i} \(mo P . If  delta ( mu , t sub {j} ) is defined, then  delta ( mu , t sub {j} ) = mu prime , where


for all  p sub {i} \(mo P .

Given a Petri net  C = (P, T, I, O) and an initial marking  mu sup {0} , we can execute the Petri net by successive transition firings. Firing an enabled transition  t sub {j} in the initial marking produces a new marking  mu sup {1} = delta ( mu sup {0}, t sub {j} ) . In this new marking, we can fire any new enabled transition, say  t sub {k} , resulting in a new marking  mu sup {2}= delta ( mu sup {1}, t sub {k} ) . This can continue as long as there is at least one enabled transition in each marking. If we reach a marking in which no transition is enabled, then no transition can fire, the next-state function is undefined for all transitions, and the execution must halt.

Two sequences result from the execution of a Petri net: the sequence of markings  ( mu sup {0}, mu sup {1}, mu sup {2}, ...) and the sequence of transitions which were fired  ( t sub {j sub {0}}, t sub {j sub {1}}, t sub {j sub {2}}, ...) . These two sequences are related by the relationship  delta ( mu sup {k}, t sub {j sub {k}} ) = mu sup {k + 1} for  k = 0, 1, 2, ... . Given a transition sequence and  mu sup {0} , we can easily derive the marking sequence for the execution of the Petri net, and, except for a few degenerate cases, given the marking sequence, we can derive the transition sequence. Both of these sequences thus provide a record of the execution of the Petri net.

In a marking  mu , a set of transitions will be enabled and may fire. The result of firing a transition in a marking  mu is a new marking  mu prime . We say that  mu prime is immediately reachable from  mu ; that is, we can immediately get to state  mu prime from state  mu .

DEFINITION 2.9
For a Petri net  C = (P, T, I, O) with marking  mu , a marking  mu prime is immediately reachable from  mu if there exists a transition  t sub {j} \(mo T such that  delta ( mu , t sub {j} ) = mu prime .
We can extend this concept to define the set of reachable markings for a given marked Petri net. If  mu prime is immediately reachable from  mu and  mu prime prime is immediately reachable from  mu prime , then we say that  mu prime prime is reachable from  mu . We define the reachability set  R ( C , mu ) of a Petri net  C with marking  mu to be all markings which are reachable from  mu . A marking  mu prime is in  R ( C , mu ) if there is any sequence of transition firings which will change marking  mu into marking  mu prime . The ``reachability'' relationship is the reflexive transitive closure of the ``immediately reachable'' relationship.
DEFINITION 2.10
The reachability set  R ( C , mu ) for a Petri net  C = (P, T, I, O) with marking  mu is the smallest set of markings defined by,

  1.  mu \(mo R ( C , mu ) .

  2. If  mu prime \(mo R ( C , mu ) and  mu prime prime = delta ( mu prime , t sub {j} ) for some  t sub {j} \(mo T , then  mu prime prime \(mo R ( C , mu ) .
For the Petri net of Figure 2.20, and the marking  mu = (1, 0, 0) , two markings are immediately reachable: (0, 1, 0) and (1, 0, 1). From (0, 1, 0), no markings are reachable since no transition is enabled. However from (1, 0, 1), we can reach (0, 1, 1) and (1, 0, 2). Using techniques which are developed in Chapter 4, we can show that the reachability set  R ( C , mu ) is  { (1, 0, n ), (0, 1, n ) | n >= 0 } .

Figure 2.20 . A marked Petri net.


It is convenient to extend the next-state function to map a marking and a sequence of transitions into a new marking. For a sequence of transitions  t sub {j sub {1}} t sub {j sub {2}} ... t sub {j sub {k}} and marking  mu , the marking  mu prime = delta ( mu , t sub {j sub {1}} t sub {j sub {2}} ... t sub {j sub {k}} ) is the result of firing first  t sub {j sub {1}} , then  t sub {j sub {2}} , and so on until  t sub {j sub {k}} is fired. (This is possible, of course, only if each transition is enabled when it is to be fired.)

DEFINITION 2.11
The extended next-state function  delta : N sup {n} times T sup {*} -> N sup {n} is defined for a transition  t sub {j} and a sequence of transitions  sigma \(mo T sup {*} by



In general, we use this extended next-state function.

Exercises

  1. For the marked Petri net of Figure 2.21 and the transition sequence  t sub {1} t sub {2} t sub {3} t sub {4} t sub {5} , give the corresponding marking sequence. For the marking sequence, (1, 0, 0), (0, 0, 1), (0, 0, 0), what is the corresponding transition sequence?

    Figure 2.21 . A marked Petri net.


  2. It was said that there are a few degenerative cases in which a marking sequence does not define a unique transition firing sequence. Characterize the class of Petri nets for which this may be the case.

  3. Show that  union from {mu \(mo N sup {n}} R ( C , mu ) = N sup {n} .

  4. Prove that if  mu prime \(mo R ( C , mu ) , then  R ( C , mu prime ) \(ib R ( C , mu ) .

  5. Prove that  mu prime \(mo R ( C , mu ) if and only if  R ( C , mu prime ) \(ib R ( C , mu ) .

  6. Is  R ( C , mu ) = union from {t sub {j} \(mo T} delta ( mu , t sub {j} ) ?

  7. Is  R ( C , mu ) = union from {t sub {j} \(mo T} R ( C, delta ( mu , t sub {j} )) ?

  8. Some of the literature on Petri nets refers to the reachability set of a marked Petri net as its marking class. More specifically, the forward marking class of a Petri net is what we have defined as the reachability set. The backward marking class is the reachability set of the inverse Petri net. (See Exercise 9 of Section 2.2.) The marking class of a marked Petri net is then the union of the forward and backward marking classes. Give formal definitions of the forward marking class, the backward marking class, and the marking class of a Petri net  C with marking  mu . Then show that the marking classes of a Petri net partition the set of all markings into disjoint equivalence classes. This requires showing that the relationship of having equal marking classes is reflexive, symmetric, and transitive.

  9. It has been observed that Petri nets with their tokens and firing rules are very similar to board games, such as checkers, backgammon, nim, go, and so on. One can imagine a game for one to four players consisting of a board with a Petri net and a collection of plastic tokens. Tokens are distributed on the places of the Petri net, and players take turns selecting enabled transitions and firing them. The game would be sold with a set of 20 different Petri nets to provide variety. Starting with these ideas, develop a complete set of rules including

    1. How is the initial distribution of tokens determined? (Each player starts with one token on the ``home'' place, or each player gets  n tokens to place on the board as desired, or ... .)

    2. What is the goal of the game? (Capture the tokens of your opponents or create the greatest number of tokens, or reduce the number of tokens you have to zero as fast as possible, or ... .)

    3. Consider the possibilities of colored tokens to distinguish players, and consider appropriate definitions of firing rules.

    4. Consider assigning points to the different transitions. A player's points are determined by the sum of the transitions fired by that player.

    5. Consider any problems which might arise such as repeated firings of transitions which create new tokens (more outputs than inputs) and the finite number of tokens provided with the game set.

    After you have defined your game, try playing it with some friends. Use the Petri net of Figure 2.22 as a playing board.

    Figure 2.22 . A Petri net game board.


Section 2.6. Alternative Forms for Defining Petri Nets

The theory of Petri nets has been developed by a number of people working at different times in different places with different backgrounds and motivations. In part due to this diversity, many of the fundamental concepts have been defined by different researchers in different ways. We present some of these variant definitional forms here to show that there is no substantial difference in the definitions and to prepare the reader for the varying representations which may be encountered in the literature.

Petri's original nets [Petri 1962a], for example, did not allow multiple arcs between places and transitions. This is equivalent to defining the inputs and outputs of a transition to be sets (not bags) of places. Further, the firing rule was limited to requiring that a token reside in each input place to a transition and no tokens reside in the output places. A transition fired by removing the tokens from its inputs (which now became empty) and placing tokens in the (previously empty) outputs (which now became full). A transition could not fire if a token already resided in an output place. Thus a marking assigned either zero or one token to each place,  mu : P -> { 0, 1 } . It should be obvious then that a net with only  n places has exactly  2 sup {n} possible markings, a finite number of states.

The early work at ADR by Holt and the Information System Theory Project [Holt et al. 1968] continued with these same definitions, but as work progressed, the limitations of this model were recognized. The work of Holt and Commoner presented at the Woods Hole conference [Holt and Commoner 1970] generalized the class of markings and the firing rule to allow arbitrary markings,  mu : P -> { 0, 1, 2, ... } . This then defined the basic Petri net model as it is defined today (with the exception of the multiple arc feature).

Many of the early researchers did not formally define their models but rather described informally the relevant components, such as places, transitions, tokens, and the firing rule. One of the first formal definitions was by Patil [1970a] in his Ph.D. dissertation where a Petri net was defined as a four-tuple  (T, P, A, B) with  T the set of transitions,  P the set of places,  A a set of arcs, and  B an initial marking. The arcs in the set  A connected either a place with a transition or a transition with a place. Thus  A \(ib (P times T) union (T times P) . Many papers on Petri nets are based on this definition and define a Petri net as a triple  (P, T, A) with a separate marking function.

The conversion from the  (P, T, A) form of definition to separate input and output functions is relatively straightforward. The set of arcs  A is split into a set of input arcs  { ( p sub {i}, t sub {j} ) | ( p sub {i}, t sub {j} ) \(mo A } and output arcs  { ( t sub {j}, p sub {i} ) | ( t sub {j}, p sub {i} ) \(mo A } . This form leads directly to the generalization allowing multiple inputs and outputs. It is necessary simply to attach a multiplicity to each input or output arc.

Hack [1975c] eventually settled on a definition of Petri nets as a four-tuple  (P, T, F, B) , with  P the set of places and  T the set of transitions, as usual.  F and  B are functions mapping places and transitions onto the number of tokens needed for input ( F ) or produced for output ( B ). Thus a transition  t sub {j} can fire only if at least  F ( t sub {j}, p sub {i} ) tokens are in each place  p sub {i} \(mo P . A transition fires by removing  F ( t sub {j}, p sub {i} ) tokens from each input place and depositing  B ( t sub {j}, p sub {i} ) tokens in each output place. The functions  F and  B can be represented by matrices.

Peterson in his dissertation [Peterson 1973] tried to combine transitions and their inputs and outputs by defining a transition as an ordered pair of bags of places, t sub {j} \(mo P sup {inf} times P sup {inf} . The first component of the pair is the bag of inputs to the transition; the second component is the bag of outputs of the transition. This reduced the primitive concepts of the theory to places and tokens, since transitions are structures composed of places. It was particularly useful in allowing the easy definition of a transition for a constructed Petri net.

These definitions vary from the one presented here only by notational differences. For most work on Petri nets, this is the case: The differences in definition are strictly notational. However in some cases, the definitions may restrict the class of Petri nets by not allowing multiple input or output arcs or otherwise restricting the form of the transitions; e.g., transitions are required to have a nonnull set of input places and a nonnull set of output places, or the input and output places of a transition must be disjoint (self-loop-free). Even these differences are not important, as is seen in Chapter 5.

Exercises

  1. For a Petri net defined by  (P, T, F, B) , give the equivalent standard  (P, T, I, O) definition. For a Petri net defined as  (P, T, I, O) , give the  (P, T, F, B) definition.

  2. Why would some researchers prefer a  (P, T, A) definition which mixes input and output relationships into the arc set  A , while others prefer  (P, T, I, O) ? Give an advantage and disadvantage of each.

Section 2.7. Further Reading

Few descriptions of Petri nets concentrate simply on the basic definitions. The Computing Surveys tutorials by Baer [1973a] and Peterson [1977] are probably the best bets for continued introduction. Almost any paper on Petri nets will present the basic definitions and notation in the first few sections. Hence you could simply scan the beginning of some of the papers listed in the bibliography to find a variety of definitions. Try Holt et al. [1968], Holt and Commoner [1970], Hack [1974a; 1975b; 1975c], Keller [1975a], Misunas [1973], Murata [1977a], and Thomas [1976].

Section 2.8. Topics for Further Study

  1. Develop Petri net theory to allow colored tokens. Consider the changes to the definitions of enabled transitions and transition firings. There are at least three reasonable ways to extend Petri nets for colored tokens; indicate as many as you can think of and evaluate their usefulness.

  2. Develop an introduction to Petri net theory for noncomputer scientists. Compare your presentation with those of Meldman and Holt [1971] and Meldman [1977; 1978].

  3. Construct a computer simulation system for Petri net execution. To allow a convenient interface for the user of the program, use an erasable graphics display (such as a CRT or plasma panel) to display the Petri net and to show the firing of transitions and consequent movement of tokens. This will involve many subproblems.

    1. The language used to define the Petri net and its markings and to select options must be defined.

    2. An internal representation of the Petri net and its marking must be constructed, along with the necessary algorithms for simulation.

    3. The display must be created. A major problem here will be trying to achieve a planar representation of the net (to the degree reasonable). Also careful thought must be given to the representation of the dynamic properties of the net (token movement).

    The work of Noe et al. [1974] and Crowley and Noe [1975] might be of some use.
Home   Comments?