Petri Net Transformations

1. Introduction

Modelling the adaption of a system to a changing environment gets more and more important. Application areas cover e.g. computer supported cooperative work, multi agent systems, dynamic process mining or mobile networks. One approach to combine formal modelling of dynamic systems and controlled model adaption are Petri net transformations. The main idea behind net transformation is the stepwise development of place/transition nets by given rules. Think of these rules as replacement systems where the left-hand side is replaced by the right-hand side while preserving a context. This approach increases the expressiveness of Petri nets and allows in addition to the well known token game a formal description of structural changes.

The chapter is structured as follows: We start with a general overview of net transformations [25, 30, 7, 10] in Section 2. In Section 3, we illustrate the rule-based refinement of place/transition nets in terms of a case study in the area of an emergency scenario [4]. The case study shows how to use Petri net transformations as refinement concept and demonstrates the compatibility of net refinement and net composition which indicate the relevance of Petri net transformations for software engineering. In Section 4, we present precise definitions of basic notions concerning Petri net transformations in the case of place/transition nets. The union theorem shows the compatibility of net transformations with the union of nets via a common interface provided that the net transformations are preserving this interface. Furthermore, results for high-level nets are also briefly discussed at the end of Section 4. In the conclusion we discuss how tools for graph transformation systems can also be used for Petri net transformations.

2. General overview of net transformations

The main idea of net transformations is the rule-based modification of nets where each application of a rule leads to a net transformation step. While the well-known token game of Petri nets does not change the net structure, the concept of Petri net transformations is a rule-based approach for dynamic changes of the net structure of Petri nets. Since Petri nets can be considered as bipartite graphs the concept of graph transformations can be applied to define transformations of Petri nets. In the following we give a general overview of graph and net transformations, for more details see [30, 8, 12, 7, 14].

The research area of graph transformation is a discipline of computer science which dates back to the early seventies. Methods, techniques, and results from the area of graph transformation have already been studied and applied in many fields of computer science such as formal language theory, pattern recognition and generation, compiler construction, software engineering, concurrent and distributed systems modelling, database design and theory, logical and functional programming, AI, visual modelling, etc. Graph transformation has at least three different roots, namely from Chomsky grammars on strings to graph grammars, from term rewriting to graph rewriting, and from textual description to visual modelling.

Computing by graph transformation is a fundamental concept for programming, specification, concurrency, distribution, and visual modelling. A state of the art report for applications, languages and tools for graph transformation on the one hand and for concurrency, parallelism and distribution on the other hand is given in volumes 2 and 3 of the Handbook of Graph Grammars and Computing by Graph Transformation [8] and [12]. In our paper [14], we have presented a comprehensive presentation of graph and net transformations and their relation. Petri net transformations can also be realized for algebraic high-level nets [25], which is a high-level net concept integrating algebraic specifications with place/transition nets.

In contrast to most applications of the graph transformation approach, where graphs denote states of a system, and rules and transformations describe state changes and the dynamic behavior of systems, in the area of Petri nets we use rules and hence transformations to represent stepwise modification of nets. This kind of transformation for Petri nets is considered to be a vertical structuring technique, known as rule-based net transformation. Basically, a rule (or production) r = (L, R) is a pair of graphs (or nets) called left-hand side L and right-hand side R. Applying the rule r = (L, R) means to find a match of L in the source graph (or net) and to replace L by R. In order to replace L by R we need to connect R with the context leading to the target graph (respectively the target net) of the transformation.

The well-known argument in favour of formal techniques, to have precise notions and rigid mathematical results, clearly holds for this approach as well. Moreover, we have already investigated net transformations in high-level Petri net classes (see Subsection 4.6) that are even more suitable for system modelling than the place/transition nets in our case study. The impact for system development is founded in what results from net transformations:

