1. Introduction
In the field of systems engineering modeling plays a key role for understanding and controlling the behavior of the corresponding systems. Software systems are increasingly characterized by dynamic structures that require execution and reconfiguration at run-time to adjust the systems behavior to its changing environment. Their main feature results from their complex coordination behavior within dynamically adapting infrastructures. Such dynamic structures need a suitable formal description technique that allows the separation at different levels of dynamic behavior within one model.
Reconfigurable Petri nets provide dynamic changes at the process level, (as typical for Petri nets) and additionally at the structure level. They are based on the algebraic approach to Petri nets, with operations describing the pre- and post-domain of transitions and are equipped with rules for the transformation of the net. These rules allow the modification of the net’s structure at run time. Reconfigurable Petri nets have been applied in various application areas where complex coordination and structural adaptation at run-time is required (e.g. mobile ad- hoc networks [1] , communication spaces [2] [3] , ubiquitous computing [4] [5] , concurrent systems [6] , work- flows in a dynamic infrastructure [7] ). The distinction between the net behavior and the dynamic change of its net structure is the characteristic feature that makes reconfigurable Petri nets so suitable for systems with dynamic structures.
In Figure 1 a screenshot of the tool ReConNet (see [8] ) is given, depicting a decorated PT net N1 that can be modified using the rule
, replacing a left hand side L by a right hand side R. The net can initially fire only once. After applying the rule r, that reverses the arcs, the resulting net is then live. Subsequent transformation steps yield alternatingly a net that is live or one that has a deadlock.
Several case studies have shown the advantages of reconfigurable Petri nets. In [5] reconfigurable Petri nets based on decorated place/transition nets have been used to model and analyze scenarios in a smart home. The tenant’s behavior follows specific procedures that the smart home has to support. These procedures depend on the situation as well as the available sensor data and the tenant’s action. These procedures are captured informally as scenarios and have been modeled formally for the better understanding of the possible interaction of the smart home and its tenant. There the scenarios describe the tenant’s procedures and the transformations describe the dynamic change of the infrastructure as the reactions to the tenant’s actions that both can be adequately captured.
Algebraic High-Level (AHL) nets are Petri nets combined with algebraic specifications [9] leading to the concept of algebraic high-level nets with suitable composition results. A general modeling framework for communication platforms and scenarios has been presented in [3] [10] using reconfigurable AHL nets. This framework employs an integration of Petri nets, algebraic data types and net transformation techniques. It allows the analysis of the evolution of communication platforms, the analysis of scenario evolutions and the investigation of user interactions on communication platforms. Reconfigurable AHL nets have also been used in [2] [11] for a case study on modeling a concrete communication platform―namely Skype. The behavior of the Skype clients has been modeled in detail and the whole system specification has been demonstrated for concrete use case scenarios. For these scenarios model properties have been formulated and validated. Ubiquitous computing systems
![]()
Figure 1. Reconfigurable Petri net with (N, {r}).
(UCSs) start to penetrate almost imperceptibly in everyday life. To ensure a solid operation, a UCS needs reliable and efficient communication between its distributed computing components. [4] presents a formal approach based on reconfigurable algebraic higher order nets with individual tokens (AHOI) nets [12] . This approach allows modeling the synchronous and asynchronous communication in UCSs. AHOI nets contain nets and transformation rules as individual tokens.
In this paper we give an overview of possible control structures for reconfigurable Petri nets. Moreover, we introduce two new control structures for decorated reconfigurable nets, namely net transformation units and rule priorities. Moreover, we discuss those control structures for reconfigurable nets that have been already introduced. In Section 2 we explain reconfigurable Petri nets and give an introductory example that we use in the subsequent section. Next we introduce two new control structures for reconfigurable Petri nets. In Section 3.1 we define net transformation units and state their main features. In Section 3.2 we introduce application conditions. First we examine negative application conditions and next we discuss nested application conditions. Further control structures are investigated subsequently. We summarize in Section 4 the investigated control structures and point out related work. The last section concerns future work and concluding remarks.
2. Basic Notions
In the algebraic approach to Petri nets a place/transition net is given by N = (P, T, pre, post, m) with pre- and post-domain functions 
and a marking
, where 
is the multiset of places. A transition t is m-enabled for a marking if we have
, and in this case the follower marking is given by 
and 
is called a firing step. In [13] new features have been added to gain an adequate modeling technique. The extension to capacities and names is quite obvious. More interesting are the transition labels that may change, when the transition is fired. This allows a better coordination of transition firing and rule application, for example can be ensured that a transition has fired (repeatedly) before a transformation may take place. This last extension is conservative with respect to Petri nets as it does not change the net behavior, but it is crucial for the coordination of rule application and transition firing.
Reconfigurable Petri nets exhibit dynamic behavior by the token game of Petri nets and by net transformation by rule application. The transformation concept that is used for reconfigurable Petri nets is double-pushout approach on directed, labeled graphs. This approach has been lifted to a categorical framework using a morphism class
, with various instantiations, called 
-adhesive high-level replacement (HLR) systems (see [14] ). Place/transition nets (see [15] ) as well as decorated place/transition nets (see [13] ) and AHL nets (see [16] ) have been shown to be 
-adhesive HLR categories. So they conform to a categorically defined replacement systems, that provides the main constructions as well as a huge amount of notions and results (see [15] ). Other net types, e.g., elementary nets, colored nets, have been shown to have that properties as well, but have not been further investigated.
Net rules and transformations are based on net morphisms. These map places to places and transitions to transitions. They are given as a pair of mappings for the places and the transitions, so that the structure and the decoration are preserved and the marking may be mapped strictly. A rule is given by the left-hand side, interface and right-hand side net. In this contribution we omit the interface due to reasons of space and concentrate on the essence of net rules and transformations. An occurrence morphism o identifies the left-hand side in the given net
N. Then the application of a rule r yields a transformation step 
can be constructed in two steps, pro-
vided that specific gluing conditions hold. The characterization of specific points is a sufficient condition for the existence and uniqueness of the transformation.
The combination of one net together with a set of rules leads to a reconfigurable Petri nets
, where N is a Petri net, more precisely a place/transition net, a decorated place/transition net or an AHL net and R is a set of net rules of the corresponding net type.
In Figure 2 the transformation of the net N by applying the rule r is depicted, where the grey transition with label T is replaced by a transition with reversed arcs. Obviously, N' is now enabled and live.
3. Control Structures
Modeling with reconfigurable nets is obviously Turing complete, but to be practically relevant, control structures are required to specify the application of the rules more precisely. These control structures may belong to
the Petri nets, as labels, names, capacities and other decoration of the net [13] . Other control structures may determine the application of rules. They concern the situation that may or may not be given or they concern the order of the rules to be applied. We first investigate control structure for the transformation part, namely net transformation units, rule priorities and application conditions. Next we deal with control structures for Petri nets, as labels, transition priorities and inhibitor arcs.
3.1. Net Transformation Units
Graph transformation units have been introduced to graph grammars as the basic units for graph programming [17] . Control conditions can be given by regular expressions, describing in which order and how often the rules and imported units are to be applied. A large body of results has been developed since then [18] -[21] , see also [22] . Net transformation units are the transfer of graph transformation units to reconfigurable Petri nets. The underlying theory concerns high-level replacement (HLR) systems and is an abstract formulation of transformation systems in terms of category theory. In this frame work HLR units [18] that allow structuring the transformations have been given. Here, we instantiate this theory obtaining net transformation units. A net transformation unit is a tuple 
where R is a finite set of rules, and ![]()
is a control expression defined over the set Names. Thus, the control expressions are given over the names of rules and are defined recursively: ![]()
implies![]()
, so each rule name is an atomic control expression and denotes the application of the corresponding rule. ![]()
and ![]()
implies both ![]()
and![]()
. The first denoting the sequential composition of both control expression, the second being the choice operator allows the application of either the expression C1 or C2. Last but not east, there is the Kleene closure, denoting that an arbitrary number of iterations may be executed, so ![]()
implies![]()
.
An example is transformation unit (R, nm, r1; r2*; r3) where R and nm are given in Figure 3. The control expression r1; r2*; r3 determines that first rule r1 is executed, then rule r2 is applied repeatedly and at last r3 is applied once. So, this unit only yields Petri nets that are circles.
Priorities of rules can be modeled in transformation units as well. But a priority control condition that gives higher priority exclusively to rules is decidable, whereas one that gives higher priority to some imported transformation unit is no longer decidable (see [19] ). So, we define them explicitly in this paper. Given a set of rules R, then a partial order ≤ over R defines the priorities of the rules. Then a rule r is applicable if there is an occurrence morphism ![]()
that satisfies the gluing conditions and there is no rule![]()
, so that r is applicable and r ≤ r.
3.2. Application Conditions
Next, we investigate the use of application conditions. Negative Application Conditions (NAC) for reconfigurable Petri nets have been introduced in [23] and provide the possibility to forbid certain rule applications. These conditions restrict the application of a rule forbidding a certain structure to be present before or after applying a rule in a certain context. Such a constraint influences thus each rule application or transformation and therefore changes significantly the properties of the net transformation system. Rules with NACs as shown in Figure 4 have an additional set of nets NCi, denoting the forbidden contexts. Formally, a rule is applicable only if match
![]()
Figure 3. Transformation unit (R, nm, r1; r2*; r3).
m cannot be extended to a match mi such that![]()
. The nets NCi together with the morphisms ![]()
are associated to one L, indicating that no extension of m should exist for any![]()
.
An example is given in Figure 5, where the rule r deletes no element of L. So, the rule could be applied again. The NAC checks that the net NC is not in the context of the application, thus forbidding the repeated application of the rule r for the same match. So, repeated application of r with different occurrences may yield the net N1, but the net N2 cannot be obtained by applying r.
A substantial extension of negative application conditions providing a much greater expressiveness are nested application conditions [24] -[26] that have been given in the framework of ![]()
-adhesive transformation systems. Stated in terms of reconfigurable Petri nets a nested application ac over a net P and its satisfaction by a morphism ![]()
is defined inductively:
・ ![]()
and every morphism satisfies true,
・ ![]()
, where ![]()
is a net morphism and ac' is an application condition over the net C, and a net morphism ![]()
satisfies ac, if there exists an injective net morphism q with ![]()
and q satisfies ac',
・ ![]()
, where ac' is a condition over P, and a morphism ![]()
satisfies ac, if p does not satisfy ac',
・ ![]()
, where aci belong to some set of conditions over N for ![]()
and a morphism ![]()
satisfies ac, if p satisfies aci for some i.
As an example consider the rule r in Figure 6. The application condition ac states that no loops of size 1 or 2 are created by the application of the rule r: This is formalized by ![]()
where the injective net morphisms in Figure 6 denote the net expressions x, y and z.
3.3. Further Control Structures
In this section we deal with additional control structures as priorities and labels. Labels and labels that change when a transition fires have been considered for decorated PT nets in [13] . These transition labels may change when the transition fires. This feature is important for the application of a rule after a transition has already fired and cannot be modeled without changing the labels. Considering the tokens in the post place of the transition does not work, because these tokens may be consumed as well. The extension to changing labels is conservative with respect to Petri nets as it does not alter the net’s behavior, but it is crucial for the control of rule application and transition firing.
Further important control structures in Petri nets are priorities of transitions and inhibitor arcs (e.g. [27] ). The first ensure that an order of transitions restricts the firing, so that a transition may fire only if it has the highest priority of all enabled transitions. The set of transitions T is equipped with a partial order ≤ on the transitions. A
![]()
Figure 5. Example for a negative application condition.
![]()
Figure 6. Example of a nested application condition.
transition ![]()
is enabled under a marking m, if![]()
, if ![]()
and if for all t being enabled under m we have![]()
. Based on a suitable function this concept has been shown to be compatible with reconfigurable Petri nets in [28] . Inhibitor arc enforce that a transition may only fire when the place connected by an inhibitor arc is empty, thus inhibitor arcs can be generalized by a function![]()
. In [28] this concept has been formulated categorically and is shown to be compatible with reconfigurable Petri nets.
In timed Petri nets (e.g., time Petri nets [29] , deterministic timed Petri nets [30] and timed coloured Petri nets [31] ) time can be considered a control structure since the firing of transitions is restricted. Based on the concepts of [31] reconfigurable timed Petri nets have been introduced in [32] .
4. Summary of Control Structures and Related Work
In the following we summarize the concepts that have been discussed in the previous sections. Moreover, we state for which kind of Petri nets these results have been obtained and point out the corresponding literature. Table 1 states which concepts affect the application of rules, which affect the firing of transitions, which coordinate both and which concepts enforce an order based on priorities.
Table 2 states if the corresponding control structure is available for the various types of Petri nets and gives the corresponding reference. We have examined place/transition nets, decorated nets and algebraic high-level nets. Since AHOI nets have nets and rules as tokens, they control the dynamics directly and thus have not been considered here.
Table 3 concerns the tool support. Editing and simulating reconfigurable Petri nets requires tool support, there are two tools explicitly dealing with reconfigurable Petri nets ReConNet [8] and the RON-editor [33] . The AGG system [34] is an attributed graph transformation system but has also been used for modeling reconfigurable Petri nets. We have omitted here the large range of other graph transformation tool, that are in principle also capable of modeling reconfigurable Petri nets.
![]()
Table 1. Types of control structures.
![]()
Table 2. Literature on control structures.
![]()
Table 3. Controls structures in tools.
5. Conclusions
In the contribution a survey over the control structures for various types of reconfigurable Petri nets has been given. We have investigated several types of reconfigurable Petri nets, namely place/transition nets, decorated nets and algebraic high-level nets. We have given an outline of various control structures for these types reconfigurable Petri nets.
As a result, we can state that there are suitable concepts for control structures for the convenient use of reconfigurable nets. Nevertheless, there only a few of these results are realized in tools. Obviously, future work is to eliminate the open questions, indicated by dashes in Table 1, most of which are straightforward. More interesting is the realization of control structures in the tools. Negative application conditions are currently developed for the tool ReConNet.