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 , a set of transitions , an input function , and an output function . The input and output functions relate transitions and places. The input function is a mapping from a transition to a collection of places , known as the input places of the transition. The output function maps a transition to a collection of places 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.
Examples of Petri net structures are given in Figures 2.1,
2.2, and 2.3.
A place is an input place of a transition if ; is an output place if . 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 for a transition is the number of occurrences of the place in the input bag of the transition, . Similarly, the multiplicity of an output place for a transition is the number of occurrences of the place in the output bag of the transition . 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 to be an input of a place if is an output of . A transition is an output of place if is an input of .
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 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 to a transition 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.
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.
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 with and . Then we can define a Petri net graph as follows,
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 and , 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 is the Petri
net 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.
A marking 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.
The marking can also be defined as an -vector, , where and each , . The vector gives for each place in a Petri net the number of tokens in that place. The number of tokens in place is , . The definitions of a marking as a function and as a vector are obviously related by . The functional notation is somewhat more general and so is more commonly used.
A marked Petri net is a Petri net structure and a marking . This is also sometimes written as .
On a Petri net graph, tokens are represented by small dots
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.
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 places is simply the set of all
-vectors, . This set, although infinite,
is of course denumerable.
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 are places and , then is enabled if has at least one token and has at least one token. For a transition with input bag , place must have at least three tokens to enable .
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 with and is enabled whenever there is at least one token in place . Transition fires by removing one token from place and depositing one token in place and one token in place (its outputs). Extra tokens in place are not affected by firing (although they may enable additional firings of ). A transition with and fires by removing one token from and one token from and then deposits one token in and two tokens in (since has a multiplicity of two).
Firing a transition will in general change the marking of the Petri net to a new marking, . 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.
As an example, consider the marked Petri net of Figure 2.15.
With this marking, three transitions are enabled,
transitions , , and .
Transition is not enabled because there is no
token in either place or , which are
both inputs of transition . Since transitions
, , and are enabled, any
of them may fire. If transition fires, it
removes a token from each input and deposits a token in each
output. This removes the token in , deposits
one token in , and increases the number of
tokens in from two to three. Thus, the new
marking which results from firing transition is
shown in Figure 2.16.
In the marked Petri net of Figure 2.16, only transitions
and are enabled. Firing
transition will remove the token in
and deposit tokens in , , and
(two tokens in since it is a
multiple output of transition ). This produces
the marking of Figure 2.17. In this marked Petri net,
transitions and are enabled.
Firing transition produces the marking of
Figure 2.18 where two tokens have been removed from
and one has been added to .
Transition firings can continue as long as there exists at
least one enabled transition. When there are no enabled
transitions, the execution halts.
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 places is the set of all markings, that is, . The change in state caused by firing a transition is defined by a change function called the next-state function. When applied to a marking (state) and a transition this function yields the new marking (state) which results from firing transition in marking . Since can fire only if it is enabled, is undefined if is not enabled in marking . If is enabled, then , where is the marking which results from removing tokens from the inputs of and adding tokens to the outputs of .
Given a Petri net and an initial marking , we can execute the Petri net by successive transition firings. Firing an enabled transition in the initial marking produces a new marking . In this new marking, we can fire any new enabled transition, say , resulting in a new marking . 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 and the sequence of transitions which were fired . These two sequences are related by the relationship for . Given a transition sequence and , 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 , a set of transitions will be enabled and may fire. The result of firing a transition in a marking is a new marking . We say that is immediately reachable from ; that is, we can immediately get to state from state .
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 and marking , the marking is the result of firing first , then , and so on until is fired. (This is possible, of course, only if each transition is enabled when it is to be fired.)
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, . It should be obvious then that a net with only places has exactly 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, . 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 with the set of transitions, the set of places, a set of arcs, and an initial marking. The arcs in the set connected either a place with a transition or a transition with a place. Thus . Many papers on Petri nets are based on this definition and define a Petri net as a triple with a separate marking function.
The conversion from the form of definition to separate input and output functions is relatively straightforward. The set of arcs is split into a set of input arcs and output arcs . 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 , with the set of places and the set of transitions, as usual. and are functions mapping places and transitions onto the number of tokens needed for input () or produced for output (). Thus a transition can fire only if at least tokens are in each place . A transition fires by removing tokens from each input place and depositing tokens in each output place. The functions and 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, . 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.
Few descriptions of Petri nets concentrate simply on the
basic definitions. The Computing Surveys tutorials by
Baer [1973a] and Peterson  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. , Holt and
Commoner , Hack [1974a; 1975b; 1975c], Keller [1975a],
Misunas , Murata [1977a], and Thomas .
Section 2.8. Topics for Further Study