• Stepwise Development of Models: The model of a complex software system may reach a size that is difficult to handle and may compromise the advantages of the (formal) model severely. The one main counter measure is breaking down the model into sub-models, the other is to develop the model top-down. In top-down development the first model is a very abstract view of the system and step by step more modelling details and functionality are added. In general, however, this results in a chain of models that are strongly related by their intuitive meaning, but not on a formal basis. Petri net transformations fill this gap by supporting the formal step-by-step development of a model. Rules describe the required changes of a model and their applications yield the transformations of the model. Moreover, the representation of changes in a visual way using rules and transformations is very intuitive and does not require a deeper knowledge of the theory.

• Distributed Development of Models: Decomposing a large model is an important technique for the development of complex models. To combine the advantages of a horizontal structuring with the advantages of step-by-step development, vertical structuring techniques for ensuring the consistency of the composed model are required. Then a distributed step-by-step development is available that allows the independent development of submodels. The theory of net transformation comprises horizontal structuring techniques and ensures compatibility between these and the transformations. In Subsection 4.4 we introduce the union construction for the decomposition, and the union theorem in Subsection 4.5 allows to develop the subnets independently of each other. The theory allows complex compositions and decompositions, where the independence of the sub-models is essential. So, the formal foundation for the distributed development of complex models is given.

• Incremental Verification: Pure modification of Petri nets is often not sufficient, since the net has some desired properties that have to be ensured during further development. Verification of each intermediate model requires a lot of effort and hence is cost intensive. But refinement can be considered as the modification of nets preserving desired properties. Hence the verification of properties is only required for the net where they can be first expressed. In this way properties are introduced into the development process and are preserved from then on. Rule-based refinement modifies Petri nets using rules and transformations so that specific system properties are preserved. For a brief discussion see Subsection 4.6.

• Foundation for Tool Support: A further advantage is the formal foundation of rule-based refinement and/or rule-based modification for the implementation of tool support. Due to the theory of Petri net transformations we have a precise description how rules and transformations work on Petri nets. Tool support is the main precondition for the practical use. The user should get tool support for defining and applying rules. The tool should assist the choice as well as the execution of rules and transformations.

• Variations of the Development Process: Another application area, where transformations are very useful, concerns variations in the development process. Often a development is not entirely unique, but variations of the same development process lead to variations in the desired models and resulting systems. These variations can be expressed by different rules yielding different transformations, that are used during the step-by-step development.

3. Emergency scenario case study

In this section we illustrate the main idea of net transformations by a case study of a pipeline emergency scenario where an unknown source of a natural gas leak is detected in a residential area

www.pipelineemergencies.com

: A postal worker delivering mail in a residential street smells a strong odor of gas. She immediately notifies the fire department. A single engine company is dispatched by the fire department with four firefighters led by one company officer. At the scene, the postal worker meets the company officer and describes the problem. He calls the gas company and requests additional law enforcement officers to control traffic into the area. While three firefighters evacuate the homes in the immediate area and afterwards deny entry to this area, the forth one reads the gas indicator and detects that the gas is highest in front of a home located on 114 Maple Street. After electricity and gas lines are shut off to each home the fire department people stand by with fully charged hose lines and wait for the arrival of the gas company. The cooperative process enacted by the firefighter company is depicted as Petri net PN1 in Fig. 1. This Petri net is decomposed into five parts corresponding to the team members described above, and in addition start as well as end activities. The union describes the gluing of the subnets along the interface given by the post domain places of transition Start (respectively pre domain places of transition End).

In this case the interface net consists of places only, so that the union corresponds to the usual place fusion of nets. But the general union construction allows having arbitrary subnets as interfaces.

In the following we show how Petri net transformations can be used in the case study before we present the basic concepts in Section 4. The three firefighters responsible for the evacuation process need more detailed information how to proceed. So the company officer gives the instruction that first of all the residents shall be notified of the evacuation. Afterwards the firefighters shall assist handicapped persons and guide all of them to the extent possible. To introduce the refinement of the Evacuate homes-transition into the Petri net PN1 we provide the rule r _evacuate depicted in the upper row of Fig. 2.

Figure 1.

Petri Net PN1.

