Home  Up  Questions? 
A class of automata based upon generalized Petri nets is introduced and defined. The language which a Petri net generates during an execution is called a computation sequence set (CSS). The class of CSS languages is shown to be closed under union, intersection, concatenation, and concurrency. All regular languages and all bounded contextfree languages are CSS, while all CSS are contextsensitive. Not all CSS languages are contextfree, nor are all contextfree languages CSS. Decidability problems for CSS hinge on the emptiness problem for CSS. This problem is equivalent to the reachability problem for vector addition systems, and is open.
Petri nets have been used by several researchers for the description and analysis of systems of parallel processes [8, 9, 16, 17, 18]. Although the majority of current research with Petri nets is still directed toward parallel computation, in this paper we consider Petri nets as an automaton in the same way as finite state machines, pushdown stack automata, and Turing machines. Viewed in this way, a language can be naturally associated with the execution of a Petri net. Consideration of the properties of the class of languages generated by Petri nets yields both new properties of Petri nets and an interesting addition to formal language theory.
We first define the new class of automata based on Petri nets. Then, the language of a Petri net, called a computation sequence set (CSS), is defined. A computation sequence set contains all possible computation sequences which may represent an execution of a Petri net from its start state to a final state. Formal definitions of these concepts are given in Section 2. Section 3 investigates the closure properties of the class of computation sequence sets, and Section 4 relates this new class of languages to the classical hierarchy of regular, contextfree, contextsensitive, and type0 languages. Section 5 then considers some decidability questions and conclusions about CSS as a class of languages.
We begin by giving a definition for the class of Petri nets. This definition follows the approach of [17] and is essentially the same as the Generalized Petri Nets of [6] although different notation is used. This general definition subsumes, or is equivalent to, most other definitions of Petri nets.
A Petri net, C, is a 5tuple defined by
where
Each transition, t_{j} ∈ T, is an ordered triple defined by
(The Appendix gives a brief summary of the theory and notation of bags. Bags are essentially an extension of sets which allow multiple occurrences of an element in a bag. The number of occurrences of an element x in a bag β is given by the function #(x, β). Our use of bags is for descriptive purposes, so we use the notation and concepts of set theory with which the reader should be familiar. For a more complete development of bag theory, the reader is referred to [2].)
The sets P, T, Σ are assumed to be finite. The cardinality of the set P is n and of the set T, m. Arbitrary elements of P and T are denoted by p_{k} (1 ≤ k ≤ n) and t_{j} (1 ≤ j ≤ m), respectively. The set Σ is not generally defined explicitly since it can be inferred from the definitions of the transitions (Σ = {σ_{j}  (σ_{j}, I_{j}, O_{j}) ∈ T}). We use σ, σ_{j} and early lowercase Roman letters (a, b, c,...) to represent elements of Σ.
An example Petri net is defined in Figure 1.
C  =  (P, T, Σ, S, F) 
P  =  {p_{1}, p_{2}, p_{3}, p_{4}, p_{5}} 
T  =  {t_{1}, t_{2}, t_{3}, t_{4}} 
Σ  =  {a, b, c} 
S  =  p_{1} 
F  =  {p_{5}} 
t_{1}  =  (a, {p_{1}}, {p_{2}, p_{3}, p_{3}, p_{5}}) 
t_{2}  =  (b, {p_{2}, p_{3}, p_{5}}, {p_{5}}) 
t_{3}  =  (c, {p_{3}}, {p_{4}}) 
t_{4}  =  (c, {p_{4}}, {p_{2}, p_{3}}) 
Figure 1. Definition of an example Petri net.
When working with Petri nets, we need to refer to the separate components of the ordered triples which define the transitions. To allow us to specify easily the portion of a transition which we are discussing, we define three projection functions  the label function (σ), the input function (I), and the output function (O). For a transition t_{j} = (σ_{j}, I_{j}, O_{j}), these functions are defined by
σ(t_{j})  =  σ_{j} 
I(t_{j})  =  I_{j} 
O(t_{j})  =  O_{j} 
To map sequences of transitions into sequences of symbols, we extend the label function by
σ(x)  =  ε  if x  =  ε,  
σ(x)  =  σ(t_{j})σ(y)  if x  =  t_{j}y, t_{j} ∈ T, y ∈ T*. 
(We use ε to denote the empty sequence. Σ* denotes the set of all strings over an alphabet Σ.)
A convenient visual representation of a Petri net is a bipartite directed graph. Both places and transitions are represented as nodes in the graph. To distinguish them, places are represented by circles and transitions by bars. An arc is directed from a transition t_{j} to a place p_{k} for each occurrence of p_{k} in the output bag, O(t_{j}), of the transition. An arc is directed from a place p_{k} to a transition t_{j} for each occurrence of p_{k} in the input bag, I(t_{j}), of t_{j}. Since the ordering of places and transitions is unimportant, the start place is assumed to be p_{1}. Final places are indicated by a circle around the node representing them. The Petri net of Figure 1 is graphed in Figure 2.
Figure 2. Graphical representation of the Petri net of Figure 1.
The graph representation of a Petri net contains all the information which is necessary to define the net. Thus we give graph representations of Petri nets rather than formal definitions for our illustrations.
The above definitions are concerned with the description of the structural properties of a Petri net. Since the Petri net is an abstract machine, it also has computational properties. The computational properties refer to its behavior during an execution. The execution of a Petri net is directed by the existence and location of tokens in the net. Tokens are abstract entities which we represent by black dots in the circles of the graphical representation of a Petri net. Tokens move about the Petri net in a manner dictated by the execution rules for Petri nets. These rules are
A transition is enabled if all of its input places have (a sufficient number of) tokens in them. A transition fires by removing tokens from all of its input places and placing tokens in all of its output places. These definitions are made more precise by
Execution of a Petri net begins with one token in the start place. Each time that a transition fires, it may change the number and/or location of tokens in the Petri net and therefore the state of the net. A Petri net may halt whenever it reaches a final state (one token in a final place and zero tokens elsewhere) or it may continue execution. If the set, U, of enabled transitions is empty, the Petri net must halt.
Figure 3 illustrates the concept of the execution of a Petri net by using the graphical representation of Figure 2 to present one possible execution. At each step, the Petri net and its tokens are given as well as the set U of enabled transitions and the selected transition which fires.
Figure 3. One possible execution of the Petri net of Figure 1.
The state of a Petri net is defined by the number and location of tokens in the net. This can also be expressed as the number of tokens (possibly zero) in each place of the net and is commonly called a marking. The number of tokens in each place will always be a nonnegative integer number, and we represent the state of a Petri net by an nvector of nonnegative integers. The firing of a transition represents a change in the state of the Petri net. A state is reachable if there exists some sequence of firings which transforms the start state (the state associated with one token in the start place and zero tokens elsewhere) into the desired state.
We define Q to be the reachable state space of a Petri net. Q is also called the marking class of a Petri net. If N represents the set of nonnegative integers then Q ⊆ N^{n}. Each element of Q is an nvector whose kth component represents the number of tokens in place p_{k} (1 ≤ k ≤ n). We denote by S both the start place and the vector (1, 0, 0,...); F denotes both the set of final places and the set of vectors representing one token in a final place and zero tokens elsewhere (the final states).
The nextstate function, δ, is a (partial) function from N^{n} × T into N^{n}. For a state vector, q, and a transition, t_{j}, the nextstate function, δ(q, t_{j}), is defined if and only if for all k, 1 ≤ k ≤ n,
Thus a transition t_{j} is enabled in a state q if and only if δ(q,t_{j}) is defined. If δ(q, t_{j}) is defined, then the new state vector defined is the state resulting from the firing of t_{j}. The kth component of the new state is defined by
Since q_{k} ≥ #(p_{k},I(t_{j})) if δ(q,t_{j}) is defined and #(p_{k},O(t_{j})) ≥ 0, we see that if δ(q,t_{j}) is defined, then δ(q,t_{j}) ≥ 0 and hence δ(q, t_{j}) ∈ N^{n}.
The definition of δ(q,t_{j}) can be recast as a vector replacement system [12]. We specify, for each transition, t_{j}, two vectors, u_{j}, and v_{j}, where (u_{j})_{k} = #(p_{k}, I(t_{j})) and (v_{j})_{k} = #(p_{k}, I(t_{j})) + #(p_{k}, O(t_{j})). Then δ(q,t_{j}) is defined if q + u_{j} ≥ 0, and if δ(q,t_{j}) is defined, then δ(q,t_{j}) = q + v_{j}. The reachable state space of a Petri net corresponds to the reachability set of a vector replacement system (see Section 5).
As with the label function, we extend the nextstate function
from a domain of individual transitions to a domain of sequences
of transitions. If x is a sequence of transitions (x ∈
T*), then
δ(q,x)  =  q  if x = ε,  
=  δ(δ(q,t_{j}),y)  if x = t_{j}y for t_{j} ∈ T, y ∈ T*. 
Of course δ(q,x) is defined if and only if the nextstate functions of the above definition are defined for their arguments.
We can now formally define the reachable state space, Q, as the smallest subset of N^{n} defined by
Since we are concerned only with reachable states, we restrict the nextstate function to the reachable state space, Q. Thus, δ: Q × T* → Q, and (except perhaps for the start state) the mapping is onto.
It should be clear from the definition of the state space, the nextstate function, and the reachable state space that the automaton defined by (Q, δ, Σ, S, F) is equivalent to (P, T, Σ, S, F) as a mathematical formulation of a Petri Net. We use both definitions interchangably,
Each separate execution of a Petri net defines, or is defined by, the sequence of transitions which are fired during the execution of the net. We say that a sequence of transitions, x ∈ T*, is legal if it represents a possible sequence of transition firings from the start state, S. Thus a sequence is legal if δ(S, x) is defined. A sequence is complete if it is legal and δ(S, x) ∈ F.
To illustrate these concepts, consider the execution shown in
Figure 3. This execution is completely defined by the transition
sequence t_{1}t_{3}t_{4}t_{2}t_{2}. For this example, the sequence is both
legal and complete. The sequences t_{1}t_{3}t_{4} and
t_{1}t_{3}t_{3}t_{4}t_{4}t_{2}t_{2} are legal but not complete, since
δ(S, t_{1}t_{3}t_{4})  =  (0,2,2,0,1), 
δ(S, t_{1}t_{3}t_{3}t_{4}t_{4}t_{2}t_{2})  =  (0,1,0,0,1), 
The sequences t_{1}t_{4}, t_{2}t_{3}t_{3}t_{4}, and t_{4} are neither complete nor legal.
Associated with each sequence of transitions, x ∈ T*, is the sequence of symbols, y ∈ Σ*, defined by y = σ(x). A sequence of symbols which corresponds to a legal and complete transition sequence is a computation sequence. Each computation sequence represents one (or more than one) execution of the Petri net which begins with one token in the start place and ends with one token in a final place, while all other places have zero tokens both before and after the execution (although probably not during the execution). The computation sequence set of a Petri net is the set of all computation sequences for that net. We denote the computation sequence set of a Petri net, C, by L(C). Formally,
Many Petri nets may generate the same CSS. We define two Petri nets to be equivalent if their CSS are equal. The CSS is the language of the Petri net and is considered the characterizing feature of the net.
The nextstate function is again extended to be defined over computation sequences as well as transition sequences by defining δ(q, y) = q' for any string y ∈ Σ* for which there exists a transition sequence, x ∈ T*, with y = σ(x) and δ(q, x) = q'. Note that with this definition δ may no longer be singlevalued, but may yield a set of states. If δ is not singlevalued, then the Petri net is nondeterministic. We define a CSS to be nondeterministic if every Petri net which generates it is nondeterministic. A deterministic CSS is then a CSS for which there exists a deterministic Petri net which generates it. Figure 4 is a nondeterministic Petri net with a nondeterministic CSS.
Figure 4. An inherently nondeterministic Petri net.
(The proof that no equivalent Petri net is deterministic is similar to the proof in [4] that this CSS is an inherently nondeterministic contextfree language.)
Having defined the Petri net automaton and its associated language, we turn now to investigating the properties of the class of CSS languages. We begin our investigation by considering the closure properties of CSS under union, intersection, concatenation, and concurrent composition. We first define a restricted class of Petri nets whose special properties are convenient in the proofs of closure under these forms of composition.
Figure 5. A "pathological" Petri net.
The general definition of Petri nets in Section 2 allows the construction of "pathological" Petri nets, such as the net of Figure 5, whose strange properties make the proofs which follow unnecessarily complicated. In particular, the transitions with empty input or output bags require special attention. We avoid these problems by showing that such transitions can be eliminated without changing the language of the Petri net. This is done by introducing a new place, p_{r}, to the net. This place is made an input and output to every transition in the net. As long as there is a token in this place, the possible transition sequences are identical to the transition sequences of the original net; when this token is removed, all transitions are disabled. Using this approach we introduce a new start place S' and final place, p_{f}. New transitions are added which mimic the old transitions except that the first transition to fire places a token in p_{r}, and the last transition to fire removes this token. From this construction, we define a restricted class of Petri nets in standard form by
DEFINITION. A Petri net, C = (P, T, Σ, S, F) is in standard form if
A Petri net in standard form has no transitions with empty input or output bags. It also has a start place which is an output of no transition and a special "final" place which is an input to no transition.
The execution of a Petri net in standard form starts with one token in the start place. The first transition removes this token and after this firing the start place is always empty. Eventually (if the transition sequence is complete) a token is placed in the final place. This token cannot be removed from the final place both because no transition has an input from the final place and because all transitions are disabled. The restrictive nature of the standard form Petri nets is useful when defining compositions of Petri nets. To show that standard form Petri nets are not less powerful than general Petri nets, we prove the following theorem.
Theorem 1. Every Petri net is equivalent to a Petri net in standard form.
Let C = (P, T, Σ, S, F) be a Petri net.
Define C' = (P', T', Σ, S', F') by
P'  =  P ∪ {S', p_{r}, p_{f}},  where {S', p_{r}, p_{f}} ∩ P = ∅,  
F'  =  {S',p_{f}}  if S ∈ F,  
=  {p_{f}}  if S ∉ F. 
We define four kinds of transitions in the set T'. First, for all
t_{j} ∈ T, we include a transition t_{j}' = (σ(t_{j}), I(t_{j}) + {p_{r}}, O(t_{j})
+ {p_{r}}) in T'. To start the net we consider that two kinds of
transitions in T could fire first; those with I(t_{j}) = {S} and
those with I(t_{j}) = ∅. For each of these we define t_{j}'' by
t_{j}''  =  (σ(t_{j}), {S'}, O(t_{j}) + {S, p_{r}})  if I(t_{j}) = ∅ ,  
=  (σ(t_{j}), {S'}, O(t_{j}) + {p_{r}})  if I(t_{j}) = {S}. 
Similarly the last transition to fire could be either a
transition with O(t_{j}) = ∅ or O(t_{j}) = {p_{k}} such that
p_{k} ∈ F. For each of these we define t_{j}''' by
t_{j}'''  =  (σ(t_{j}), {p_{r}} + I(t_{j}), {p_{f}}) 
These transitions define a legal and complete transition sequence
t_{j1}'' t_{j2}' t_{j3}' ... t_{jl1}' t_{jl}''' (l > 2) 
Figure 6. A standard form Petri net equivalent to the Petri net of Figure 5.
We consider two CSS L_{1} and L_{2} and two Petri nets in standard form, C_{1} = (P_{1}, T_{1}, Σ, S_{1}, F_{1}) and C_{2} = (P_{2}, T_{2}, Σ, S_{2}, F_{2}) with L_{1} = L(C_{1}) and L_{2} = L(C_{2}). We construct a new Petri net, C' = (P', T', Σ, S', F') whose language, L' = L(C'), is the desired composition of L_{1} and L_{2}. Figure 7 gives example Petri nets for C_{1} and C_{2} which we use in our discussions to illustrate the construction of C'.
Figure 7. Illustration Petri nets.
The concatenation of two languages can be formally expressed as
L_{1}L_{2}  =  {x_{1}x_{2}  x_{1} ∈ L_{1} and x_{2} ∈ L_{2}}. 
Theorem 2. If L_{1} and L_{2} are CSS, then the concatenation of L_{1} and L_{2} is CSS.
We define a Petri net, C' = (P', T', Σ, S', F'), where
P'  =  P_{1} ∪ P_{2},  
T'  =  T_{1} ∪ T_{2} ∪ {(σ_{j}, {p_{f}}, O_{j})  (σ_{j}, {S_{2}}, O_{j}) ∈ T_{2}, p_{f} ∈ F_{1}},  
S'  =  S_{1},  
F'  = 

With this definition we have overlapped the final places of C_{1} with the start place of C_{2}. The transition which signals the termination of C_{1} by placing a token in an element of F_{1} acts to initiate C_{2} by placing a token in a place equivalent to S_{2}. Since both nets are in standard form, all transitions of the C_{1} subnet are disabled when the token is placed in a final place of F_{1}, and all transitions of the C_{2} subnet are disabled until a token is placed in one of these places. Any "extra" tokens produced by an execution of the C_{1} subnet remain in that net after the token is placed in an element of F_{1}, so that C' cannot reach a final state unless both C_{1} and C_{2} have reached final substates. Thus, if a sentence is generated by C', it must be composed of a sentence which was generated by C_{1} followed by a sentence generated by C_{2}, and is in the concatenation of L_{1} and L_{2}. Similarly, any computation sequence in the concatenation has a path from S_{1} to an element of F_{2} in C', and is an element of L'. This shows that CSS are closed under concatenation. Figure 8 illustrates this construction.
Figure 8. A Petri net whose CSS is the concatenation of the Petri nets of Figure 7.
Since languages are sets of strings, a common method of
composition is to take the union of two languages. This is
defined as
L_{1} ∪ L_{2}  =  { x  x ∈ L_{1} or x ∈ L_{2}}. 
Theorem 3. If L_{1} and L_{2} are CSS, then the union of L_{1} and L_{2} is CSS.
We construct C' with L(C') = L_{1} ∪ L_{2}. The definition of C' is
P'  =  P_{1} ∪ P_{2} ∪ {S'},  
T'  =  T_{1} ∪ T_{2} ∪ {(σ_{j}, {S'}, O_{j})  (σ_{j}, {S_{1}}, O_{j}) ∈ T_{1} or (σ_{j}, {S_{2}}, O_{j}) ∈ T_{2}},  
S'  =  S_{1},  
F'  = 

