The Petri net standard ISO/IEC 15909 comprises 3 parts. The first one defines the most used net types, the second an interchange format for these - both are published. The third part deals with Petri net extensions, in particular structuring mechanisms and the introduction of additional, more elaborate net types within the standard. This paper focuses on the latter issue: how should a new net type be added, while guaranteeing the compatibility with the current standard. The extension of Petri nets with static or dynamic priorities is studied, showing design choices to ensure the desired compatibility. The result is integrated within the standard companion tool, PNML Framework. Then, the approach is generalised so as to be used at a later stage for other Petri nets extensions.
Extensions are, for instance, the support of modularity, time or probabilities. Enrichments consider less significant semantic changes such as inhibitor arcs, capacity places, etc. This raises flexibility and compatibility issues in the standard.
One of the interesting features in Petri nets is priorities. There are a number
possibilities: static priorities and dynamic priorities, as summarised in [
This paper focuses on this objective: enrich existing Petri net types with both static and dynamic priorities. To do so, we explore a modular and generic enrichment mechanism that benefits from the current metamodels architecture of the standard. Thus, we can preserve consistency between existing Petri net types and those obtained with the proposed enrichments.
The paper is structured as follows. Section 2 summarises the specific aims of part 3 of the standard. Section 3 defines prioritised Petri nets, before describing, in Section 4, the introduction of Prioritised Petri nets types in the standard metamodeling framework. The metamodels obtained are then integrated within PNML Framework, and experimental results are reported in Section 4.3. Section 5 discusses the expertise drawn from the case of Prioritised Petri nets, so as to give general guidelines for the integration of a new Petri net type within the standard. 2
While parts 1 and 2 of the ISO/IEC 15909 standard address simple and common Petri nets types, part 3 is concerned with extensions. These can take several forms, as described in Section 2.1. The work on these issues started with a oneyear study group drawing conclusions w.r.t. the scope to be addressed. According to the study group conclusions, the standardisation project was launched in November 2010, for delivery within 5 years. The choices to be made must of course ensure compatibility with the previous parts of the standard, as discussed in Section 2.2. 2.1
The Petri net extensions considered can be of different kinds: nodes or arcs extensions, structuring mechanisms, new Petri net types. One can even consider the possibility of tools exchanging Petri net properties through the net files. In this section, we present the main ideas underlying these possibilities. Enrichments are concerned with the addition of a new type of node or arc to an already existing Petri net type. Typical examples of such extensions are inhibitor arcs or capacity places.
Enrichments5 are rather simple extensions since, although they modify the net semantics, they do not not require the manipulation of data which is not already described in the Petri net type. Indeed, let us illustrate this with the capacity place example. If a net is extended with capacity places, the capacity only indicates a maximum marking the place can hold. The marking being already an element of the Petri net type description, adding capacities is straightforward. The mechanism for doing so is independent of the Petri net type: it is defined as a maximal marking for the place in the same manner as its initial marking is defined.
We have already tested enrichment mechanisms in practice within PNML
Framework, the companion tool to the standard [
Attribute Extensions ObjectNature
The experiment consisted in extending the metamodel of PT-Net, first by defining the special arcs nature as attribute extensions, whose metamodel is depicted in Fig. 1. Then, the extended PT-net metamodel is built by merging the current PT-Net metamodel and importing the attribute extensions one. This modular definition approach is put into practice in Section 4 and the use of the import and merge relationships explained.
Modularity and structuring mechanisms are essential for modelling and analysis
purposes. Such mechanisms are independent of the Petri net type and should
thus be general enough. Preliminary theoretical work in that direction has been
presented in [
types [
Even though the work on structuring mechanisms has progressed well, there
are still numerous issues to be considered, as detailed in [
New Petri net types build on existing types — at least the Core Petri Net model — enhancing them with specific features which could be a new attribute or a new element. However, they are distinguished from “enrichments” in that they necessitate the elaboration of specific additional constructs. As an example, dynamically prioritised Petri nets associate with each Petri net transition a priority function with a marking as input and some value, e.g. a real number, as output. In this case, markings are already part of the defined Petri net elements, but real numbers are not. Therefore, in contrast to the capacity place example discussed above, dynamic priority is not an enrichment.
The core of this paper concerns how to introduce new Petri net types, and will thus be detailed by first studying the case of prioritised Petri nets in Section 4, and then generalising the approach in Section 5 to give guidelines for introducing new Petri net types in the future.
Properties such as safety and liveness properties, are a much longer term issue for standardisation, and will certainly not be achieved in the first release of part 3 of the standard, but might be in a future revision. The idea is to define storage mechanisms for properties so as to include properties within Petri net files. Thus, properties could be computed by one tool and later be exploited by another one. 2.2
The new features brought by part 3 of the standard must of course ensure compatibility with the previous stages, i.e. parts 1 and 2. This is essential since the already defined Petri net types constitute the building blocks.
Hence, an enrichment, such as the aforementioned capacity places, basically involves the addition of a new attribute to an already existing class of objects. In the case of capacity places, this attribute is a maximum marking. Note that this kind of extension easily applies to any type of net: a maximum marking is a marking as defined for the net type, be it a P/T net or a high-level net.
Similarly, the modular or structuring constructs must apply to all kinds of nets. They define the different parts of a module, that is the interface and the implementation, the composition policy, etc. The implementation is then an already known net type and the interface adds attributes telling which objects are imported or exported. The composition policy has so far been quite simple: place fusion and transition fusion, essentially. Nonetheless, work in this area must be pursued further.
Finally, adding new Petri net types will, as discussed in Section 2.1, build on at least the Petri net core model, thus preserving the essential characteristics common to all Petri net types. However, one can easily imagine that Prioritised P/T nets build on the P/T nets model while Prioritised high-level nets build on high-level nets. Further, several kinds of extensions could be applied so as to obtain a more elaborate net type, e.g. Prioritised Modular High-Level nets. Therefore, extensions must be carefully designed, allowing for a high degree of compatibility.
An important point must be investigated while some characteristics of Petri Nets can be considered as “orthogonal” (i.e. without influence on each other). As an example, priorities and colours can be considered separately and combined together because they do not affect the same attributes6. Such an orthogonality is important in the design of new Petri net types in the standard. This is discussed further in section 5. 3
This section introduces the definition of prioritised Petri nets, starting with static priorities.
A Statically Prioritised Petri net is a tuple SPPN = (P, T, W, M0, ρ), where: – (P, T, W, M0) is a Petri net. – ρ is the static priority function mapping a transition into R+.
We can also consider the case where the priority of transitions is dynamic,
i.e. it depends on the current marking [
A Prioritised Petri net is a tuple PPN = (P, T, W, M0, ρ), where: – (P, T, W, M0) is a Petri net. – ρ is the priority function mapping a marking and a transition into R+.
The behaviour of a prioritised Petri net is now detailed, markings being those of the associated Petri net. Note that the firing rule is the same as for nonprioritised Petri nets, the priority scheme influencing only the enabling condition.
are PTMarking for P/T nets and HLMarking for high-level nets. Definition 3 (Prioritised enabling rule).
– A transition t ∈ T is priority enabled in marking M , denoted by M [tiρ, iff: • it is enabled, i.e. M [ti, and • no transition of higher priority is enabled, i.e. ∀t0 : M [t0i ⇒ ρ(M, t) ≥ ρ(M, t0). – The definition of the priority function ρ is extended to sets and sequences of transitions (and even markings M ): • ∀X ⊆ T : ρ(M, X) = max{ρ(M, t) | t ∈ X ∧ M [ti} • ∀σ ∈ T ∗ : ρ(M, σ) = min{ρ(M 0, t0) | M 0[t0iρ occurs in M [σiρ}.
In the definition of ρ(M, X), the set X will often be the set T of all transitions, in which case the T could be omitted and we could view this as a priority of the marking, i.e. ρ(M ). The definition of ρ(M, X) means that we can write the condition under which transition t is priority enabled in marking M as M [tiρ, or in the expanded form M [ti ∧ ρ(M, t) = ρ(M, T ). We prefer the latter form if the range of transitions is ambiguous.
If the priority function is constantly zero over all markings and all transitions, then the behaviour of a Prioritised Petri Net is isomorphic to that of the underlying Petri Net.
Note that we choose to define priority as a positive real-valued function over markings and transitions — the higher the value, the greater the priority. We could equally define priority in terms of a rank function which maps markings and transitions to positive real values, but where the smaller value has the higher priority. This would be appropriate, for example, if the rank were an indication of earliest firing time. Note that the dependence of the priority function on the markings (as well as the transitions) means that the priority is dynamic. 4
Adding Prioritised Petri Nets to the Standard This section introduces the Petri nets metamodels modular definition approach defined in Part 2 of the standard and how we put it into practice to design prioritised Petri nets. 4.1
High-level Petri nets
Import is meant to use an element from another namespace (package) without the need to fully qualify it. For example, when package A includes: import B.b, then in A we can directly refer to b without saying B.b. But b still belongs to the namespace B. In the ISO/IEC 15909-2 standard, Symmetric nets import sorts packages such as Finite Enumerations, Cyclic Enumerations, Booleans, etc.
Merge is meant to combine similar elements from the merged namespace to the merging one. For example, let us assume that A.a, B.a and B.b are defined. If B is merged into A (B being the target of the relationship), it will result in a new package name A’: – all elements of B now explicitly belong to A’ (e.g., A’.b); – A.a and B.a are merged into a single A’.a which combines the characteristics of both; – actually, since A is the merging package (or the receiving package), A becomes A’ (in the model, it is still named A).
Merge is useful for incremental definitions (extensions) of the same concept for different purposes.
In the standard, this form of reuse is implemented for instance by defining Place/Transition nets upon the Core Model and High-level nets upon Symmetric nets, as depicted in Figure 2. That is why Symmetric nets elements and annotations are also valid in High-Level Petri nets (but not considered as Symmetric nets namespace elements anymore).
This extensible architecture is compatible with further new net types definitions, as well as with orthogonal extensions shared by different net types. These two extension schemes will be put into practice for defining prioritised Petri nets, as discussed in the next section. 4.2
A prioritised Petri net basically associates a priority description with an existing standardised Petri net, thus building a new Petri net type. The metamodel in XX Priority YY Petri Net – the root metaclass for priorities, represented by the Priority metaclass; – a priority level, which is an evaluated value represented by PrioLevel, associated with each instance of Priority; – the ordering policy among the priority values of the prioritised Petri net.
This ordering policy is represented by the PrioOrderingPolicy metaclass.
The purpose of priority levels is to provide an ordered scalar enumeration of values such that either the higher the value, the higher the priority, or the lower the value, the higher the priority. With the Priority Core package, and thanks to the PrioLevel metaclass, static priorities can thus be attached to transitions, as in the Static Priority PT-Net shown in Figure 4.
Using the same approach, Figure 6 shows a prioritised PT-Net which uses dynamic priorities. Dynamic priorities are built upon Priority Core.
This modular construction follows the extension schemes adopted so far in the PNML standard, that were explained earlier in this section. For instance, Static Priority PT-Net
Transition priority
Priority Core::Priority
Priority Core
Priority *
priorities 0..1 evaluation
PrioLevel +value: Real
PrioOrderingPolicy +policy: PrioOrdering «Enumeration»
PrioOrdering ASCENDING
DESCENDING --PrioOrderingPolicy must have a singleton instance context PrioOrderingPolicy inv: PrioOrderingPolicy.allInstances->size() = 1
High-Level Petri nets build upon Symmetric nets that they merge, and new specific sorts (such as List, String and arbitrary user-defined sorts) that they import. The use of the merge and import relationships is therefore consistent.
This approach is consistent with the idea that a new Petri net type subsumes the underlying one it builds upon, but the algebraic expressions it reuses are generally orthogonal to net types. Next, we introduce the metamodel for priorities.
Priority Metamodel Prioritised Petri nets augment other net models (e.g. PT or Symmetric nets) by associating a priority description with the transitions. Such priority schemes are of two kinds: – static priorities, where the priorities are given by constant values which are solely determined by the associated transition7; – dynamic priorities, where the priorities are functions depending both on the transition and the current net marking.
Figure 7 shows the modular architecture of priorities metamodels. The Priority Core package (detailed in Figure 5) provides the building blocks to define
which are solely determined by the associated binding element.
Dynamic Priority PT-Net Dynamic Priorities
Multiplication
PrioOperator Subtraction
Addition Priority Operators both Static Priorities and Dynamic Priorities. However, dynamic priorities are further defined using Priority Operators. Dynamic priorities can encompass static ones by using a constant function (for the sake of consistency in the use of priority operators). concrete prioritised Petri net type is created. Its type will then be a reference to the actual underlying Petri net type marking metaclass. For instance, in the case of prioritised PT-Net, this ref attribute will refer to the PTMarking metaclass.
A PrioTerm is composed of an operator (PrioOperator) and ordered subterms. This definition enables priority expressions to be encoded in abstract syntax trees (AST). For example, the conditional priority expression: if M (P 2) > 3 then 3 ∗ M (P 2) else 2 ∗ M (P 1), is encoded by the AST of Figure 9, assuming that: – P1 and P2 are places; – M(P1) and M(P2) are respectively markings of P1 and P2; – T1 is a transition the dynamic priority expression is attached to.
Guarded Expression
Multiplication GreaterThan Fig. 9. AST of the conditional expression: if M (P 2) > 3 then 3 ∗ M (P 2) else 2 ∗ M (P 1).
The priority operators are gathered within the Priority Operators package to allow for more flexibility in extending this priority framework. New operators can thus be added easily to this package.
Note that all these operators can also be found in ISO/IEC 15909-2, but are scattered among different sorts packages, thus directly tied to the sort they are most relevant for. We suggest for the next revision of the standard that they be gathered in separate and dedicated packages (e.g. arithmetic operators, relational operators, etc.). This refactoring will allow for more reusability across different Petri net type algebras definitions. 4.3
PNML Framework is one of the standard’s companion tools, which provides an intuitive and easy way to use Java Application Programing Interface (API) to handle standardised Petri nets models. The design and development of PNML Framework follows model-driven engineering (MDE) principles and relies on implementing mature technology such as Eclipse Modeling Framework (EMF).
Thanks to MDE, PNML Framework already uses the same modular
definition approach as in the standard. Dealing with new Petri net types as proposed
in this extension framework will thus be implemented in the same way as it
was for the first standardised net types [
Using such an approach, an API to handle the new net type models can be generated in any output language, not only Java. This is possible because EMF format is the standardised eXtended Metadata Interchange (XMI), which is XML-based. It is thus open to any technology which can handle XML. In PNML Framework, code generation templates are designed to automatically capture these annotations.
The standard uses UML merge relationship to implement the reuse between metamodels. Therefore, UML merge constraints (preconditions) and transformations (postconditions) should also apply in our framework as well, at the design level.
When we started the development of PNML Framework as a means for early assessment of the standard design choices, EMF did provide powerful code generation capabilities (including code merging). However it did not provide models merging in the sense defined by UML, which was a disappointment. It was up to the modeler to come up with a way to implement this. UML plugin did provide models merging, but this needs a round-trip transformation from EMF to UML and vice versa, which practically turned out to be messy.
Recently, EMF Compare plugin now provides a workspace editor and a programmaging interface to compare and merge models, in a version control fashion. This environment could be used to perform a basic merger in the following main steps: 1. (a) If the source package of the merge relationship does not have any specific elements different from the merge relationship target package, duplicate the package of target Petri net type in the merge relationship and rename it to the source of the merge relationship. (b) If there are more than one merge relationship, perform this iteratively by pair of packages, the source being incrementally augmented. (c) If the source package does have specific elements, then design it first and apply the merge with one target. If there many targets, apply previous step. 2. Select the packages to import and import them. 3. Add relationships and attributes which need the merge operation to complete first.
IBM’s Rational Software Architect also performs UML models comparison
and merger [
In the next section, we propose a generalisation of the metamodel modular definition approach we presented in this section, as an extension framework for the definition of new Petri net types. 5
We now generalise the approach used to create prioritised Petri nets metamodels to set up an extension framework as a proposal to be considered for ISO/IEC 15909-3. The purpose is to compose extensions on an existing Petri net type to build a new net type. It is illustrated by Figure 10, where XX Extension and ZZ Extension are extensions metamodels (e.g. priority and time) which are composed over an existing YY Petri net type to build the (XX ◦ ZZ) YY Petri net type metamodel.
(XX ◦ ZZ) YY Petri Net
This generalised modular definition approach involves two important characteristics to build the new net type, that are the orthogonality and compatibility of the combined features (extensions).
Orthogonality must guarantee upward compatibility: current net types definitions must have the ability to be extracted from new definitions that build upon them. For example, a Core model can currently be extracted from a Symmetric net model; a partial Symmetric net model can be extracted from a High-Level net model, after having pruned annotations and inscriptions that are not recognised in Symmetric nets.
Let us consider a Petri net type made of n extensions that are orthogonal in the sense defined in section 2.2. Compatibility must guarantee that the firing rule of the new net is sound. This is the case when the set of firable transitions can be expressed as follows:
Tf = n \ firing i(T ) i=1 where Tf is the set of firable transitions and firing i are partial firing functions using the dedicated attributes associated with a Petri net type extension.
These characteristics yield semantic issues that we are currently
investigating with a group of Petri nets experts to assess how they should be tackled.
Underlying issues regarding semantics of Petri nets in terms of: (i ) abbreviation
(e.g. P/T vs. Colored nets), (ii ) extension of the modeling power (e.g. inhibitor
arcs) and (iii ) change of semantic domain (e.g. time vs. stochastic) must be
properly addressed [
Experts must therefore pay careful attention to the compatibility issue between features since it is not considered at the syntactic level which concerns their metamodels definition. 6
The standardisation effort of the International Standard ISO/IEC 15909 is currently focused on the third part, where enrichments and extensions to Petri nets are being defined. This paper presents an extension scheme based on the standard approach, in order to define prioritised Petri nets. The presented work is structured in two steps: first the formal definition of prioritised Petri nets and their enabling rule, and then their metamodels definition.
Prioritised nets metamodels are built in a modular way. First, the priority core metamodel defines the necessary concepts for static priorities. Then the dynamic priorities package reuses the core package, while adding operators from the priority operators package to its definition. Using these building blocks, a static priority PT-Net can thus be defined upon the classic PT-Net package from the standard, using the priority core. A dynamic priority PT-Net can also be defined in the same way, this time using the dynamic priorities package.
Integrating new Petri net types defined using such an approach into the companion tool, PNML Framework, is no more different than the initial work which enables the support of the current standardized types (PT-Net, Symmetric Net and High-Level Petri Net). PNML Framework being based on mature modeldriven engineering tools such as Eclipse Modeling Framework, enabling support of new Petri net types follows three simple steps: (i ) create the metamodels of the extensions and the new type, (ii ) annotate the metamodels with PNMLspecific information (XML tags and attributes), and finally ( iii ) click on a button to generate the Java API to handle the new type. The annotation step follows simple conventions that are embedded in the current metamodels, and which are easy to reproduce. Code generation templates have been designed to capture these annotations.
The purpose of this investigative work is to propose an extension framework which enables experts to easily define new Petri net types, in a consistent way with the current standard approach. Orthogonality and compatibility of combined extensions to define new Petri net types are paramount for the semantic aspect of the new net types, in particular regarding firing rules. Syntax will usually not be an issue, as the metamodel definition approach presented does not consider semantic rules.
Perspectives to this work include presenting this approach as a contribution to the next plenary session of the ISO/SC 7/WG 19 working group (responsible for the standardisation of Petri nets in the ISO/IEC 15909 series), and experiment new Petri net types definitions involving different features combination such as time and priorities.