We show explicitly the direct transformation with rule revacuate from Firefighters 1-3 (see Fig. 1) to Firefighters 1-3' in Fig. 2. The application of the rule is given as follows: the match morphism m is given by the obvious inclusion and identifies the relevant parts of the left hand side L1 of rule r _evacuate in Firefighter 1-3. In the first step we delete from Firefighter 1-3 the Evacuate homes-transition and adjacent edges, but we preserve all places of L1, because they are also in K1 and R1, leading to the context net C in Fig. 2. In the second step we glue together C and R1 via K1 by adding the transitions Notify residents, Assist handicapped persons and Guide persons together with their (new) environment to the context net C leading to Firefighters 1-3' in Fig. 2. Thus we obtain the direct transformation Firefighters 1-3 $$\stackrel{r_{evacuate}}{\Rightarrow }$$ Firefighters 1-3'.

Since the rule r _evacuate and the direct transformation are preserving the interface of the corresponding union in Fig. 1, the interfaces are still available and can be used to construct a resulting net. The union theorem in Section 4 makes sure that this construction leads to the same result as if we would have applied the rule revacuate to the entire net PN1 in Fig. 1. This is a typical example for compatibility of horizontal structuring (union) with vertical refinement (rule-based transformation).

After the problem identification the odor of gas grows stronger and the firefighter takes an additional reading of the gas indicator and informs the company officer about the result, so that the company officer is able to determine if the atmosphere in the area is safe, unsafe, or dangerous. To extend our process by these additional activities we use the rule r _analyse in Fig. 3.

Figure 2.

Direct transformation Firefighters 1-3 $$\stackrel{r_{evacuate}}{\Rightarrow }$$ Firefighters 1-3'.

Figure 3.

Rule r _analyse.

Figure 4.

Rule r _expand.

Based on the additional results of the gas indicator the company officer analyses that the atmosphere in this area is over the lower explosive limit and thereby more dangerous than expected. He determines that the best course of action is to call for additional resources to maintain the isolation perimeter and expand the area of evacuation as a precaution. Here, we use rule r _expand depicted in Fig. 4 to extend the Petri net by the additional activities.

Summarizing, after the sequential application of the rules r _evacuate , r _analyse and r _expand to the Petri net PN1 in Fig. 1. we obtain the Petri net PN4 in Fig. 5.

4. Concepts of Petri net transformations

Following up the informal overview in Section 2 we give in this section the precise definitions of the notions that we have already used in our case study. For notions and results beyond that we give a brief survey in Subsection 4.6 and refer to literature.

The concept of Petri net transformations [30, 8, 12, 7, 14] is a special case of high-level replacement systems. High-level replacement systems have been introduced in [9] as a categorical generalisation of the double-pushout approach to graph transformation, short DPO-approach. The theory of high-level replacement systems can be successfully employed not only to graph transformation, but also to other areas as Petri nets (see [9]). This leads to the concept of Petri net transformations as an instantiation of high-level replacements systems. In the following we explicitly present the resulting concepts of Petri net transformations for the case of place/transition nets.

Figure 5.

Petri net PN4.

4.1. Place/transition nets and net morphisms

Let us first present a notation of place/transition net that is suitable for our transformation approach. We assume that the nets are given in the algebraic style as introduced in [21]. A place/transition net N = (P, T, pre, post) is given by the set of places P, the set of transitions T, and two mappings pre,post : $T\to P^{\oplus }$ , the pre-domain and the post-domain,

$$\begin{array}{cc}T& \begin{array}{l}\stackrel{pre}{\to }\\ \underset{post}{\to }\end{array}\end{array}{P}^{\oplus }$$ E1

where $P^{\oplus }$ is the free commutative monoid over P that can also be considered as the set of finite multisets over P. The pre- (and post-) domain function maps each transition into the free commutative monoid over the set of places, representing the places and the arc weight of the arcs in the pre-domain (respectively in the post-domain). For finite P, an element $w\in P^{\oplus }$ can be presented as a linear sum $w={\displaystyle {\sum }_{p\in P}{\lambda }_p\cdot p}$ with ${\lambda }_p\in \text{N}$ or as a function w : P → N. In the infinite case we have to require that ${\lambda }_p\ne 0$ only for finitely many $p\in P$ that means the corresponding w : P → N has finite support.