This construction introduces one new start place and transitions which make this new start place equivalent to both S_{1} and S_{2}. Placing the start token in S' enables a transition corresponding to every transition which would be enabled by placing a start token in S_{1} or S_{2}. When one of these transitions fires, the output tokens are placed in a subnet defined by (P_{1}, T_{1}) or (P_{2}, T_{2}) and execution continues exactly as it would in C_{1} or C_{2}. The null sequence is included by the definition of F'. This construction generates L_{1} ∪ L_{2}. Thus CSS are closed under union. The construction of C' from C_{1} and C_{2} is illustrated in Figure 9 for the C_{1} and C_{2} of Figure 7.
Figure 9. A Petri net whose CSS is the union of the CSS of the Petri nets of Figure 7.
As with union, the intersection composition is similar to the set
theory definition of intersection and is given for CSS by
L_{1} ∩ L_{2}  =  { x  x ∈ L_{1} and x ∈ L_{2}}. 
Theorem 4. If L_{1} and L_{2} are CSS, then the intersection of L_{1} and L_{2} is CSS.
The construction of a Petri net to generate the intersection of two CSS is rather complex. At a given point in a computation sequence if a transition fires in one Petri net, there must be a transition in the other Petri net with the same label which can fire also. When there exists more than one transition in each Petri net with the same label, we consider all possible pairs of transitions from the two nets. For each of these pairs, we create a new transition which can fire if and only if both transitions in the old nets can fire. This is done by making the input (output) bag of the new transition the bag sum 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}) = σ_{jk}, then we have a transition t_{jk} = (σ_{jk}, I_{j} + I_{k}, O_{j} + O_{k}) in T'. Some of these transitions will have inputs which include the start place. If for a transition t_{jk} in T' as defined above, I(t_{jk}) = {S_{1}, S_{2}}, then we add a transition t'_{jk} with I(t'_{jk}) = {S'}, and other components equal. Similarly, for any transition t_{jk} with O(t_{jk}) = {p_{f1}, p_{f2}} with p_{f1} ∈ F_{1} and p_{f2} ∈ F_{2}, we add a new transition t''_{jk} which is equal to t_{jk} except that O(t''_{jk}) = {p_{f}'}. F' is {p_{f}', S'} if S_{1} ∈ F_{1} and S_{2} ∈ F_{2} and {p_{f}'} otherwise. Figure 10 illustrates this construction.
Figure 10. A Petri net whose CSS is the intersection of the CSS of the Petri nets of Figure 7.
Concurrent composition allows all possible interleavings of a computation sequence from one CSS with a computation sequence from another CSS. Riddle [19] has introduced the Δ operator to represent this concurrency. The concurrency operator has also been called the "shuffle" operator [5]. It is defined for two strings by
where a, b ∈ Σ, and x_{1}, x_{2} ∈ Σ*. The
concurrent composition of two languages is then
L_{1} Δ L_{2}  =  {x_{1} Δ x_{2}  x_{1} ∈ L_{1} and x_{2} ∈ L_{2}}. 
For example, ab Δ c = abc + acb + cab, (a + b) Δ c = ac + ca + bc + cb. (The shuffle operator was defined so that it appears that strict alternation of elements of two strings is required. That is, if x = x_{1}x_{2}... x_{k} and y = y_{1}y_{2} ... y_{k}, then shuffle(x,y) = x_{1}y_{1}x_{2}y_{2} ... x_{k}y_{k}. However, x_{i} and y_{i} are allowed to be (possible null) strings, not simply elements, of the alphabet.)
It is easily shown that regular, contextsensitive and type0 languages are closed under concurrency, while contextfree languages are not. For CSS, we have
Theorem 5. If L_{1} and L_{2} are CSS, then the concurrent composition of L_{1} and L_{2} is CSS.
The construction of a Petri net to generate the concurrent
composition of L_{1} and L_{2} given nets to generate these CSS is
basically the construction of a Petri net which places tokens in
both the start places of C_{1} and C_{2}, and then accepts the
input if tokens are in any two final places (one from each net),
and no other places. To start the combined Petri net we
introduce a new start place, S'. The first transition which
fires in the concurrent composition of two CSS will come from
either C_{1} or C_{2}. If the first transition which
fires is from C_{1}, then we modify it to also place a
token in S_{2}, allowing the Petri net C_{2} to then start
whenever it wishes. A similar strategy is used if the first
transition is from C_{2}. Thus C' is defined by
P'  =  P_{1} ∪ P_{2} ∪ {S', p_{f}'}, 
T'  =  T_{1} ∪ T_{2} ∪ T_{SF}, 
F'  =  {p_{f}'}, 
where,
T_{SF}  =  {(σ_{j}, {S'}, O_{j} + {S_{2}})  (σ_{j}, {S_{1}}, O_{j}) ∈ T_{1}} 
∪  {(σ_{j}, {S'}, O_{j} + {S_{1}})  (σ_{j}, {S_{2}}, O_{j}) ∈ T_{2}}  
∪  {(σ_{j}, I_{j} + {p_{k}}, {p_{f}'})  (σ_{j}, I_{j}, {p_{f}}) ∈ T_{1}, p_{f} ∈ F_{1}, p_{k} ∈ F_{2}}  
∪  {(σ_{j}, I_{j} + {p_{k}}, {p_{f}'})  (σ_{j}, I_{j}, {p_{f}}) ∈ T_{2}, p_{f} ∈ F_{2}, p_{k} ∈ F_{1}} 
The last two types of transitions added to T' by T_{SF} remove the tokens from final places in C_{1} and C_{2} and place them in a new final place when the last transition of the composition is fired. This construction is demonstrated in Figure 11.
Figure 11. A Petri net whose CSS is the concurrent composition of the CSS of the Petri nets of Figure 7.
The construction is correct only for εfree CSS. However, if L_{1} = {ε} ∪ L_{1}+ with ε ∉ L_{1}+, then L_{1} Δ L_{2} = L_{2} ∪ (L_{1}+ Δ L_{2}). Thus, since CSS are closed under union, CSS are closed under concurrent composition.
The closure properties of CSS under many other operations can be investigated, but for our purposes the above four are most relevant. It is easily shown that CSS are also closed under reversal, εfree homomorphism, and εfree regular substitution [17]. Hack has shown that CSS are closed under εfree homomorphism, εfree Finite State Transducer mappings, and inverse homomorphisms. He has also shown that CSS are not closed under Kleene star or general substitution [7].
It is conjectured that CSS are not closed under complement.
Hopcroft and Ullman [10] have compiled a table of closure properties of regular, contextfree, contextsensitive, and type0 languages for several closure operations. A similar study for CSS as a class of languages might shed some further light on the character of the CSS languages and indirectly, on their relationship to these other classes of languages. Knowledge of the relationship between CSS languages and these other classes of languages might be useful for establishing decidability results for CSS from the known results for these languages.
Thus, we turn now to investigating the relationship between CSS and the classes of regular, contextfree, and contextsensitive 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 can be characterized by regular expressions. Problems of equivalence or inclusion between two regular languages are decidable and algorithms exist for their solution [10]. With such a desirable set of properties it is encouraging that we have the following theorem.
Theorem 6. Every regular language is CSS.
The proof of this theorem is based on the fact that every regular
language is generated by some finite state machine. A finite
state machine is defined as a 5tuple, (Q, δ, Σ, S,
F), where Q is a finite state space, δ a nextstate
function from Q × Σ into Q, Σ an alphabet, S
∈ Q a start state, and F ⊆ Q a set of
final states. We can construct an equivalent Petri net as
(Q, T, Σ, S, F), where the set of transitions is
T  =  {(σ_{i}, {q_{j}}, {q_{k}})  δ(q_{j},σ_{i}) = q_{k}} 
This Petri net will generate the same language as the finite state machine. Thus, every regular language is CSS.
The converse to Theorem 6 is not true. Figure 7 displays a Petri net which generates the contextfree language {a^{n}cb^{n}  n ≥ 1}. Since this language is not regular, we know that not all CSS are regular. Figure 12 shows that not all CSS are contextfree by exhibiting a CSS which is contextsensitive, but not contextfree.
Figure 12. A contextsensitive, but not contextfree CSS.
Theorem 7. There exist contextfree languages which are not CSS.
Assume there exists an nplace, mtransition Petri net which
generates {ww^{R}  w ∈ Σ*}. Let k be the number of
symbols in Σ, k > 1. For an input string xx^{R}, let l =  x ,
the length of x. Since there are k^{l} possible input strings x,
the Petri net must have k^{l} distinct reachable states after l
transitions in order to remember the complete string x. If we do
not have this many states, then for some strings x_{1} and x_{2}, we
have δ(S, x_{1}) = δ(S, x_{2}) for x_{1} ≠ x_{2}. Then,
δ(S, x_{1}x_{2}^{R})  =  δ(δ(S, x_{1}), x_{2}^{R}) 
=  δ(δ(S, x_{2}), x_{2}^{R})  
=  δ(S, x_{2}x_{2}^{R})  
=  ∈ F 
and the Petri net will incorrectly generate x_{1}x_{2}^{R},
For each transition t_{j}, there exists a vector v_{j} such that if δ(q, t_{j}) is defined then δ(q, t_{j}) = q + v_{j}. Thus after l inputs, a Petri net will be in a state q given by
for a sequence of transitions t_{j1}, t_{j2}, ... t_{jl}. Another way of expressing the above sum is
where a_{j} is the number of times transition t_{j} occurs in the sequence. We have also the constraint that
At best the vectors v_{1},v_{2}, ..., v_{m} will be linearly independent and each vector of coefficients (a_{1}, a_{2}, ..., a_{m}) will represent a unique state q. Since the sum of the coefficients is l, the vector of coefficients is a partition of the integer l into m parts. Knuth [13] gives the number of partitions of an integer l into m parts as
Now since
there are strictly less than (l + m)^{m} reachable states in Q after l inputs. For large enough l, we have then that
Having shown that not all contextfree languages are CSS and not all CSS are contextfree, the question arises, What is the class of languages which are both contextfree and CSS? 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 classes of languages is regular languages. Another subset is the set of bounded contextfree languages [4].
A contextfree language, L, is a bounded contextfree language
over an alphabet Σ, if there exist strings w_{1}, w_{2}, ..., w_{m} from
Σ* such that
L  ⊆  q_{1}*w_{2}* ... w_{m}*. 
Ginsburg [4] has developed a detailed examination of the properties of bounded contextfree languages and gives the following characterization theorem ([4, Theorem 5.4.1]).
Theorem 8. The family of bounded contextfree languages is the smallest family of sets defined by
We have already shown that every regular language (and hence every finite subset of Σ*) is CSS. We have also shown that CSS are closed under union and concatenation. Thus we have only to show that CSS are closed under the operation described in (3) above to show that bounded contextfree languages are CSS,
For any case where x, y, or W is ε, x_{i}Wy_{i} reduces to a language
of the form x*W, Wy*, x*, x^{i}y^{i}, or W which are CSS, for x, y
∈ Σ* and W CSS. For nonnull x and y, we define C_{x}
and C_{y} by
x = x_{1}x_{2}...x_{k}, x_{i} ∈ Σ  y = y_{1}y_{2}...y_{l}, y_{i} ∈ Σ 
C_{x} = (P_{x} , T_{x} , Σ, S_{x}, F_{x}),  C_{y} = (P_{y} , T_{y} , Σ, S_{y}, F_{y}), 
P_{x} = {p_{x1},p_{x2},...,P_{xk+1}},  P_{y} = {p_{y1},p_{y2},...,P_{yl+1}}, 
T_{x} = {x_{i},{p_{xi}}, {p_{xi+1}}  1 ≤ i ≤ k},  T_{y} = {y_{i},{p_{yi}}, {p_{yi+1}}  1 ≤ i ≤ l}, 
S_{x} = p_{x1},  S_{y} = p_{y1}, 
F_{x} = {p_{xk+1}},  F_{y} = {p_{yl+1}}, 
With these definitions, L(C_{x}) = {x} and L(C_{y}) = {y}. Let C_{w} =
(P_{w}, T_{w}, Σ, S_{w}, F_{w}) be a Petri net in standard form with
L(C_{w}) = W; then we define C' = (P', T', Σ, S', F') by
P'  =  P_{x} ∪ P_{y} ∪ P_{w} ∪ {p}, 
T'  =  T_{x} ∪ T_{y} ∪ T_{w} ∪ T_{xx} ∪ T_{xW} ∪ T_{Wy} ∪ T_{yy}, 
S'  =  S_{x}, 
F'  =  F_{y}, 
where
T_{xx}  =  {(x_{k}, {p_{xk}}, {p,p_{x1}})}, 
T_{xW}  =  {(σ(t_{j}), {p_{x1}}, O(t_{j}))  t_{j} ∈ T_{W} and I(t_{j}) = S_{W}}, 
T_{Wy}  =  {(σ(t_{j}), I(t), {p_{yl+1}})  t_{j} ∈ T_{W} and O(t_{j}) ∈ F_{W}}, 
T_{yy}  =  {(y_{1}, {p,p_{yl+1}}, {p_{y2}})}, 
The place p acts as a counter of the number of times that x has been generated and assures that y will be generated the same number of times if the string is correct. The additional transitions allow the proper sequencing of the C_{x}, C_{w}, and C_{y} nets.
With this construction, all bounded contextfree languages are shown to be CSS. Are there contextfree languages which are also CSS but not bounded? Unfortunately, yes. Ginsburg shows that the regular expression (a + b)* is not bounded contextfree. Since this language is both contextfree and CSS, we see that bounded contextfree languages are a proper subset of the family of languages which are both CSS and contextfree. (a + b)*ca^{n}b^{n} is both contextfree and CSS but neither regular nor bounded.
We turn now to contextsensitive languages. From the example in Figure 12 we know that some CSS are contextsensitive; below we prove that all CSS are contextsensitive. Since we know that all contextfree languages are also contextsensitive and there exist contextfree languages which are not CSS, there exist contextsensitive languages which are not CSS. Thus the inclusion is proper.
Theorem 9. All CSS are contextsensitive.
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 recognizes it. We use the latter technique for the proof given here. A proof using a contextsensitive grammar is given in [17].
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 the linear bounded automaton to recognize 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 automaton used to recognize contextfree languages (since the maximum length of the stack is bounded by a linear function of the input string length) except that the linear bounded automaton has random access (in the same sense as a Turing machine) to its memory, while the pushdown automaton has access to only one end of its memory.
To recognize a CSS with a linear bounded automaton, we simulate the Petri net by remembering, after each input, the number of tokens in each place. How fast can the number of tokens in a Petri net grow, as a function of the length of the input? After the transition sequence t_{t1} ,t_{t2} ,..., t_{tl} we have seen that the Petri net is in a state defined by
where v_{j} is the vector describing the change in state caused by
firing transition t_{j}. Since the v_{j} are fixed by the structure
of the Petri net, there is a maximum vector v which is
(componentwise) greater than all v_{j} (1 ≤ j ≤ m). Thus
q  <  S + l ⋅ v. 
If , then the number of tokens, η, in a Petri
net after l transitions is bounded by
η  <  1 + l ⋅  v  
Thus the number of tokens, and the amount of memory needed to remember them, is bounded by a linear function of the input length. Hence CSS can be recognized by linear bounded automata, showing that CSS are contextsensitive.
Figure 13. Relationship of CSS to other classes of languages.
Figure 13 summarizes the relationships among the classes of languages which are regular, bounded contextfree, CSS, contextfree, and contextsensitive. An arc between two classes of languages indicates proper containment.
A large number of problems for CSS and Petri nets are currently unanswered. The decidability of the following list of decision problems (among others) needs resolution.
The last problem above is the emptiness problem for CSS. This problem is central to the decidability properties of CSS languages. If the emptiness problem is undecidable, then all of the above questions are undecidable [17].
Another viewpoint on the emptiness problem for CSS can be obtained by considering the equivalence between the state space of the Petri net and vector replacement systems. Keller [12] has defined a vector replacement system as a triple (q_{0}, U, V), where U and V are sets of nvectors over the integers, with u_{j} < v_{j} for u_{j} ∈ U and v_{j} ∈ V (1 ≤ j ≤ U = V). A reachability set, Q, is defined by
(a) q_{0} ∈ Q.
(b) if x ∈ Q and x + u_{j} > 0,
then x + v_{j} ∈ Q (u_{j} ∈ U, v_{j} ∈ V).
Comparing this with the definition of the state space of a Petri net (Section 2.3), we see that the emptiness problem for CSS is similar to the reachability problem for vector replacement systems: Given a vector replacement system with reachability set Q and an arbitrary vector x, is x ∈ Q? This reachability problem is equivalent to the reachability problem for vector addition systems [11, 14].
A short proof along the lines of Nash's proof of the equivalence of the (general) reachability to the zero reachability problem [11] shows that the emptiness problem for CSS is equivalent to the reachability problem for vector replacement and addition systems. The decidability of these questions is an open problem.
The use of concepts from formal language theory in the investigation of Petri nets is still a new field of research. Some preliminary investigations along this line have been made by other researchers. Baker [1] considered briefly the prefix languages of Petri nets defined by the set of legal (but not necessarily complete) computation sequences. This has been developed further by Hack [7], who considers the properties of four related classes of languages which can be defined for Petri nets. These languages result from considering either prefix or finalstate languages either with or without null labels (σ(t_{j}) = ε).
Another interesting connection between formal language theory and Petri nets has been considered by CrespiReghizzi and Mandrioli [3]. Their work points out the relationship between Petri net languages and the matrix contextfree languages. Petri net languages can also be related to the Szilard languages [20] for matrix contextfree languages.
Although some of the fundamental properties of CSS have been established, many questions concerning CSS are still unanswered. We feel that CSS, and other classes of languages which can be associated with Petri nets, are an important new type of formal languages. CSS provide a useful bridge between formal language theory and research in the area of parallel computation using Petri nets, and, we believe, add significant new concepts to both existing theories.
The theory of bags (also called multisets) has been developed by Cerf et al. [2]. Bags are an extension of the concept of sets. A bag, like a set, is a collection of elements from some domain. Unlike a set, however, an element may occur in a bag more than once. A function, #(⋅,⋅), is defined on elements of a domain and bags over that domain which yields the number of occurrences of the element in the bag. That is,
#(x, β) = k ≥ 0 if there are exactly k occurrences of the element x in the bag β.
Since the theory of sets is included in the theory of bags (for the special case when the range of the # function is {0, 1}), we adopt most of the notation and many of the basic concepts of sets for our work with bags. Figure A lists some of the concepts of bags, gives the notation we use, and the formal definition in terms of the # function.
Concept  Notation  Definition 

Empty bag  ∅  ∀x [#(x,∅) = 0] 
Membership  x ∈ B  #(x, B) > 0 
Size of bag   B   B = Σ_{x} #(x,B) 
Bag equality  A = B  ∀x [#(x,A) = #(x,B)] 
Bag inclusion  A ⊆ B  ∀x [#(x,A) ≤ #(x,B)] 
Strict bag inclusion  A ⊂ B  A ⊆ B and A ≠ B 
Bag union  A ∪ B  ∀x [#(x,A ∪ B) = max(#(x,A), #(x,B))] 
Bag intersection  A ∩ B  ∀x [#(x,A ∩ B) = min(#(x,A), #(x,B))] 
Bag sum  A + B  ∀x [#(x,A + B) = #(x,A) + #(x,B)] 
Bag difference  A  B  ∀x [#(x,A  B) = #(x,A) #(x,A ∩ B)] 
The set of all bags over a domain D  D^{ ∞ }  ∀B ∈ D^{∞}, ∀x ∈ B [x ∈ D] 
Limited repetition over a domain D  D^{n}  D^{n} ⊆ D^{∞}, ∀B ∈ D^{n}, ∀x ∈ D [#(x,B) ≤ n] 
For bags over a finite domain, D = {d_{1}, d_{2}, ..., d_{n}}, a natural correspondence exists between a bag β ∈ D^{∞} and the nvector Ψ(β) over the nonnegative integers defined by
This is known as the Parikh mapping [15] of the bag.
I gratefully acknowledge the help of Professor T, H. Bredt and the careful, helpful, and encouraging remarks of M. Hack in the preparation of this paper. Mr. Hack's review and comments have helped to correct some early errors in the paper,
Home  Comments? 