Home  Up  Questions? 
The discussions of Chapters 4 and 5 have concentrated on problems related to the reachability problem, dealing mainly with problems of reachable markings. A related but quite different approach is to focus not on what markings are reachable but rather on how we reach them. The primary object of interest is then the transition and particularly the sequences of transitions which lead us from one marking to another in a Petri net.
A sequence of transitions is a string, and a set of strings is a language. Thus, in this chapter, we concentrate on the languages defined by Petri nets and their properties.
Petri nets are being developed for two major reasons: (1) the description of proposed or existing systems and (2) the analysis of systems which can be modeled by a Petri net description. The analysis of a Petri net attempts to determine the properties of the net and the system which it models. One of the most important properties of a system is the set of actions which can occur. The set of all possible sequences of actions characterizes the system.
In a Petri net, actions are modeled by transitions, and the occurrence of an action is modeled by the firing of a transition. Sequences of actions are modeled by sequences of transitions. Thus the set of allowable transition sequences characterizes a Petri net and (to the degree that the Petri net correctly models a system) the modeled system.
These sequences of transitions can be of extreme importance in using Petri nets. Assume that a new system has been designed to replace an existing one. The behavior of the new system is to be identical to the old system (but the new system is cheaper, faster, easier to repair, or something). If both systems are modeled as Petri nets, then the behaviors of these two nets should be identical, and so their languages should be equal. Two Petri nets are equivalent if their languages are equal. This provides a formal basis for stating the equivalence of two systems.
A particular instance in which equivalence is important is optimization. Optimizing a Petri net involves creating a new Petri net which is equivalent (languages are equal) but for which the new net is “better” than the old one (for some definition of better). For example, if a Petri net is to be directly implemented in hardware, then a Petri net with fewer places, transitions, and arcs would be less expensive to build, since it has fewer components. Thus one optimization problem might be to reduce  P  +  T  without changing the behavior of the net.
For purposes of optimization, a set of languagepreserving transformations might be useful. If a transformation applied to a Petri net produces a new Petri net with the same language, then it is language preserving. An optimal Petri net can be produced by applying languagepreserving transformations to a nonoptimal Petri net. Practical use of a Petrinetbased system for modeling and analysis would require a collection of languagepreserving transformations.
Petri net languages can also be useful for analysis of Petri nets. Techniques have been developed in Chapter 4 for determining specific properties of Petri nets, such as safeness, boundedness, conservation, liveness, reachability, and coverability. Although these are important (and difficult) properties to establish, they are not the only properties for which a Petri net might be analyzed. It may be necessary to establish the correctness of a modeled system by showing that systemspecific properties are satisfied. Thus, either new techniques must be developed for each new property, or a general analysis technique for Petri nets is needed.
A large class of questions can be posed in terms of the sequences of actions which are possible in the system. If we define the set of possible sequences of actions as the language of the system, then we can analyze the system by analyzing the language of the system. Now problems may be answered by considering the emptiness question (Will any sequence get me from here to there?) or the membership question (Is a sequence of this form possible?). This may provide us with a general technique for analyzing arbitrary systems for systemspecific properties. Riddle [1972] has investigated analysis based on the language of the modeled system.
Another use of Petri net languages would be in the specification and automatic synthesis of Petri nets. If the behavior which is desired can be specified as a language, then it may be possible to automatically synthesize a Petri net whose language is the specified language. This Petri net can be used as a controller, guaranteeing that all and only the sequences specified are possible. Path expressions [Lauer and Campbell 1974] have been developed to define allowable sequences of actions. Techniques have been developed for automatically creating a Petri net from a path expression.
Another motivation for the study of Petri net languages comes from a desire to determine decidability results for Petri nets. The decidability of many properties of Petri nets is unknown. The decidability of a few basic questions for Petri nets, such as reachability, is the object of much current research. One area in which decidability questions have been considered is formal language theory. By consideration of the languages of Petri nets, the concepts and techniques of formal language theory may be brought to bear on the problems of Petri nets. This may produce new results concerning Petri nets and their decidability questions. It is also possible to use Petri net methods to obtain new useful results about formal languages.
The Petri net language theory which has developed so far is similar to development of other parts of formal language theory. Several books present the classical theory of formal languages [Hopcroft and Ullman 1969; Salomaa 1973; Ginsburg 1966]. Many of the basic concepts of Petri net language theory have been borrowed from the classical theory of formal languages.
An alphabet is a finite set of symbols. A string is any sequence of finite length of symbols from the alphabet. The null or empty string λ is the string of no symbols and zero length. If Σ is an alphabet, then Σ^{*} is the set of all strings of symbols from Σ, including the empty string. Σ^{+} is the set of all nonempty strings over an alphabet Σ . Σ^{*} = Σ^{+} ∪ { λ } .
A language is a set of strings over an alphabet. Languages may in general be infinite; thus representing the language is a problem. Two approaches have been developed for representing languages. One approach is to define a machine which when executed generates a string from the language, and all strings of the language are generated by some execution. Alternatively, a grammar may be defined which specifies how to generate a string of a language by successively applying the productions of the grammar.
Restrictions on the forms of the machines or grammars which generate the languages define classes of languages. The traditional classes of languages are regular, contextfree, contextsensitive, and type0 languages, corresponding to finite state machines, pushdown automata, linear bounded automata, and Turing machines. Each of these classes of languages is generated by the appropriate class of automata. This provides an excellent means of linking Petri net theory to formal language theory: We define the class of Petri net languages as the class of languages generated by Petri nets. The details of the definition should be similar to the details for any of the other classes of languages.
As an example, let us consider finite state machines and
regular expressions. A finite state machine C is a
fivetuple ( Q, δ, Σ, s, F ), where Q is a
finite set of states, Σ is an alphabet of symbols,
δ: Q ⨯ Σ → Q is a next state
function, s ∈ Q is the start state, and
F ⊆ Q is a finite set of final states.
The next state function δ is extended to a function
from Q ⨯ Σ^{*} to Q in the natural way. The
language L ( C ) generated by the finite state machine is the
set of strings over Σ defined by
L(C)  =  { α ∈ Σ^{*}  δ(s, α) ∈ F } 
With each finite state machine is associated a language, and the class of all languages which can be generated by finite state machines is called the class of regular languages. The language of a finite state machine is a characterizing feature of the machine. If two finite state machines have the same language, they are equivalent.
The same basic concepts used to produce a regular language from a finite state machine can be applied to Petri nets to produce a theory of Petri net languages. In addition to the Petri net structure defined by the sets of places and transitions (which correspond roughly to the state set and nextstate function of the finite state machine), it is necessary to define an initial state, an alphabet, and a set of final states. The specification of these features for a Petri net can result in different classes of Petri nets. We consider each of these in turn.
The initial state of a Petri net can be defined in several ways. The most common definition is to allow an arbitrary marking μ to be specified as an initial state. However, this definition can be modified in several ways. One convenient limitation is to restrict the initial state to a marking with one token in a start place and zero tokens elsewhere [Peterson 1976]. Another more general definition allows a set of initial markings rather than simply one marking.
These three definitions are essentially the same. Certainly the start place definition is a special case of the initial marking definition, which is a special case of the set of initial markings definition. However, if a set of initial markings M = { μ_{1}, μ_{2}, …, μ_{k} } is needed with a start place definition, we can simply augment the Petri net with an extra place p_{0} and a set of transitions { t_{1}′, …, t_{k}′ } . Transition t_{j}′ would input a token from p_{0} and would output marking μ_{j}. Thus the behavior of the augmented net would be identical to a Petri net with a set of initial markings, except that each transition sequence would be preceded with t_{j}′ if marking μ_{j} were used to start the execution.
We see then that these three definitions of start states for a Petri net are essentially equivalent. Out of a sense of tradition, we define a Petri net language as starting from a single arbitrary marking μ .
Labeling Petri nets is another situation where several definitions can be used. We must define both what the alphabet Σ of a Petri net should be and how it is to be associated with the Petri net. We have indicated that the symbols are associated with the transitions, so that a sequence of transition firings generates a string of symbols for the language. The association of symbols to transitions is made by a labeling function, σ: T → Σ . Variations in language definition may result from various restrictions placed on the labeling function.
A freelabeled Petri net is a labeled Petri net where all transitions are labeled distinctly [i.e., if σ ( t_{i} ) = σ ( t_{j} ), then t_{i} = t_{j} ]. The class of free Petri net languages is a subset of the class of Petri net languages with a more general labeling function which does not require distinct labels. An even more general labeling function has been considered which allows null labeled transitions, σ ( t_{j} ) = λ . These λ labeled transitions do not appear in a sentence of a Petri net language, and their occurrence in an execution of a Petri net thus goes unrecorded. These three classes of labeling functions (free, λ free, and with λ transitions) define three variations of Petri net languages.
Without further investigation, it is not obvious which of these three labeling definitions is most reasonable. Perhaps each of the three is the most useful labeling function for some application. Thus, we need to consider the languages resulting from each possible definition of the labeling function.
The definition of final states for a Petri net has a major effect upon the language of a Petri net. Four major different definitions of the final state set of a Petri net have been suggested. Each of these may produce different Petri net languages.
One definition is derived from the analogous concept for finite state machines. It defines the set of final states F as a finite set of final markings. For this definition we define the class of Ltype Petri net languages.
The class of Ltype Petri net languages is rich and powerful, but it has been suggested that the requirement for a sentence to result in exactly a final state in order to be generated is contrary to the basic philosophy of a Petri net. This comment is based on the observation that if δ ( μ, t_{j} ) is defined for a marking μ and a transition t_{j}, then δ ( μ′, t_{j} ) is defined for any μ′ ≥ μ . From this comment we define a new class of languages, the class of Gtype Petri net languages, by the following.
A third class of Petri net languages is the class of Ttype Petri net languages. These are defined by identifying the set of final states used in the definition of Ltype languages with the (not necessarily finite) set of terminal states. A state μ_{t} is terminal if σ ( μ_{t}, t_{j} ) is undefined for all t_{j} ∈ T. Thus the class of Ttype Petri net languages is as follows.
Still a fourth class of languages is the class of Ptype Petri net languages whose final state set includes all reachable states. These languages are prefix languages since if α ∈ Σ^{*} is an element of a Ptype language, then for all prefixes β of α ( α = β x for some x ∈ Σ^{*} ) β is an element of that same language.
In addition to the four classes of languages based on
different specifications of the final state set, we have the
previously mentioned variations due to the labeling
function. Figure 6.1 lists the 12 classes of languages
which result from the cross product of the four types of
final state specification and the three types of labeling
functions. Each cell of Figure 6.1 lists the notation which
is used to denote each class of Petri net language.
To specify a particular Petri net language, four quantities must be defined: the Petri net structure, C = (P, T, I, O) ; the labeling function, σ: T → Σ ; the initial marking, μ: P → N, and the set of final markings, F (for L and Gtype languages). We define γ = (C, σ, μ, F) to be a labeled Petri net with Petri net structure C, labeling σ, initial marking μ, and final state set F. For a given labeled Petri net γ, 12 languages can be defined: L ( γ ), G ( γ ), T ( γ ), P ( γ ), L^{f} ( γ ), G^{f} ( γ ), T^{f} ( γ ), P^{f} ( γ ), L^{λ} ( γ ), G^{λ} ( γ ), T^{λ} ( γ ), P^{λ} ( γ ) .
The different definitions of Petri net languages can
associate different languages with a given Petri net.
Consider, for example, the Petri net of Figure 6.2. The
initial marking of (1, 0, 0, 0) is given on the net, and
each transition t_{j} is labeled by
σ ( t_{j} ) . If we define
F = { (0, 0, 1, 0) } (one token
in place p_{3} ), the Ltype language
is { a^{n} c b^{n}  n ≥ 0 },
the Gtype language is
{ a^{m} c b^{n}  m ≥ n ≥ 0 },
the Ttype language is
{ a^{m} c b^{n} d  m ≥ n ≥ 0 },
and the Ptype language is
{ a^{m}  m ≥ 0 } ∪ { a^{m} c b^{n}  m ≥ n ≥ 0 } ∪ { a^{m} c b^{n} d m ≥ n ≥ 0 } .
For this example, all four types of languages are different.
The labeling function given is a free labeling, but by
using different labeling functions, other languages can
also be produced.
Despite the differences in definitions, the classes of Petri
net languages are closely related. For instance, the set of
free labelings is a subset of the set of non λ
labelings, which is a subset of the set of
λ labelings. Thus,
L^{f}  ⊆ L ⊆ L^{λ} 
G^{f} ⊆ G ⊆ G^{λ}  
T^{f} ⊆ T ⊆ T^{λ}  
P^{f} ⊆ P ⊆ P^{λ} 
Also, every Ptype language is a Gtype language where
F = { (0, 0, …, 0) } . Thus,
P^{f}  ⊆ G^{f} 
P ⊆ G  
P^{λ} ⊆ G^{λ} 
We can also show that each language of type G or G^{λ} is also a language of type L or L^{λ}, respectively. Let G be a Gtype language for a Petri net structure (P, T, I, O), initial marking μ, and final set F. Construct a new labeled Petri net with the same places but with additional transitions as defined by the following:
For each t_{j} ∈ T, let B_{j} be the set of all proper subbags of O ( t_{j} ) . Each subbag in B_{j} is used to define a new transition with the same label and inputs as t_{j} but with the subbag as output. These new transitions are added to the previous set of transitions.
For example, if we consider the transition labeled a in the
Petri net of Figure 6.2, its input bag
is { p_{1} }, and
its output bag is { p_{1}, p_{2} } . The subbags
of { p_{1}, p_{2} } are { p_{1} }, { p_{2} }, and { } ( = ∅ ). This transition would
result in three new transitions being added to the net. All
of these new transitions would be labeled a and have input
bag { p_{1} }, but the output bags would be the three
subbags listed above (one transition for each subbag). New
transitions would also be added for the transitions labeled
b, c, and d, which would have the same
inputs but null outputs (since the current outputs are
singleton bags and hence the only subbag is ∅ ).
This new net is shown in Figure 6.3.
This new net has been modified in such a way that the
“extra” tokens which exceed a final state in F need not be
produced, if one selects the appropriate new transition which
has fewer outputs. Thus the Ltype language of the new net
is the same as the Gtype language of the old net.
G  ⊆ L 
G^{λ} ⊆ L^{λ} 
The above construction can also be modified slightly to show that a generalization of the definition of Ltype languages (to permit incompletely specified final markings) does not change the classes L and L^{λ}. Let a final marking for a Petri net with n places be an n vector over N ∪ { ω } . If a component of a final marking is ω, this means we do not care what the value of that component is in a final state. A state s is a final state if there exists a final marking f such that for all i, 1 ≤ i ≤ n, if f_{i} ≠ ω, then s_{i} = f_{i}. This is obviously a more general definition than the definition of Ltype languages given earlier.
Now consider a language which is defined by a Petri net and an incompletely specified final marking, f. Let τ be the set of all places for which f_{i} = ω . For each transition t_{j} ∈ T for which O ( t_{j} ) ∩ τ ≠ ∅, let ρ_{j} = O ( t_{j} ) ∩ τ and ψ_{j} = O ( t_{j} ) − ρ_{j}. The bag ρ_{j} is all places whose markings are don'tcares, while the bag ψ_{j} is all places whose markings must be exactly as specified in the final marking f. We add new transitions to the net whose label and input bag are the same as the label and input bag for t_{j} but whose output bag is ψ_{j} + ξ, where ξ ranges over all subbags of ρ_{j}. This construction does not in any way modify the behavior of those places which are not in τ but allows those places which are don'tcares to have any number of tokens less than or equal to the number of tokens which would have appeared in the original net. Thus, for each sentence in the generalized language of the original net, it is possible to pick appropriate transitions to fire so that when the net reaches a state s such that s_{i} = f_{i} for f_{i} ≠ ω, then s_{i} = 0 for f_{i} = ω . Thus the Ltype language for the constructed Petri net with a final marking f′ (where all ω in the incompletely specified marking f have been replaced by 0) is the same as the generalized language of the original net (as defined by the incompletely specified final marking f ).
For a language defined by a set of incompletely specified final markings (as opposed to only one such marking as just discussed), we use the fact that L (and L^{λ} ) languages are closed under union (see Section 6.5.2) to show that the language is still an L (or L^{λ} ) language.
With the introduction of incompletely specified final markings, we can show that Ttype languages are also Ltype languages (except possibly for free Ttype languages).
A final state μ for a Ttype language is such that no transition t_{j} can fire [i.e., ≥ μ ≱ I ( t_{j} )">] for all t_{j} ∈ T ]. The condition which specifies a final state for a Ttype language is thus exactly the opposite of the condition specifying a final state for a Gtype language. (We might call the Ttype languages inverse Gtype languages.) It is not difficult to see that such a set of markings can be described by a finite set of incompletely specified markings (as was done in Section 5.4). For example, the condition [≥ μ ≱ (2, 0) and ≥ μ ≱ (1, 1) ] is equivalent to [ μ = (0, ω ) or μ = (1, 0) ]. A Ttype language (or, more generally, an inverse Gtype language) can thus be rewritten as a generalized (i.e., incompletely specified) Ltype language and then as an Ltype language. Thus T ⊆ L, and T^{λ} ⊆ L^{λ}.
It is known that every L^{λ} type language can be generated by a Petri net in which every transition has an input place, and where the unique final marking is the zero marking, at which no transition is fireable [Hack 1975b]. If we add to every place a λ transition with a single input and a single output of that same place (i.e., a selfloop), then the language is not changed, and the zero marking becomes the only terminal marking. Hence, L^{λ} ⊆ T^{λ}, and from our previous demonstration that T^{λ} ⊆ L^{λ}, these two classes of languages are identical, T^{λ} = L^{λ}.
Figure 6.4 represents graphically the relationships among
the classes of Petri net languages which we have just
derived. An arc between classes indicates the containment
of one class of Petri net languages within another.
The study of Petri net languages is just beginning, and at present knowledge of the properties of these newly defined classes of languages is limited. The power of Petri nets is reflected in the variety of potentially different classes of Petri net languages which can be defined. The newness of this research is reflected by our inability to either show the complete relationships between these languages, or to argue that only a few of these classes are of importance. This results in a vast field of study, with the need to develop the properties of 12 different classes of languages.
It is obviously not possible to develop all 12 classes of languages in this volume, and so we limit ourselves here to considering only one class of Petri net languages, the Ltype languages. The major reasons for this limitation are space and the fact that this language has been investigated in the literature [Peterson 1973; Hack 1975b; Peterson 1976]. Some results have also been obtained by Hack [1975b] for the prefix (Ptype) languages and will be presented in our summary. The Gtype and Ttype languages have been defined, but no work has been done on their development. Remember also that the class of Ltype languages includes the classes of Ttype, Gtype, and Ptype languages. Thus, Ltype languages are in some sense the largest class of Petri net languages and so are appropriately investigated first.
Our investigation of the properties of Ltype Petri net languages will focus on two aspects. First we present closure properties of Petri nets under certain common operations (concatenation, union, concurrency, intersection, reversal, complement, indefinite concatenation, and substitution). Then we consider the relationship between Petri net languages and the classical formal languages: regular, contextfree, contextsensitive, and type0. This presentation provides an understanding of the power and limitations of (Ltype) Petri net languages. It also indicates how the other classes of Petri net languages can be investigated.
Although we are interested in the entire class of Ltype Petri net languages, we limit our discussion to only a limited set of standard form Petri nets. This limitation is made in order to ease the proofs and constructions; it does not limit the class of Petri net languages. For every Petri net language, there may be many Petri nets which generate that language; we choose to work only with those nets with certain properties. To show that this does not reduce the set of languages, we show that for every Ltype Petri net language there exists a standard form Petri net which generates it.
First we define a standard form Petri net.
The execution of a Petri net in standard form begins with one token in the start place. The first transition which fires removes this token from the start place, and after this firing the start place is always empty. Eventually the Petri net may stop by placing one token in the final place. This token cannot be removed from the final place both because no place has an input from the final place and because all transitions are disabled. Thus the execution of a Petri net in standard form is quite simple and limited. This is of great use when compositions of Petri nets are constructed. To show that Petri nets in standard form are not less powerful than general Petri nets, we prove the following theorem.
To start, we define three new places p_{r}, p_{f}, and p_{s} which are not in p. Place p_{s} is the start place, place p_{f} is the final place, and p_{r} is a “run” place; a token must be in p_{r} to allow any transition in T to fire. The initial marking of C′ will have one token in p_{s}; the final marking will consist of one token in p_{s} [if λ ∈ L ( γ ) ] or p_{f} [for λ ∉ L ( γ ) ].
Now we wish to be sure that every transition sequence in C leading from the initial marking to a final marking is “mimicked” in C′ . To this end we consider three types of strings in L ( γ ) . First, the empty string λ is properly handled by the definition of F′ . We can determine if λ ∈ L ( γ ) by checking if the initial marking μ is a final marking μ ∈ F. Second, for all strings of length 1 in L ( γ ), we include a special transition from p_{s} to p_{f} in C′ as follows: For α ∈ Σ with α ∈ L ( γ ), define t_{α} ∈ T′, with I ( t_{α} ) = { p_{s} } and O ( t_{α} ) = { p_{f} } . The label for t_{α} is α . We can determine if α ∈ L ( γ ) by checking all transitions t_{j} ∈ T, with σ ( t_{j} ) = α, to see if δ ( μ, t_{j} ) ∈ F.
Finally, consider all strings of length greater than 1.
These strings result from a transition sequence
t_{j1} t_{j2}... t_{ji} 
a t_{j1}′ ⋯ t_{ji}′ b 
a t_{j1}′ ⋯ t_{ji}′ b 
t_{j1}... t_{ji} 
Unfortunately this would produce a sequence which is too long since the extra symbols corresponding to transitions a and b would exist for C′ but not for C. One solution would be a null labeling for a and b, but the Ltype languages do not allow null labelings. So to solve this problem we are forced to collapse transitions a and t_{j1}′ into one transition t_{j1}′′ and collapse transition b and t_{ji}′ into t_{ji}′′′ . Thus for all t_{j} ∈ T we define the following transitions in T′:
σ′(t_{j}′)  =  σ′(t_{j}′′)  =  σ′(t_{j}′′′)  =  σ(t_{j}) 
α  =  σ′(t_{j1}′′ t_{j2}′ ⋯ t_{ji − 1}′ t_{ji}′′′) 
Figure 6.6 gives a simple Petri net which is not in standard
form. Applying the construction of the proof to this Petri
net produces the standard form Petri net of Figure 6.7.
We now examine the closure properties of Petri net languages under several forms of composition (union, intersection, concatenation, concurrency, and substitution) and under some operations (reversal, complement, and indefinite concatenation). The motivation for this examination is twofold. First, it increases our understanding of the properties and limits of Petri net languages as languages. Second, many of these compositions reflect how large systems are designed and constructed by the composition of smaller systems into larger systems. Thus, this investigation may help in the development of synthesis techniques.
Most of the closure properties deal with compositions of Petri net languages. For this we assume two Petri net languages L_{1} and L_{2}. We know that each of these languages is generated by some Petri net in standard form. Thus, we consider the two standard form labeled Petri nets γ_{1} = (C_{1}, σ_{1}, μ_{1}, F_{1} ) and γ_{2} = (C_{2}, σ_{2}, μ_{2}, F_{2} ) with L_{1} = L ( γ_{1} ) and L_{2} = L ( γ_{2} ) . Since they are in standard form, γ_{1} has a start place p_{s1} ∈ P_{1} and γ_{2} has p_{s2} ∈ P_{2}. Also F_{1} = { p_{s1}, p_{f1} } or { p_{f1} } and F_{2} = { p_{s2}, p_{f2} } or { p_{f2} } .
From these two labeled Petri nets we show how to construct a new labeled Petri net γ′ = (C′, σ′, μ′, F′ ) with language L ( γ′ ) which is the desired composition of L_{1} and L_{2}. We illustrate these constructions with example Petri nets.
We begin by considering the composition of two Petri net languages by concatenation, union, intersection, and concurrency. Then we consider the reversal and complement of a Petri net language and, finally, substitution.
Many systems are composed of two sequential subsystems.
Each of the subsystems may separately be expressed as a
Petri net with its own Petri net language. When the two
systems are combined sequentially, the resulting execution
is the concatenation of an execution from the first
Petri net language with an execution from the second. The
concatenation of two languages can be formally expressed as
L_{1}L_{2}  =  { x_{1} x_{2}  x_{1} ∈ L_{1}, x_{2} ∈ L_{2} } 
The formal definition of γ′ must take into
consideration the empty string and so is more complex but
can be defined as the union of γ_{1} and γ_{2}
with the following extra transitions. For each transition
t_{j} ∈ T_{2} with
I_{2}( t_{j} ) = { p_{s2} }, we
introduce a new transition t_{j}′ with
I′ ( t_{j}′ ) = { p_{f1} } and
O′ ( t_{j}′ ) = O_{2}( t_{j} ) .
If p_{s1} ∈ F_{1},
then we also add
t_{j}′′ with
I′ ( t_{j}′′ ) = { p_{s1} }
and O′ ( t_{j}′′ ) = O_{2}( t_{j} ) .
We define
σ′ ( t_{j}′ ) = σ_{2}( t_{j} )
and σ′ ( t_{j}′′ ) = σ_{2}( t_{j} ) .
The new final set F′ is
F_{1} ∪ F_{2}
if p_{s2} ∈ F_{2};
otherwise F′ = F_{2}.
Q.E.D.
This shows that Petri net languages are closed under
concatenation. Figure 6.8 illustrates this construction for
L_{1} = ( a + b )^{+} and
L_{2} = a^{n} b^{n}.
Another common method of combining systems is union.
In this composition either one, but only one, of the
subsystems will be executed. This is similar to set union
and is a common composition of languages. It can be defined
by
L_{1} ∪ L_{2}  =  { x  x ∈ L_{1} or x ∈ L_{2} } 
Formally we define a new start place
p_{s}′ and new transitions
t_{j1}′ for each
t_{j1} ∈ T_{1} with
I ( t_{j1} ) = p_{s1} and
t_{j2}′ for each
t_{j2} ∈ T_{2} with
I ( t_{j2} ) = p_{s2}. We define
I′ ( t_{j1}′ ) = p_{s}′ and
I′ ( t_{j2}′ ) = p_{s}′
with O′ ( t_{j1}′ ) = O_{1}( t_{j1} ) and
O′ ( t_{j2}′ ) = O_{2}( t_{j2} ) .
The labeling function
σ′ ( t_{j1}′ ) = σ_{1}( t_{j1} )
and σ′ ( t_{j2} ) = σ_{2}( t_{j2} ) . The new initial
marking has one token in p_{s}′ ; the new
final marking set F′ = F_{1} ∪ F_{2}. If
p_{s1} ∈ F_{1} or
p_{s1} ∈ F_{2}, then
p_{s}′ ∈ F′ also.
Q.E.D.
Still another way of combining two Petri nets is by allowing
the executions of two systems to occur concurrently.
This allows all possible interleavings of an execution of
one Petri net with an execution of the other Petri net.
Riddle [1972] has introduced the  operator to represent
this concurrency. It can be defined for a, b ∈ Σ
and x_{1}, x_{2} ∈ Σ^{*} by
a x_{1}  b x_{2}  =  a(x_{1}  b x_{2}) + b(a x_{1}  x_{2})  
a  λ  =  λ  a  =  a 
L_{1}  L_{2}  =  { x_{1}  x_{2}  x_{1} ∈ L_{1}, x_{2} ∈ L_{2} } 
It is easily shown that regular, contextsensitive, and type0 languages are closed under concurrency by demonstrating that the cross product of two finite state machines, linear bounded automata, or Turing machines is still a finite state machine, linear bounded automaton, or Turing machine, respectively. Since the cross product of two pushdown stack automata cannot be transformed into another pushdown stack automaton, contextfree languages are not closed under concurrency. For Petri net languages, we have the following theorem.
This construction is illustrated in Figure 6.10 for
L_{1} = a ( a + b )^{+} and
L_{2} = c a^{3n} c b^{2n} c.
As with union, the intersection composition is similar to
the set theory definition of intersection and is given for a
Petri net language by
L_{1} ∩ L_{2}  =  { x  x ∈ L_{1} and x ∈ L_{2} } 
The construction of a Petri net to generate the
intersection of two Petri net languages is rather complex.
At a given point in the generated string, if a transition fires
in one Petri net, there must be a transition in the other
Petri net with the same label which fires also. When more
than one transition exists in each Petri net with the same
label, we must consider all possible pairs of transitions
from the two Petri nets. For each of these pairs, we create
a new transition which fires if and only if both transitions
fire in the old Petri nets. This is done by making the
input (output) bag of the new transition the bag sum (see the
appendix) of the input (output) bags of the pair of
transitions from the old Petri nets. Thus if
t_{j} ∈ T_{1} and t_{k} ∈ T_{2} are such that
σ ( t_{j} ) = σ ( t_{k} ), then we have a
transition t_{j, k} ∈ T′
with I′ ( t_{j, k} ) = I_{1}( t_{j} ) + I_{2}( t_{k} ) and
O′ ( t_{j, k} ) = O_{1}( t_{j} ) + O_{2}( t_{k} ) .
Some of these transitions have inputs which include the
start place. If for a transition t_{j, k}
in T′, as defined above,
I′ ( t_{j, k} ) = { p_{s1}, p_{s2} }, then we
replace this transition with a new transition
t_{j, k}′, where
I′ ( t_{j, k}′ ) = { p_{s}′ } . This construction essentially
places the two original Petri nets in a lockstep identical
execution mode. This composite Petri net generates the
intersection of L_{1} and L_{2}. The construction is
demonstrated in Figure 6.11.
Unlike the previous composition operations which we have
examined, the operation of reversal seems to have only
academic interest. The reversal of a sentence
x^{R} is the sentence x with its symbols in the
reverse order. We define this recursively by
a^{R}  =  a 
(a x)^{R}  =  x^{R} a 
L^{R}  =  { x^{R}  x ∈ L } 
The construction is trivial. The start and final markings are interchanged, and the input and output bags for each transition are also interchanged and L ( γ′ ) = L ( γ )^{R}. This merely runs the Petri net backwards and reverses all generated strings.
The complement L of a language L over an alphabet
Σ is the set of all strings in Σ^{*} which are
not in L. This can be expressed as
L  =  Σ^{*} − L 
L  =  { x ∈ Σ^{*}  x \o′/∈′ L } 
Closure under complement for the Ltype Petri net languages is an open problem. However, CrespiReghizzi and Mandrioli [1977] have shown that some Petri net languages are not closed under complement; that is, there are Petri net languages whose complement is not a Petri net language.
So far we have considered the operations of union, intersection, concatenation, concurrency, reversal, and complement. Except for the last operation, we were able to give constructions that show that Petri net languages are closed under these operations. From these results we can immediately derive the following corollary.
A new operation can be defined by removing the constraint
that only a finite number of compositions be allowed. The
indefinite concatenation (Kleene star) of a language
is the set of all concatenations (of any length) of elements
from that language. This is represented by L^{*} and is
defined by
L^{*}  =  L ∪ L L ∪ L L L ∪ ⋯ 
This operation may be of practical use. Indefinite concatenation is similar to the modeling of a loop. Also it is known that regular, contextfree, contextsensitive, and type0 languages are closed under indefinite concatenation [Hopcroft and Ullman 1969]. Thus it is unexpected and perhaps unfortunate that Petri net languages are not closed under indefinite concatenation.
This appears to be due to the combination of the finite nature of Petri nets (finite number of places and transitions) and the permissive nature of the state changes [transitions are allowed (permitted) to fire but cannot be required to do so]. To construct a Petri net to generate the indefinite concatenation of a Petri net language would, in general, require the reuse of some portion of the Petri net. This allows tokens to be generated and left in some of the places which are reused. At a later repetition of the Petri net, these tokens may be used to allow transitions to fire when they should not.
The proof that Petri nets are not closed under indefinite
concatenation appears to be very difficult. Perhaps a
flavor of the approach can be given by considering an
example. We have already seen that
a^{n} b^{n} ( n > 1 ) is
a Petri net language. We claim that
( a^{n} b^{n} )^{*} is not a Petri
net language. All generators of
( a^{n} b^{n} )^{*} must have some
place or set of places that encode the number n for
each portion of the string. These tokens control the
generation of the b symbols. For a Petri net to
generate ( a^{n} b^{n} )^{*} it is
necessary to use these places more than once. But since the
net is permissive, there is no way to guarantee that these
places are empty before they are reused. Thus for any Petri
net which attempts to generate
( a^{n} b^{n} )^{*} there exists
some i, j, k such that the Petri net also
generates some string of the following form:
a^{n1} b^{n1}... a^{ni} b^{nj}... a^{nj} b^{ni}... a^{nk} b^{nk} 
For readers familiar with the formal language theory of Abstract Families of Languages (AFL) [Ginsburg 1975], it is easy to prove that Petri net languages are not closed under indefinite concatenation. It is well known that the smallest full AFL closed under intersection and containing { a^{n} b^{n} } contains every recursively enumerable set. Thus, since Petri net languages are closed under intersection and { a^{n} b^{n} } is a Petri net language, if they were closed under indefinite concatenation, they would be such an AFL. However, we know that { w w^{R} } is not a Petri net language (see Section 6.6.2), and so Petri net languages are not closed under indefinite concatenation. This argument is due to Mandrioli.
A subclass of Petri net languages exists which is closed under indefinite concatenation, however. This is the class of Petri net languages for properly terminating Petri nets. Proper termination was defined by Gostelow [1971] for complex bilogic graph models of computation. We borrow his definition and rephrase it in terms of Petri nets as follows.
We notice first that the second part of the definition is not actually a restriction since if the Petri net terminates, then it terminates in a finite amount of time and hence generates only a finite number of tokens. But the first part of the definition is a restriction. We may view the Petri net as a machine which generates strings of symbols. We place a token in the input to the machine, and a string of symbols is printed on a piece of tape for us. Eventually a light may come on saying that the machine has halted (i.e., there are no enabled transitions). In normal use, before we can use the printed output, we must look inside the machine and check that a final marking has been reached. If a final marking has not been reached, then we must reject the output and try again. If the Petri net is properly terminating, then we need not look inside the machine; we are guaranteed that a final marking has been reached.
We can see then how a properly terminating Petri net can be used to construct a Petri net generating the indefinite concatenation of its language. We simply connect the final place to the start place. Since the Petri net is known to be empty whenever a token appears at the final place, no tokens will be left in the Petri net to cause spurious transitions when the Petri net is reused.
Unfortunately, this subclass of Petri nets is not very interesting since we can show that all properly terminating Petri nets are finite state machines and vice versa. Hence the Petri net languages of properly terminating Petri nets are regular languages, and it is already known that this class of languages is closed under indefinite concatenation. Thus we see that the properties of systems modeled by Petri net languages are limited to finite repetitions of smaller subsystems or indefinite repetitions of smaller finite subsystems.
We have mentioned that systems can be designed and modeled hierarchically by Petri nets. This involves first specifying a rough outline of the system and then successively refining this outline by substituting for operations the definitions of these operations in terms of other operations. With Petri nets, this refinement may take the form of substituting a complete Petri net for a transition or a place. The latter is very straightforward; we therefore restrict our attention to considering the problem of substituting a subnet for a transition (or operation) of a Petri net.
When it is desired to substitute a Petri net for an operation in another Petri net, this can be considered as a composition of the Petri net languages of the two Petri nets. Since the operation is represented by a symbol from Σ, substitution of a Petri net language L_{2} for a symbol σ in another Petri net language L_{1} is defined as the replacement of all occurrences of σ in L_{1} by the set of strings L_{2}. Petri net languages are closed under substitution if the result of a substitution involving a Petri net language is also a Petri net language. Variations on substitution include finite substitution, where L_{2} must be a finite set of strings, and homomorphism, where L_{2} is a single string.
Again, unfortunately, we have a negative result. Petri net languages are not closed under general substitution. This is shown immediately by letting L_{1} = c^{*} and substituting L_{2} = a^{n} b^{n} for c in L_{1}. The problem is again caused by the possible reuse of a Petri net. For finite substitution and homomorphism, however, we see that L_{2} is a regular language, and hence a properly terminating Petri net can be constructed to generate it. This yields the following theorem and corollary.
Having considered the properties of Petri net languages as a class of languages, we turn to investigating the relationship between Petri net languages and other classes of languages. In particular, we consider the classes of regular, contextfree, contextsensitive, and type0 languages.
One of the simplest and most studied classes of formal languages is the class of regular languages. These languages are generated by regular grammars and finite state machines. They are characterized by regular expressions. Problems of equivalence or inclusion between two regular languages are decidable, and algorithms exist for their solution [Hopcroft and Ullman 1969]. With such a desirable set of properties, it is encouraging that we have the following theorem.
The proof of this theorem is based on the fact that every regular language is generated by some finite state machine and we have shown (Section 3.3.1) that every finite state machine can be converted to an equivalent Petri net.
The converse to this theorem is not true. Figure 6.12
displays a Petri net which generates the contextfree
language { a^{n} b^{n}  n > 1 } .
Since this language is not regular, we know that not
all Petri net languages are regular languages.
Figure 6.12 demonstrated that not all Petri net languages
are regular languages by exhibiting a Petri net language
which was contextfree but not regular. Figure 6.13 shows
that not all Petri net languages are contextfree by
exhibiting a Petri net language which is contextsensitive
but not contextfree. Unlike the situation with regular
languages, however, there also exist contextfree languages
that are not Petri net languages. An example of such a
language is the contextfree language
{ w w^{R}  w ∈ Σ^{*} } .
This results in the
following theorem.
δ(μ, x_{1} x_{2}^{R})  =  δ(δ(μ, x_{1}), x_{2}^{R}) 
=  δ(δ(μ, x_{2}), x_{2}^{R})  
=  δ(μ, x_{2} x_{2}^{R}) ∈ F 
In Section 4.2.2, we showed that for each transition
t_{j} there exists a vector
v_{j} = e [ j ] ⋅ D
such that if δ ( q, t_{j} ) is defined,
then the value of δ ( q, t_{j} ) is
q + v_{j}. Thus after r inputs, we have a
state q_{r} where
q_{r}  =  μ +  Σ  v_{ij} 
j 
q_{r}  =  μ +  Σ  f_{j} v_{j} 
j 
Σ  f_{j}  =  r 
j 
At best the vectors
v_{1}, v_{2}, …, v_{m}
will be linearly independent, and each firing
vector ( f_{1}, f_{2}, …, f_{m} )
will represent a unique state
q_{r}. Since the sum of the coefficients is
r, the vector
( f_{1}, f_{2}, …, f_{m} )
is a partition of the integer
r into m parts. Knuth [1973] has shown that the
number of partitions of an integer r into m
parts is
r + m − 1 
m − 1 
&leftbigparen;

= 

<  (r + m)^{m} 
r + m − 1 
The proof that w w^{R} is not a Petri net language sheds some light on the limitations of Petri nets as automata and hence on the nature of Petri net languages. Petri nets are not capable of remembering arbitrarily long sequences of arbitrary symbols. From the proof, we see that Petri nets can remember sequences of bounded length (but so can finite state machines). Another feature of Petri nets is the ability to remember the number of occurrences of a symbol, such as in a^{n} b^{n} c^{n}, to an extent that regular and contextfree generators cannot. However, a Petri net cannot simulate the power of a pushdown stack, which is necessary to generate contextfree languages. The rate of growth of the reachable state space for a Petri net is combinatorial with the length of the input and not exponential as needed for a pushdown stack.
The reason that Petri nets are able to generate languages which a pushdown stack cannot generate despite the smaller state space is because of the more flexible interconnections between states in the Petri net compared to the restrictive paths between states allowed in a pushdown stack automaton. This results from restricting the pushdown stack automaton to accessing only the top of the stack, while the Petri net can access any of its counters at any time.
Having shown that not all contextfree languages are Petri net languages and not all Petri net languages are contextfree, the question arises as to what is the class of languages which are both contextfree and Petri net languages? At present we cannot fully answer this question, but we can give an indication of some of the members of this intersection. One subset of both contextfree and Petri net languages is, of course, the class of regular languages. Another subset is the set of bounded contextfree languages investigated by Ginsburg [1966].
A contextfree language L is bounded contextfree
if there exist words (or strings)
w_{1}, w_{2}, …, w_{m}
from Σ^{*} such that
L ⊆ w_{1}^{*} w_{2}^{*}... w_{m}^{*} 
Bounded contextfree languages are characterized by the following theorem of Ginsburg [1966, Theorem 5.4].
We have already shown (Section 3.3.1) that every finite state machine and hence every regular language and every finite subset of Σ^{*} is a Petri net language. In Sections 6.5.1 and 6.5.2 we showed that Petri net languages are closed under concatenation and union. Thus we have only to show that 3 above is satisfied for Petri net languages. To show this, we would construct a Petri net γ′ = (C′, Σ, μ′, F′ ) which generates the Petri net language { x^{i} W y^{i}  i ≥ 0 } given standard form Petri nets γ_{x} = (C_{x}, Σ, μ_{x}, F_{x} ), γ_{y} = (C_{y}, Σ, μ_{y}, F_{y} ), and γ_{W} = (C_{W}, Σ, μ_{W}, F_{W} ) that generate x, y, and W, respectively. γ′ combines the Petri nets γ_{x}, γ_{y}, and γ_{W} and a new place p so that each time γ_{x} is executed, a token is placed in p. The place p counts the number of times γ_{x} is executed. After γ_{x} has executed as many times as it wishes, γ_{W} is executed, and finally γ_{y} is executed repeatedly, removing one token from p for each repetition. Since the input string is correctly generated only if the Petri net is empty (except for F′ which is defined to be F_{y} ), we are assured that the number of executions of γ_{x} and γ_{y} are equal.
This construction, which is demonstrated in Figure 6.14, for
x = a b, y = b ( a + b ),
and W = b^{+} a, shows that
{ x^{i} W y^{i}  i ≥ 0 }
is a Petri net language. Thus any
bounded contextfree language is a Petri net language.
Are there contextfree languages which are also Petri net languages but not bounded? Unfortunately, the answer is yes. Ginsburg shows that the regular expression ( a + b )^{+} is not a bounded contextfree language. Since this language is a contextfree Petri net language, we see that bounded contextfree languages are only a proper subset of the family of contextfree Petri net languages. We also exhibit the language { ( a + b )^{+} a^{n} b^{n}  n > 1 } which is a contextfree Petri net language but is neither bounded nor regular. Further research is needed to completely characterize the set of contextfree Petri net languages.
The presence of both regular sets and bounded contextfree languages as subsets of the class of Petri net languages is encouraging since both classes of languages have several desirable properties and some nice analysis characteristics.
We have investigated the relationship between Petri net languages and regular languages and between Petri net languages and contextfree languages. Now we turn to contextsensitive languages. Figure 6.13 has shown that some Petri net languages are contextsensitive; below we prove that all Petri net languages are contextsensitive. Since we know that all contextfree languages are also contextsensitive and that there exist contextfree languages which are not Petri net languages, we know that there exist contextsensitive languages which are not Petri net languages. Thus the inclusion is proper.
The proof that all Petri net languages are contextsensitive is rather complex. There are two ways to show that a language is contextsensitive: Construct a contextsensitive grammar which generates it, or specify a nondeterministic linear bounded automaton which generates it. Peterson [1973] has shown how to define a contextsensitive grammar to generate a Petri net language; here we indicate why a linear bounded automaton can generate a Petri net language.
A linear bounded automaton is similar to a Turing machine. It has a finite state control, a read/write head, and a (twoway infinite) tape. The limiting feature which distinguishes it from a Turing machine is that the amount of tape which can be used by a linear bounded automaton to generate a given input string is bounded by a linear function of the length of the input string. In this sense it is similar to the pushdown stack automaton used to generate contextfree languages (since the maximum length of the stack is bounded by a linear function of the input string) except that the linear bounded automaton has random access to its memory, while the pushdown automaton has access to only one end of its memory.
To generate a Petri net language, one can simulate the Petri
net by remembering, after each input, the number of tokens
in each place. How fast can the number of tokens grow as a
function of the input? Consider the number of tokens after
r transition firings. This number, denoted by
c, is, for a transition sequence
t_{i1} t_{i2}... t_{ir},
c  =  1 +  Σ   O(t_{ij})  −  I(t_{ij})  
j 
l  =  max   O(t_{j})  −  I(t_{j})  
t_{j} ∈ T 
c  =  1 +  Σ   O(t_{ij})  −  I(t_{ij})  
j  
≤  1 + r ⋅ l 
With this proof, we have shown that all Petri net languages
are contextsensitive languages. We summarize the results
of our investigation into the relationship between the class
of Petri net languages and other classes of languages in the
graph and Venn diagram of Figure 6.15.
Figure 6.16 summarizes the properties of Petri net
languages. It is drawn from [Peterson 1976] and [Hack 1975b].
L^{f}  L  L^{λ}  P^{f}  P  P^{λ}  
Closure under  
Union  No  Yes  Yes  ?  Yes  Yes  
Intersection  Yes  Yes  Yes  Yes  Yes  Yes  
Concatentation  ?  Yes  Yes  ?  Yes  Yes  
Concurrency  ?  Yes  Yes  ?  Yes  Yes  
Regular substitution  No  λfree  Yes  ?  Prefix  Prefix  
Inverse homomorphism  Yes  Yes  Yes  Yes  Yes  Yes  
Kleene star (iteration)  ?  No  No  ?  ?  ?  
Complement  No  ?  No  No  ?  No  
Contains regular languages  No  Yes  Yes  No  Prefix  Prefix  
Symmetric difference with contextâ€”free languages (nonempty)  Yes  Yes  Yes  Yes  Yes  Yes  
Is contextsensitive  Yes  Yes  ?  Yes  Yes  ? 
Most of the results presented here have been developed in both [Peterson 1976] and [Hack 1975b]. In addition, Hack has investigated a number of decidability problems for Petri net languages. The membership problem [Is a string α an element of a language L ( γ ) ?] is decidable, while the emptiness problem [Is the language L ( γ ) empty?] can be easily seen to be equivalent to the reachability problem. It is undecidable if two Petri net languages are equal or if one is contained within the other (the equivalence and inclusion problems).
Figure 6.17 summarizes these results.
L  L  L^{λ}  P^{f}  P  P^{λ}  
Decision Problems  
Membership  D  D  ?  D  D  D 
Emptiness  ?  ?  ?  D  D  D 
Finiteness  ?  ?  ?  D  D  D 
Equivalence and inclusion  ?  U  U  ?  U  U 
A different approach to the study of Petri nets by the use of formal language theory has been considered by CrespiReghizzi and Mandrioli [1974]. They noticed the similarity between the firing of a transition and the application of a production in a derivation, thinking of places as nonterminals and tokens as separate instances of the nonterminals. The major difference is, of course, the lack of ordering information in the Petri net which is contained in the sentential form of a derivation. This resulted in the definition of the commutative grammars, which are isomorphic to Petri nets. In addition CrespiReghizzi and Mandrioli considered the relationship of Petri nets to matrix [Abraham 1970], scattered context, nonterminal bounded, derivation bounded, equalmatrix, and Szilard languages. For example, it is not difficult to see that the class L^{f} is the set of Szilard languages of matrix contextfree languages [CrespiReghizzi and Mandrioli 1977; Hopner and Opp 1977].
There are three good studies on Petri net languages. [Peterson 1976] or [Peterson 1977] is probably the easiest to get, although [Hack 1975b] is a more rigorous and complete investigation. [CrespiReghizzi and Mandrioli 1974] is rather hard to find, but nonetheless it is an excellent piece of work, quite inventive and well explained.
Although a good start on research into the properties of Petri nets has been made, much still remains to be done. Of the classes of languages which have been defined, only two, the classes of Ptype and Ltype languages, have been studied and these only for generalized Petri nets. Several subsets of the set of general Petri nets have been defined, including marked graphs, conflictfree nets, restricted nets, and freechoice nets, as we see in Chapter 7. Each of these classes of Petri nets presumably has its own class of languages with its own distinctive properties. Some investigation of these classes has been done. It is known [Hack 1975b] that the classes L, L^{λ}, G, G^{λ}, P, and P^{λ} for restricted Petri nets [no selfloops, no multiple arcs; i.e., all bags are sets, and for every t_{j}, I ( t_{j} ) ∩ O ( t_{j} ) = ∅ ] are identical to the corresponding classes for generalized Petri nets. It is also not difficult to see that the classes L^{λ}, G^{λ}, and P^{λ} are not changed by restricting the nets to freechoice nets (see Section 7.4.3). This still leaves many interesting cases to be studied. In particular, the languages generated by marked graphs, or by conflictfree nets in general, seem to have a structure reminiscent of deterministic contextfree languages, and their study should be very promising.
Another important open problem concerns the distinction between λ free languages ( L, P, …) and unrestricted languages ( L^{λ}, P^{λ}, …). It is not known whether L = L^{λ} or not, for example.
Home  Comments? 