In the net L3 in Fig. 4, T consists of one transition t and P of four places, where p₁,p₂,p₃ are shown above and p₄ below of t. The function pre : $T\to P^{\oplus }$ and post : $T\to P^{\oplus }$ are defined by $pre(t)=p_1\oplus p_2\oplus p_3\text{and}post(t)=p_4$ , respectively.

Based on the algebraic notion of Petri nets we use simple homomorphisms that are generated over the set of places. These morphisms map places to places and transitions to transitions. A morphism ƒ : N₁ → N₂ between two place/transition nets N₁= (P1,T1,pre1,post1) and N₂ = (P₂,T₂, pre₂, post₂) is given by ƒ = (ƒ_p, ƒ_t) with mappings ƒ_p : P1 → P₂ and ƒ_t : T1 → T₂ that pre₂ ○ $f_T=f_P\oplus$ ○ pre1 and post₂ ○ $f_T=f_P\oplus$ ○ post₁ . These conditions ensure that the pre-domain as well as the post-domain of a transition are preserved, so that, even if places may be identified, the number of tokens that are taken remains the same. Note that the extension $f_P\oplus :P_1\oplus \to P_2\oplus$ : of ƒ_p : p₁→P2 is defined by $f_P^{\oplus }\left({\Sigma }_{p\in P_1}{\lambda }_p\cdot p\right)={\Sigma }_{p\in P_1}{\lambda }_p\cdot f_P(p)$ . The morphism ƒ = (ƒ_p, ƒ_t) is called injective, if ƒ_p and ƒ_t are injective. The diagram schema for net morphisms is given in the following diagram.

$$\begin{array}{ccc}{T}_1& \begin{array}{l}\stackrel{pr{e}_1}{\to }\\ \underset{pos{t}_1}{\to }\end{array}& P_1^{\oplus }\\ f_T\downarrow & & \downarrow f_p^{\oplus }\\ T_2& \begin{array}{l}\stackrel{pr{e}_2}{\to }\\ \underset{pos{t}_2}{\to }\end{array}& P_2^{\oplus }\end{array}$$ E2

Several examples of net morphisms can be found in Fig. 2 where the horizontal and vertical arrows denote injective net morphisms.

4.2. Rules and transformations

The formal definition of rules and transformations is based on concepts of the following category PT. The category PT consists of place/transition nets as objects and place/transition net morphisms as morphisms. In order to formalise rules and transformations for nets we first state the construction of pushouts in the category PT of place/transition nets. For any span of morphisms N₁ ← N₀ → N₂ the pushout can be constructed and means intuitively the gluing of nets N₁ and N₂ along N₀ . The construction is based on the pushouts for the sets of transitions and places in the category Set. In the category Set of sets and functions the pushout object D is given by the quotient set D = B + C/ ≡, short D = B + _a C, where B + C is the disjoint union of B and C and ≡ is the equivalence relation generated by ƒ (a) ≡ g(a) for all $a\in A$ . In fact, D can be interpreted as the gluing of B and C along A: Starting with the disjoint union B + C we glue together the elements $f(a)\in B$ and $g(a)\in C$ for each $a\in A$ . Given the morphisms ƒ : N₀ → N₁ and g : N₀ → N₂ then the pushout N₃ in the category PT with the morphisms ƒ ′ : N₂ → N₃ and g′ : N₁ → N₃ is constructed (see diagram below) as follows:

$$\begin{array}{l}•T_3=T_1+T_0{T}_2\text{with}{f}_T^{\prime }\text{and}{g}_T^{}\text{as}\text{pushout}\text{of}{f}_T\text{and}{g}_T\text{in}Set.\\ •P_3=P_1+P_0{P}_2\text{with}{f}_P^{}\text{and}{g}_P^{}\text{as}\text{pushout}\text{of}{f}_P\text{and}{g}_P\text{in}Set\text{as}\text{well}.\\ •pr{e}_3(t)=\{\begin{array}{c}\left[pr{e}_1(t_1)\right];if{g}_T^{}(t_1)=t\\ \left[pr{e}_2(t_2)\right]if{f}_T^{}(t_2)=t\end{array}\\ •pos{t}_3(t)=\{\begin{array}{c}\left[pos{t}_1(t_1)\right]if{g}_T^{\prime }(t_1)=t\\ \left[pos{t}_2(t_2)\right];if{f}_T^{}(t_2)=t\end{array}\end{array}$$ E3

$$\begin{array}{ccc}{N}_0& \stackrel{f}{\to }& N_1\\ g\downarrow & (=)& \downarrow g\prime \\ N_2& \underset{f\text{'}}{\to }& N_3\end{array}$$ E4

Two examples of the pushout construction of nets are depicted in Fig. 2. We have the embedding of K1 into L1 and C. The pushout describes the gluing of the nets L1 and C along the two places of the interface K1. Hence we have the pushout L1 + _k1 C =Firefighters 1-3 on the left hand side of Fig. 2. Similarly, we have the pushout R1 + _k1 C =Firefighters 1-3' on the right hand side of Fig. 2.

Since rule application always involves the construction of two pushouts, we speak of the double-pushout (DPO) approach to graph and net transformation, where transformation rules describe the replacement of the left-hand side net by the right-hand side net in the presence of an interface net.

1. A rule $r=\left(L\stackrel{k_1}{\leftarrow }K\stackrel{k_2}{\to }R\right)$ consists of place/transition nets L, K and R, called left-hand side, interface and right-hand side net respectively, and two injective net morphisms $K\stackrel{k_1}{\to }L\text{and}K\stackrel{k_2}{\to }R$ .

2. Given a rule $r=\left(L\stackrel{k_1}{\leftarrow }K\stackrel{k_2}{\to }R\right)$ , a direct transformation $N_1\stackrel{r}{\Rightarrow }{N}_2$ from N₁ to N₂ is given by two pushout diagrams (1) and (2) in the following diagram. The morphisms m : L → N₁ and n : R → N₂ are called match and comatch, respectively. The net C is called pushout complement or the context net.

$$\begin{array}{ccccc}L& \stackrel{k_1}{\leftarrow }& K& \stackrel{k_2}{\to }& R\\ m\downarrow & (1)& \begin{array}{c}|\\ c\\ \downarrow \end{array}& (2)& \downarrow n\\ N_1& \stackrel{}{\leftarrow }& C& \stackrel{}{\to }& N_2\end{array}$$ E5

The illustration of a transformation can be found for our case study in Fig. 2, where the rule r_evacuate is applied to the net Firefighters 1-3 with match m. As explained above, the first pushout denotes the gluing of the nets L1 and C along the net Kl resulting in the net Firefighters 1-3. The second pushout denotes the gluing of the nets R1 and C along the net Kl resulting in the net Firefighters 1-3'.

4.3. Gluing condition and context nets

Given a rule r and a match m as depicted in the diagram above, then we construct in the first step the pushout complement C provided that a suitable gluing condition holds. This leads to the pushout (1) in the diagram above. In the second step we construct the pushout of c and k2 leading to N2 and the pushout (2) in the diagram above.

Intuitively the gluing condition makes sure that we can construct a context net C, also called pushout complement, from rule r and match m such that the gluing C + _k L of C and L along K is equal to the net N1. Formally we have to require that dangling points and identification points are gluing points in the following sense:

Gluing Condition for Nets: $DP\cup IP\subseteq GP$ , where the gluing points GP, dangling points DP and the identification points IP of L are defined by

$$\begin{array}{l}•GP=k_1\left(P_K\cup T_K\right),\\ •DP=\left\{p\in P_L|\exists t\in \left(T_1\backslash m_T\left(T_L\right)\right):m_p\left(p\right)\in pr{e}_1\left(t\right)\oplus pos{t}_1\left(t\right)\right\},\text{and}\\ •IP=\left\{p\in P_L|\exists p\prime \in P_L:p\ne p\prime \wedge m_P\left(p\right)=m_P\left(p\prime \right)\right\}\\ \cup \left\{t\in T_L|\exists t\prime \in T_L:t\ne t\prime \wedge m_T\left(t\right)=m_T\left(t\prime \right)\right\}\end{array}$$ E6

Now the pushout complement C is constructed by:

$$\begin{array}{l}•P_C=\left(P_1\backslash m_P\left(P_L\right)\right)\cup m_P\left(k_{1P}\left(P_K\right)\right)\\ •T_C=\left(T_1\backslash m_T\left(T_L\right)\right)\cup m_T\left(k_{1T}\left(T_K\right)\right)\\ •pr{e}_C=pr{e}_{1|T_C}\text{and}pos{t}_C=pos{t}_{1|T_C}\end{array}$$ E7

Note that the pushout complement C leads to the pushout (1) in the diagram above and that it is unique up to isomorphism.

In our case study in Section 3, the gluing condition is satisfied in the direct transformation in Fig. 2 since the match is injective and places are not deleted by the rule r_evacuate . In fact, the dangling points DP of the match in Fig. 2 are given by one place of L1, while the gluing points GP consists of all places in L1. The set of identification points IP is empty, because the match is injective, hence we have $DP\cup IP\subseteq GP$ .

4.4. Union construction

The union of two Petri nets sharing a common subnet, that may be empty, is defined by the pushout construction for nets. The union of place/transition nets N1, N2 sharing an interface net I with the net morphisms ƒ : I → N1 and g : I → N2 is given by the pushout diagram (1) below. Subsequently we use the short notation N = N1 +I N2 or N1; N2> $\stackrel{I}{\Rightarrow }$ N.

$$\begin{array}{ccc}I& \stackrel{f}{\to }& N_1\\ g\downarrow & (1)& \downarrow g\prime \\ N_2& \underset{f\prime }{\to }& N\end{array}$$ E8

In our example in Fig. 1 we can use the union construction several times to describe the net PN1 as the composition of five different subnets given by Firefighters 1-3, Officer, Firefighter 4, Start and End. The interface nets I are given by the intersection of the corresponding nets.

4.5. Union theorem

The Union Theorem states the compatibility of union and net transformations in the following sense: A union of two nets followed of a parallel transformation of the united nets yields the same result as two transformations of the original two nets followed by a union of the two transformed nets.

Given a union N1 +I N2 = N and net transformations N1 $\stackrel{r_1}{\Rightarrow }$ M₁ and N2 $\stackrel{r_2}{\Rightarrow }$ M₂ then we have a parallel rule r₁+r₂ = (L₁+L₂ ← K₁+K₂ → R₁+R₂), where L₁ + L₂, K₁+ K₂ and R₁ + R₂ are disjoint unions of the respective nets of rules r₁ and r₂ , and a parallel net transformation N $\stackrel{r_1+r_2}{\Rightarrow }$ M. Then M = M₁ +I M₂ is the union of M₁ and M₂ with the shared interface I, provided that the given net transformations preserve the interface I. The Union Theorem is illustrated in the following diagram and especially stated and proven in [22]:

$$\begin{array}{ccc}{N}_1,N_2& \stackrel{I}{\Rightarrow }& N\\ r_1,r_2\Downarrow & (=)& \Downarrow r_1+r_2\\ M_1{M}_2& \stackrel{I}{\Rightarrow }& M\end{array}$$ E9

Note that the compatibility requires an independence condition stating that nothing from the interface net I may be deleted by one of the transformations of the subnets.

This allows in Section 3 to apply either the rules r1 = r_evacuate and r2 = r_analyse , respectively, to N1 =Firefighters 1-3 in Fig. 1 and N2 constructed as union in four steps of the nets Officer, Firefighter 4, Start and End, or in parallel to the union N = N1 +_IN2, where I consists of two places which are preserved by both transformations N1 $\stackrel{r_1}{\Rightarrow }$ M1 and N2 $\stackrel{r_2}{\Rightarrow }$ M₂ . This allows to obtain the same net M by union M = M₁ +_IM₂ and by transformation N $\stackrel{r_1+r_2}{\Rightarrow }$ M. Finally, applying rule r₃ = r_expand to M leads to the net PN4 in Fig. 5.

4.6. Further results

We briefly introduce the main net classes which have been studied up to now and subsequently present some main results.

• Place/transition nets in the algebraic style have already been introduced in Subsection 4.1. In [11, 17, 10] we have transferred these results to place/transition systems, where a place/transition system is a place/transition net with an initial marking.

• Coloured Petri nets [18, 19, 20] are high-level nets combining P/T nets and ML expressions for data type definitions. They are very popular due to the tool CPN-tools [5].

• Algebraic high-level nets are available in quite a few different notions e.g. [28, 25]. We use a notion that reflects the paradigm of abstract data types into signature and algebra. An algebraic high-level net (as in [25]) is given by N = (SPEC,P,T,pre,post,cond,A), where SPEC = (S,OP,E;X) is an algebraic specification in the sense of [13] with additional variables X not occurring in E, P is the set of places, T is the set of transitions, pre,post : $T\to {\left(T_{OP}\left(X\right)\times P\right)}^{\oplus }$ are the pre- and post-domain mappings, cond : T → P_fin(EQNS(SIG, X)) are the transition guards, and A is a SPEC algebra.

Horizontal Structuring Union and fusion are two categorical structuring constructions for place/transition nets that merge two subnets (fusion) or two different nets (union) into one.

The union has been introduced in the previous subsection. Now let us consider the fusion: Given a net F that occurs in two copies in the net N1, represented by two morphisms $\begin{array}{ccc}F& \begin{array}{l}\stackrel{f}{\to }\\ \underset{f\prime }{\to }\end{array}& N_1\end{array}$ , the fusion construction leads to a net where both occurrences of F in N₁ are merged. If F consists of places p1,...,pn then each of the places occurs twice in net N1, namely as ƒ(p1),..., ƒ(p_n), and ƒ′(p1),..., ƒ′(p_n). N₂ is obtained from the net N1 by fusing both occurrences ƒ(pi) and ƒ′(pi) of each place pi for 1 ≤ i ≤ n.

The Union Theorem has been presented in the previous subsection. The Fusion Theorem [23] is expressed similarly: Given a rule r and a fusion $\begin{array}{ccc}F& \begin{array}{l}\stackrel{}{\to }\\ \underset{}{\to }\end{array}& N_1\end{array}$ then we obtain the same result whether we derive first $$N_1\stackrel{r}{\Rightarrow }{N}_1^{\prime }$$ and then construct the fusion $\begin{array}{ccc}F& \begin{array}{l}\stackrel{}{\to }\\ \underset{}{\to }\end{array}& N_1^{\prime }\end{array}$ resulting in N₂ ' or whether we construct the fusion $\begin{array}{ccc}F& \begin{array}{l}\stackrel{}{\to }\\ \underset{}{\to }\end{array}& N_1\end{array}$ first, resulting in N₂ , and then perform the transformation step $$N_2\stackrel{r}{\Rightarrow }{N}_2^{\prime }$$ . Similar to the Union Theorem, a certain independence condition is required. Both theorems state that Petri net transformations are compatible with the corresponding structuring technique under suitable independence conditions. In short these conditions guarantee that the interface net I and respectively the fusion net F are preserved by all net transformations.

Interleaving and Parallelism We are able to realize model interleaving and parallelism of net transformations. The Local Church- Rosser Theorem states a local confluence in the sense of formal languages corresponding to interleaving. The required condition of parallel independence means that the matches of both rules overlap only in parts that are not deleted. Sequential independence means that those parts created or used by the first transformation step are not used or deleted in the second step, respectively. The Parallelism Theorem states that sequential or parallel independent transformations can be carried out either in arbitrary sequential order or in parallel. In the context of step-by-step development these theorems are important as they provide conditions for the independent development of different parts or views of the system. More details on horizontal structuring or parallelism are given in [25] and [23].

Refinement Rule-based refinement comprises the transformation of Petri nets using rules while preserving certain net properties. For Petri nets the desired properties of the net model can be expressed e.g in terms of Petri nets (as liveness, boundedness etc.), in terms of logic (e.g. temporal logic, logic of actions etc.), in terms of relation to other models (e.g. bisimulation, correctness etc.), and so on.

For place/transition nets, algebraic high-level nets and Coloured Petri nets the most important results for rule-based refinement are presented in Table 1. For more details see [27].

Table 1.

Achieved results.

5. Conclusion

The main idea of Petri net transformations is to extend the classical theory of Petri nets by a rule-based technique that allows to model the changes of the Petri net structure.

There have been already a few approaches to describe transformations of Petri nets formally (e.g. in [2, 3, 31, 6, 32]). The intention has been mainly on reduction of nets to support verification, and not on the software development process as in our case. This use of transformations has been one of the main focus areas of the DFG-Research group Petri Net Technology. There are some large studies in various application areas as medical information systems [15], train control systems [26], or as sketched in this paper in emergency scenarios. These case studies clearly show the advantages using net transformation in system development and the practical use of the results stated in Table 1. Although the area of Petri net transformations is already well-established, there are many promising directions for further research to follow, for example:

• Transfer to other net classes - There is a large variety of Petri net classes, and in principle the idea of Petri net transformation is applicable to all of them. The concept of transformation we have employed is an algebraic one, so the use of algebraic approaches to Petri nets is more suggesting. Algebraic higher-order nets [16] have been recently developed and are one of the promising targets to transfer the idea of transformations to. These nets extend algebraic high-level nets as they are equipped with a higher-order signature and algebra. This allows most interesting applications and supports structure flexibility and system adaptability in an extensive way.

• Reconfigurable place/transitions systems - In [17], the concept of reconfigurable place/transition (P/T) systems has been introduced that is most important to model changes of the net structure while the system is kept running. In detail, a reconfigurable P/T-system consists of a P/T-system and a set of rules, so that not only the follower marking can be computed but also the structure can be changed by rule application to obtain a new P/T-system that is more appropriate with respect to some requirements of the environment. Moreover these activities can be interleaved. In [11] we have continued our work by transferring the results of local Church-Rosser which are well known for term rewriting and graph and net transformations (see [30, 7, 10]) to the consecutive evolution of a P/T-system by token firing and rule applications. In more detail, we assume that a given P/T-system represents a certain system state. The next evolution step can be obtained not only by token firing, but also by the application of one of the rules available. Hence, we have presented conditions for (co-)parallel and sequential independence, such that each of these evolution steps can be postponed after the realization of the other, yielding the same result and, analogously, they can be performed in a different order without changing the result.

• Component technology - Components present an advanced paradigm for the structuring of complex systems and have been advocated in the recent years most strongly. Components that use Petri nets for the specification of the interfaces and the component body have been defined in [24]. There are three nets that represent the import, the export and the body of the component. The export is an abstraction of the body and the import is embedded into the body. There are two operations: the hierarchical composition and the union of components. Unfortunately, up to now there is no transformation concept in the sense of graph and net transformation. Based on net transformations the transformation of the import, the export and the body can be defined straightforward.

• Tool support - The practical use of graph transformation is supported by several tools. The algebraic approach to graph transformation is especially supported by the graph transformation environment AGG (see [1]). A tool for net transformations using the graph transformation engine AGG has been developed recently [29] as an Eclipse plug-in to support a special class of reconfigurable P/T-systems.