Universiteit Leiden
Opleiding Informatica

A Formal Representation and Calculation Method
for Generic Petri nets

Name:
Date:
1st supervisor:
2nd supervisor:

J. Viëtor
31/05/2016
Jetty Kleijn
Fons Verbeek

MASTER’S THESISLeiden Institute of Advanced Computer Science (LIACS)
Leiden University
Niels Bohrweg 12333 CA Leiden
The Netherlands

A Formal Representation and Calculation
Method for Generic Petri nets
J. Viëtor
May 31, 2016
Abstract
Petri nets can be used for a wide range of applications. However due tothe increasing amount of extensions made to “classic” Petri nets there is no
single unifying method to work with all of them. This paper introduces
a generic notation model for Petri net classes, encompassing the mostpopular types. This model is then extended with algorithms that canbe used for all classes that fit the model. To complete the solution, an
open-source proof of concept Petri net simulator/animator (PetriCalc) is
provided which works according to this theory.

12Contents
1 Introduction

5

2 Preliminaries

93 What is a (Petri) net?
11
3.1 Theoretical focus . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4 Marked Petri nets . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 Common properties of marked Petri nets
19
4.1 Enabledness and firing . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Arc types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3 Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.4 Concurrency and auto-concurrency . . . . . . . . . . . . . . . . . 22
5 Algorithms for experimental analysis of marked Petri nets
25
5.1 Single transition steps . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2 Concurrent transition steps . . . . . . . . . . . . . . . . . . . . . 26
5.3 Auto-concurrent transition steps . . . . . . . . . . . . . . . . . . 28
5.4 Maximal stepping . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6 Natural Petri nets

33

7 Properties of NatNets
39
7.1 Limitations to the expressive abilities of a single arc . . . . . . . 39
7.2 Arc label subtypes . . . . . . . . . . . . . . . . . . . . . . . . . . 39
8 PetriCalc: Implementation in code43

9 Discussion and conclusion

51

3

4

1

Introduction

The usefulness of Petri nets is undisputed, and there is a myriad of tools available
to work with them - anything from interfaces for building Petri nets to analysing
their structure or running simulations using them.
Unfortunately, this increasingly widespread use and interest has led to a
fragmentation of classes of Petri nets as well as confusion around the vocabulary
and semantic meaning used for them. There are various efforts (such as [HMR05,
BM01]) to classify and analyse transition systems, of which Petri nets are justone example.
While there are tools that allow running simulations on Petri nets, these aremostly geared towards animation of small nets, producing graphics. Tools fordoing large-scale simulations are much harder to find, and often crash-prone or
too slow to be of practical use. This problem became especially apparent while
Laura Bertens was working on [BKH+ 15], where she needed to simulate a Petrinet that contained millions of tokens and hundreds of places and transitions (seeFigure 1). This seemingly simple task proved to be too difficult for Snoopy (thetool the net was modelled in) or any other existing simulation method and/or
tool. Additionally, only a handful of places needed to be monitored for token
counts and these counts were only needed exactly every 5 simulation steps.
Inspired by the inability to simulate particularly large and/or complex Petrinets, a calculation tool (PetriCalc) was developed especially designed to beable to handle this. In order to do such calculations, it was important to havean efficient internal data model for the net as well as a straightforward andcorrect way to convert existing nets to this internal data model.
After completion of PetriCalc around the end of 2011, Jetty Kleijn andthe author of this paper agreed that the methods and data model as used in
PetriCalc could be very interesting if properly formalized. This paper is theresult of those efforts. The formal method was then turned into changes to PetriCalc itself so that it accurately follows this formal notation, of which thefirst version of PetriCalc could be considered a rough draft. Since PetriCalc
and the formal methods described in this paper are so closely tied together, theconstant goal to keep simulation possible for large and/or complex Petri nets
will be visible in nearly all decisions made.
Because of the new notation used to work with Petri nets, this paper takes
a different approach to Petri nets compared to most other literature. Usually
Petri nets are introduced as simple place-transition systems, then weights andother extensions such as colours, extra arc types, time and/or stochasticity areadded. In this paper however, we focus more on the notation, starting with analready extended Petri net model based loosely on and conforming to old andwell-accepted definitions of extended Petri nets such as [Pet77] and [Mur89].
Specifically, the notation is shifted from a place/transition-centric model toan arc-centric model. The reason for this shift is three-fold:First, we would like to provide a more direct translation from theory to computer programming code for running simulations. Using only a single concept5

(arcs) as opposed to two (places and transitions) makes this translation botheasier to follow and less complex.
Secondly, we would like a fast and efficient implementation of this code. Having only a single concept to keep track of makes optimizations easier and lowers
memory usage because there are less objects which matter to the calculations
to keep track of.
Finally, the focus on arcs allows us to come up with rules for combining arcs
together, which not only benefits optimization (by further reducing the objects
that we need to keep track of) but also assists net analysis efforts by providing
means of classifying groups of arcs together as opposed to only singular arcs.
The focus on speed and translation to computer programming code will
be visible as a recurring theme throughout this paper as the main motivation
behind most decisions that were made.
While the focus may be shifted, the model is still fully compatible with andintuitively similar to traditional models, and straightforward translations bothto and from those models to this model are possible. This enables the use of
all techniques and tools as discussed in this paper on many existing Petri net
classes and thus many existing Petri nets.
Throughout this paper both Demarcations and Definitions will be used. Demarcations give information on principles, ways of thinking; while definitions
give the harder, mathematically sound boundaries.
Demarcation 1 A Demarcation explains the reasoning or principles (softboundaries) of a subject, while a Definition gives mathematically sound(hard) boundaries.
Demarcations usually precede definitions, allowing terminology to be
used without fully defining it first. Additionally, they allow for easily looking
up the basic ideas behind concepts without needing to read through the fulldefinition.
This paper will begin with some preliminaries that establish basic principles.
It continues with a brief overview of Petri nets in the new notation, followedby an explanation of the theoretical focus of this paper. Then the concepts ofPetri net structure and Petri net classes are introduced, coming together witha marking to form marked Petri nets. With all the basics then established, it
continues with a list of various properties that hold for all nets that fit in the
new notation as well as algorithms for stepping through simulations with various
step types. At that point, the Petri net class of Natural Petri nets is introduced
and some properties of this class are explored. Finally, the translation of all
this theory to code is given and it ends with a short discussion and conclusion
section.

6

Figure 1: The Petri net from [BKH+ 15] modelling gradient formation. It has
125 places and 272 transitions.

7

8

2

Preliminaries

We use Z to denote the set of integers, meaning both positive and negative
whole numbers as well as zero; N to denote the set of natural numbers, meaning
positive integers including zero; and N∞ to denote N with the addition of thespecial symbol infinity (N∞ = N ∪ {∞}). In this paper, the only property of ∞that is used is that ∞ > i where i ∈ N.
A multiset µ : A → N is a mapping from the set A to N, with µ(a) indicating
how many times a occurs in the multiset. Sets and subsets can be seen as
multisets throughtheir characteristic
function:
0 if a ∈/XµX (a) =where X ⊆ A and µX : A → {0, 1}.
1 if a ∈ X
min and max denote the smallest, respectively largest element of a finite
totally ordered set.
A commutative monoid is a 3-tuple (L, ⊗, I ∈ L) where L is a set, ⊗ is acommutative and associative binary operator, and I is the identity element forthe ⊗ operation on set L.
The concept of “connected” elements will be used quite often in this paper.
In order to save space and make things easier to read, the symbol ‡ represents thephrase “connected to” and the symbol † represents the phrase “not connected
to”, where the nature of the connection is dependent on the context.

9

10

3

What is a (Petri) net?

This section introduces “Petri nets” as we will consider them in this paper. Since
the world of Petri nets is filled with a wide range of specialized net classes, it isimportant to clarify exactly which classes we are dealing with.
Petri nets are usually introduced as (annotated) directed bipartite graphs,
where the set of nodes is partitioned in two disjoint subsets. Places are in one
subset and transitions in the other. Places are never directly connected to places,
and transitions are never directly connected to transitions. Transitions represent
actions while places represent state variables. The state of these variables isrepresented by “marking” the places. Depending on the exact class of net, themarking of a place may be binary, a number, a set or even a complex expression.
The arcs between a particular transition and places define its sphere of influence.
The neighbourhood of an element consists of the element itself, the elements it
is connected to, and the arcs involved. A transition may not affect places outsideof its neighbourhood.
For the sake of unambiguity, these are the elements of a Petri net:
Demarcation 2 A transition is a representation of an action. The occurring of an action is called firing.
If a transition is allowed to fire, this transition is said to be enabled.
Whether a transition is enabled and the effect of its firing are fully definedby the arcs in its environment (see Definition 6).
Transitions will be visually displayed as rectangles:

Figure 2: A transition

Demarcation 3 A place is a representation of a state variable.
Places will be visually displayed as circles:

Figure 3: A place

Demarcation 4 The marking of a net defines a value d ∈ D (where D isa given domain) for each place in the net. A marking describes a state ofa net, but is not part of the net itself.
Markings will be visually displayed by writing the corresponding value
inside the places:11dFigure 4: A place with the value of the current marking

Demarcation 5 An arc connects a single place to a single transition. It
represents both under what conditions on its connected place its connectedtransition may fire (the arcs range) and how the value of its connected placeis altered when its connected transition fires (the arcs effect).
Arcs will be visually represented by a labelled line between a place anda transition, with the range and effect of the arc together forming the label:(r, e)
Figure 5: A place and a transition, connected by a labelled arc
Range and effect are not usually represented in this way. We have chosen
arc-labelled undirected bipartite graphs, as opposed to non-labelled directedbipartite graphs. More on this decision is explained in the following subsection.

3.1

Theoretical focus

We have introduced arcs as specifying an undirected connection between place
and transition, together with an arc label consisting of the arc range and arc
effect. This is not the usual representation of arcs, however.
In the usual representation, Petri nets are seen with a focus on either theplaces or the transitions, with a flow relation between them. The things thatgive Petri nets their behavioural properties are hence properties of the places
and transitions. The flow relation merely points out which places and transitions
affect each other.
This paper uses a quite different way of looking at things. Instead of focusing
on places and/or transitions, it focuses on the flow relation (the arcs) between
them. We assign properties to the arcs (specifically, the arc range and arc effect).
This leaves the places as nothing more than identifiers for specific parts of amarking, and transitions as nothing more than identifiers for a set of arcs. Since
they are identifiers for parts of a net, they are still quite useful to humans but
have lost their computational significance.
Because places and transitions have lost their computational significance,
only the arcs are left as important for computations. Instead of needing to keep
track of two different types of objects and their relation to each other, we only
have to keep track of one type of object: the relations themselves. This also has
the added benefit of making transformations on the net easier, such as combining
transitions.
12Since the properties that are computationally significant are all defined
through the arcs, it becomes possible to write down a single set of arc-based
rules that governs all behaviour. We shall refer to such rule sets as the class ofa Petri net, while the places, transitions and arcs themselves shall be referred
to as the structure of a Petri net.
Both the structure and class of a net are static for the lifetime of a net. But
there is also a third, dynamic part: the marking. These three parts together
fully describe a Petri net and its current state.
The structure defines what transitions, places and arcs (including their labels) exist in specific net. Changing the structure is thus effectively creating a
new, different, net.
The class defines how and under what conditions arcs interact with themarking of a net. The class can be seen as a set of ‘rules’, which the net must
follow. Changing the class doesn’t just create a new net: it creates an entirely
new type of net; hence the naming “class” for this part.
Finally, the marking describes the current state of a net. It is the dynamic
part, changing when a net evolves.

3.2

Structure

The structure of a Petri net is determined by places, transitions and the arcs
between them.
Definition 1 N = (P, T, A) is a PetriStructure, where:• P is a set of places.
• T is a set of transitions, such that P ∩ T = ∅• A is a set of arcs, each connecting a place and a transition and labelled with a tuple (r, e) where r is the range of the arc, and e is theeffect of the arc. If an arc a with label (r, e) thus connects (‡) placep ∈ P and transition t ∈ T , then we write:– aP = p– aT = t– aR = r– aE = eSome remarks about the above definition:• We require that P ∩ T = ∅, because P and T represent different entities.
• Each of P , T , and A is allowed to be infinite or empty.
• The graph represented by this definition is not directed, so unlike thetraditional definition of Petri nets, there is no distinction between input
arcs / places / transitions and output arcs / places / transitions.
13(r, e)(r, e)(r, e)(r, e)(r, e)(r, e)(r, e)(r, e)

Figure 6: An example of a Petri net structure. The (r, e) arcs are placeholders
for more concrete labels.
• There may be several arcs a 6= b such that aP = bP , aT = bT , aR , = bR
and/or aE = bE . In other words, the identity of an arc is not fully describedby its parameters (p, t, r, e).
Arc range and effect were partially chosen for practical reasons (they provide
a sensible base for calculations), but also partially inspired by [KK10], where
the ideas of range arcs and testing are heavily used. The ideas about localities
as they are used in [KK10] also mesh nicely with the theoretical focus of thispaper on arcs as opposed to places or transitions.
Taking into account the representation of places, transitions and arcs as introduced at the beginning of this section, an example net following this definitionof structure could look as depicted in Figure 6.

3.3

Class

The class of a Petri net describes the behavioural rules defining its dynamics.
First, let us introduce some new concepts: domain, the set of arc labels, therange function, the effect function, the combination operator and the identity
arc label. Together these are sufficient to define behaviour.
The domain together with the set of arc labels puts restrictions on the markings and arc labels of net.
14

Demarcation 6 The domain of a class defines the possible values that amarking may assign to places, as well as the possible values for arc range
and arc effect.
The set of arc labels of a class specifies which combinations of arc range
and arc effect may occur on arc labels.
The range and effect functions together describe the equivalent of what is
usually referred to as the firing rule.
The range function is used to define under what conditions an arc enables
its connected transition.
Demarcation 7 The range function of a class is used to determine forany given arc and marking whether a transition is enabled with regard to
the place the marking corresponds to. A transition is enabled if and only if
all the arcs connected to it enable it. In other words, a transition is enabled
when the range function of all its connected arcs evaluate to true for themarking of their connected place.
The effect function defines what happens to the place of an arc, when its
transition fires.
Demarcation 8 The effect function of a class determines for any givenarc and the current marking of its place what the resulting marking of its
place is after firing its transition.
In addition there is a combination operator that defines concurrent behaviour: how two arcs connected to the same place can be combined to createa single new arc that behaves as a simultaneous occurrence of these arcs, fromthe perspective of the range function and effect function.
Since simultaneous behaviour is inherently unordered, this operator is commutative and associative. Thus it may be used to combine any number of arcs
connected to the same place into one. See Figure 7 for an example.
Demarcation 9 The combination operator (⊗) of a class defines how
any two arcs connected to a shared place may be combined into a single
arc with the same effect as if the two arcs would work simultaneously. It is
commutative and associative.
All of the arc labels involved in the use of this operator must be in theset of arc labels of the class.
Finally, there is an identity arc label. This is effectively an “unconditionally,
do nothing” arc label. This sounds like a very useless arc label to have at first,
but it serves two key purposes.
Firstly, it makes it possible to make a fully connected net, where everytransition is connected to every place. Unconnected places and transitions canbe connected using an arc labelled with the identity arc label, without altering
the semantics of the net itself.
15

(a, b)(c, d)

a)(a, b) ⊗ (c, d)b)
Figure 7: In b, two arcs from a combined into one with a new label obtained
from the original arcs using the combination operator ⊗.

16

Secondly, the existence of this arc label is the final piece of the puzzle tobe able to claim that when put together with the set of arc labels and the
combination operator, a commutative monoid is created. This is desirable because commutative monoids have very convenient properties (specifically, being
associative and commutative).
Demarcation 10 The “identity arc label” (I = (Ir , Ie )), is an element of
the set of arc labels such that a ⊗ I = a for any given arc a. It must havean unconditional range, and may not alter any marking through its effect.
Putting all of the above into more formal language results in the following
definition of Petri net class:
Definition 2 A PetriClass is a tuple (D, fr , fe , L, ⊗, I) where:• D = (Dr , De , Dm ), where:– Dr is the domain for arc range.
– De is the domain for arc effect.
– Dm is the domain for markings.
• fr : Dr × Dm → {true, f alse} is the range function.
• fe : De × Dm → Dm is the effect function.
• L is a subset of (Dr × De ), the set of arc labels of the PetriClass.
• ⊗ : L × L → L as the combination operator.
• I = (Ir , Ie ) ∈ L, as the identity label, such that:– fr (Ir , i) = true for all i ∈ Dm
– fe (Ie , i) = i for all i ∈ Dm
• (L, ⊗, I) is a commutative monoid.
Note that because (L, ⊗, I) is a commutative monoid, there is only one I,
but there may be more than one valid Ir or Ie .
The property that (L, ⊗, I) is a commutative monoid is a particularly interesting one. Petri nets have commutative monoid tendencies when modelled
and/or viewed in various ways. For example, in [MM90] it is already shownthat Petri nets can be seen as monoids of places with a composition operator
on transitions (of which a PetriClass can be seen as a more generalized form
that only operates on arcs instead of places and transitions). In [DMM96] asimilar modelling method is used to show that both sequential and parallel stepsemantics (see subsection 4.3 for more on steps) can be modelled as monoids
as well. More recently, [KKPKR12] has taken the approach of modelling theconnections between places and transitions as monoids, again from the vantage
17

point of step semantics. The model described by PetriClasses takes inspirationfrom all of these and ends up with something complementary to the connection
monoids in [KKPKR12] (keeping the focus on arcs as opposed to steps), while
retaining the expressive ability that is seen in [MM90] and [DMM96]. This will
become more clear in section 6, where we introduce NatNets.
One might wonder why multiple arcs between one place and one transition
are allowed, especially since the combination operator allows combining them
together, preserving semantic meaning. The reason for this is to make it easier
to convert nets from other models to this model. And indeed, in a later section
we will use the combination operator to reduce the amount of arcs between
combinations of places and transitions to a maximum of one each. This greatly
simplifies the complexity of both the model in general as well as computations
done on it, by keeping the amount of arcs to a minimum.

3.4

Marked Petri nets

Combining the above definitions of PetriStructure and PetriClass together,a marked Petri net is defined as a combination of structure (PetriStructure),class (PetriClass) and marking (M ). The PetriStructure defines the structure of the net itself, the PetriClass defines the class of the net and the marking
defines the current state of the net. Only the last of those properties (the marking) can change within the operational semantics of a net, because changing
either of the other two would change the underlying net itself.
The combination of a PetriStructure, PetriClass and marking is called
permissible when they “fit” together:
Demarcation 11 A combination of PetriStructure, PetriClass andmarking is permissible when the marking assigns to the places of the PetriStructure elements from the domain for markings of the PetriClassand all arc labels are allowed by the PetriClass.
This gives us the following formal definition of a marked Petri net:
Definition 3 A marked Petri net N is a tuple N = (S, C, M ) where:• S = (P, T, A) is a PetriStructure, as in Definition 1.
• C = (D, fr , fe , L, ⊗, I) is a PetriClass, as in Definition 2.
• S, C, M is permissible by L, meaning that M : P → Dm is the marking and for all a ∈ A we have (aR , aE ) ∈ L

18

4

Common properties of marked Petri nets

We are now able to consider a marked Petri net (as defined in Definition 3)
as comprising of a PetriStructure, PetriClass and marking, but have notactually provided any of the three yet in a tangible form. Even without doingso, it is already possible to reason with marked Petri nets and further define
general properties that will hold true for all possible values S, C and M .

4.1

Enabledness and firing

The concepts of enabledness and firing were already briefly mentioned in Demarcations 2 and 7.
Before we can give the full formal definitions of enabledness and firing, we
first need to define the “place-transition-combined arc label”. This is a method
relying on the combination operator to reduce the number of arcs between any
given place and transition pair to a single arc.
Definition 4 Let (P, T, A) be a PetriStructure, p ∈ P and t ∈ T . Let
a1 , . . . , an be all distinct arcs connecting p and t. Let li be the label of ai
for 1 ≤ i ≤ n. The place-transition-combined arc label of p and t is thelabel resulting from I ⊗ l1 ⊗ . . . ⊗ ln .
The ordering of the arc labels used above does not matter, since ⊗ is bothcommutative and associative. Also note that by this definition the place-transition-combined arc label of unconnected places and transitions is the identity
arc label, as there are no labels li . This is desired behaviour because Defintion
2 requires I to unconditionally do nothing, which is semantically equivalent toa place and transition being unconnected.
An example of reducing number of arcs to one by using the place-transitioncombined arc label is given in Figure 8.
With place-transition-combined arc labels, we can now relatively easily givethe formal definitions of enabledness and firing. After all, now that we can
combine all arcs between any given place and any given transition into a single
arc, we only have to consider a single arc for each part of place and transition.
Since the identity arc label is required to always make both the range function evaluate to true and the effect function to not change the marking, this arclabel may be used when no arcs connect a place and transition. This has exactly
the same effect as simply leaving the markings for those places unchanged.
A transition is enabled when the range function is true for the place-transition-combined arc label of each connected place:
Definition 5 In a marked Petri net N = ((P, T, A), (D, fr , fe , L, ⊗, I), M )a transition t ∈ T is enabled when for all p ∈ P , fr (lr , M (p)) = true,
where l = (lr , le ) is the place-transition-combined arc label of p and t.
19

(a, b)(k, l)(g, h)(c, d)(i, j)(e, f )

a)(g, h)(a, b) ⊗ (c, d) ⊗ (e, f )b)(i, j) ⊗ (k, l)

Figure 8: A simple net with several combinable arcs, showing both before (a)and after (b) using the place-transition-combined arc label to transform the net
for all arcs where this is possible.
The firing of a transition defines a new marking with the result of the effectfunction for the place-transition-combined arc label of each connected place,leaving unconnected places unaffected.
Definition 6 In a marked Petri net N = ((P, T, A), (D, fr , fe , L, ⊗, I), M )the firing of an enabled transition t ∈ T changes M into M 0 so that ∀p ∈ P ,
M 0 (p) = fe (le , M (p)), where l = (lr , le ) is the place-transition-combined arclabel of p and t.
Note that since only the marking of a marked Petri net is affected by firing
a transition and the marking is transformed using the effect function (fe ), the
new marking is guaranteed to yield a permissible marked Petri net.

4.2

Arc types

In the notation used for Petri nets in this paper, places can be considered variables, merely holding values and playing no other role. Transitions can be seen
as identifiers for a collection of arcs. As a result of this, it is the arcs that do
all the work and are the most interesting to analyse. In this subsection, we will
explore the theoretically possible types of arcs in marked Petri nets. We will dothis through analysis of the possible values the arc labels can take.
Let us see if we can classify some major arc label types. Each arc label
consists of two parts: the arc range and arc effect. Since we know there is an
identity arc label (I = (Ir , Ie )), both of these can either hold a value that does
something or doesn’t do something. For the arc label range “doing nothing”
means being unconditional (fr (lr , i) = true for all i ∈ Dm , where lr is thearc label range). For the arc label effect it means not changing the marking(fe (le , i) = i for all i ∈ Dm , where le is the arc label effect). Since all ranges
that do nothing are indistinguishable from Ir by the range function, we shall20

use Ir to refer to all of them. Similarly, we shall use Ie to refer to all effects that
do nothing. This leads to four major arc label types (or arc classes):• No-operation arc labels (Ir , Ie )These arc labels have a range that is unconditional and an effect that does
not alter the marking. In other words: an arc label that is always enabled
and does nothing.
There is at least one arc label part of this classification: the identity label,I.
• Check arc labels ((r, Ie ), where r 6= Ir )These arc labels have a range with conditions and an effect that doesnothing.
This class of arc labels does not affect the marking of the place it isconnected to, but only checks the current marking.
• Radical arc labels (((Ir , e), where e 6= Ie )These arc labels have an unconditional range and are able to change themarking through their effect.
This class of arc labels can affect the marking of the place it is connected
to in some way, without checking the current marking.
• Conditional arc labels ((r, e), where r 6= Ir and e 6= Ie )These arcs both check the current marking of its connected place and may
affects that marking.
All arcs that have any range other than Ir and have any effect other thanIe are conditional arcs, making this the largest (and most interesting) classby far.
Until we define Dr , De , L, this is the only classification we can make on arcs,
as all we know is that there is a r and an e, and both may contain an identity
value or some other value. Later, when we have defined our first PetriClass,
we shall define some subclasses of arcs as well.

4.3

Steps

A step is an execution of actions. In its most simple form, it is nothing morethan firing a single enabled transition in a given marked Petri net. Doing so
results in a new marked Petri net, but does not change the PetriStructure or
PetriClass.
A firing sequence is a sequence of consecutively executed actions, and assuch may be seen as a list of steps. By performing steps in sequence, a firing
sequence is created out of the transitions that are chosen to be executed.
In the following subsections, we will use a method similar to the “policies”
of [DKPY08] to extend the singleton step into more complex steps, by changing
the net structure so that it represents these new steps as single steps.
21

(if marking is one, do nothing)0(if marking is zero, add one to marking)
Figure 9: Two arcs that would allow their connected transitions to fire in sequence, but not simultaneously: the upper arc first, then the lower arc.

4.4

Concurrency and auto-concurrency

Nets may also express concurrent behaviour, where multiple transitions may fire
simultaneously in a single step. The concept of “simultaneous” was already used
before (in Demarcation 9) and the combination operator is defined in terms of
it. In other words, the contextual meaning of “firing simultaneously” in a given
PetriClass is fully defined by the combination operator of that PetriClass.
Auto-concurrent behaviour, where a given transition may fire simultaneouslywith itself, is possible as well.
Going into the territory of concurrency, conflicts become important. These
are a type of resource contention, where the range of two arc labels each separately is enabled, but their combined arc label may not be. Combining certain
arc labels together may prevent further arc labels from being added to this combination and the other way around, creating a choice between them. When achoice like this needs to be made, the arcs are said to be in conflict.
Simultaneous and auto-simultaneous behaviour are similar to transactions.
In transactions multiple steps are executed in sequence, but considered as if
they were a single step. This is relevant, because transactions are still a subjectof research. In [BM97, BM00b, BM00a, BM01] a lot of groundwork is laid togeneralize transactions.
Transactions and simultaneous behaviour are not the same, however: it ispossible for transitions connected to two arcs to be able to fire in sequence, but
not simultaneously (example in Figure 9). Similarly, it is possible for transitions
connected to two arcs to be able to fire simultaneously but not in sequence(example in Figure 10).
The principles used in this section are heavily based on those used for transactions in the before mentioned [BM97,BM00b,BM00a,BM01]. Specifically, themethods used to “grow” transitions in Algorithms 4, 5 and 6 are similar to howtransactions can be created.
The combination operator of a PetriClass underlies the contextual meaningof simultaneous firing, and as such, we can actually use the combination operator
to generalize the simultaneous firing of multiple transitions to new singletontransitions. This allows us to use the same method on all step types, turning
each step type into a single transition being fired.
22

(if marking is two, remove one from marking)2(if marking is two, remove one from marking)
Figure 10: Two arcs that would allow their connected transitions to fire simultaneously, but not in sequence.

Demarcation 12 The (auto-)concurrent enabledness and firing of any
combination of transitions can be derived from a single “super transition”
where all arcs connected to the original transitions are copied and thesecopies connected to this new super transition; if a single transition is present
multiple times, the arcs connected to this transition must also be copied thatsame amount of times.
Because both the enabledness check (Definition 5) and firing (Definition 6)of transitions combine arcs going to the same place into a single arc, these supertransitions end up using the combination operator to resolve multiple arcs going
into the same place. Since simultaneous behaviour for any specific PetriClass
is defined in terms of its combination operator, this means a super transition
thus behaves equal to the simultaneous firing of the transitions it was createdfrom.
Definition 7 Let N = (P, T, A) be a PetriStructure and S : T → N be amultiset of transitions. Then T(S) is a new super transition. For each arc
a ∈ A connecting a transition t ∈ S to a place p ∈ P , we add S(t) new arcsb, such that:• bp = ap• bt = T(S)• br = ar• be = ae
An example of the creation of a super transition from two transitions isshown in Figure 11.
Definition 7 describes how to combine multiple transitions into a single supertransition. The resulting super transition itself is also a transition, and thus
can be used to create further super transition. Since the combination operator(⊗) used on the arcs in this process is both commutative and associative, theorder in which transitions are combined does not matter as the resulting supertransition will be the same. We will now introduce notation that allows us
23

b

a

d

c

e

a)

b

b

a

a

T

c

c

d

d
e

e

b)
Figure 11: The leftmost two transitions in (a) are combined into a single supertransition T in (b) that has the same behaviour as those two transitions would
have when fired simultaneously. The arc labels have been simplified to single
letters to condense space and preserve the ability to clearly distinguish thevarious labels of the involved arcs.
to easily combine transitions into a new super transition. This is a transition
analogue to the combination operator for arcs.
Demarcation 13 The expression a ⊕ b where a, b ∈ T means to create
a new super transition, using the method to create super transitions as
described in Definition 7 with S(a) = 1 and S(b) = 1 and S(c) = 0 for allc ∈ T where c 6= a and c 6= b.

24

5Algorithms for experimental analysis of marked
Petri nets

First let us be clear about what is meant here by experimental analysis. In
general, two types of analysis can be done on (marked) Petri nets:• Experimental
This involves “running” the net under consideration (simulating its behaviour) by observing the effects on the marking of a firing sequence. Thisapproach generally requires a great number of simple steps to be performed, where not much (if any) insight into the inner workings of the net
is required. In particular, when creating a firing sequence any conflicts areresolved automatically as they turn into choices.
• Theoretical
This involves identifying and classifying the net under consideration, making statements about the structure of its (potential) behaviour. It includes
things such as reachability, locating and/or identifying deadlocks and invariants plus anything else that doesn’t involve running the net at any
point. This approach generally requires more insight into the inner workings of a net, as opposed to sheer computational power.
While both approaches can be automated, the experimental approach ismore generally applicable, more repetitive and requires the least amount ofunderstanding about what is being done. This makes it a great candidate for
automation in a general sense. Additionally, the theoretical approach is alreadycovered by the vast majority of existing literature on Petri nets.
That is why in this paper, we focus on the experimental approach. After all,the goal of the methods described in this paper is to achieve a high degree ofautomation and speed.
For the purpose of experimenting, using all the principles and definitions
from this paper so far, we can now construct algorithms that extend steps (seeSubsection 4.3). We shall extend steps from single transitions to (multi)sets oftransitions, thus covering simultaneous (auto-concurrent) firing.

5.1

Single transition steps

The step consisting of a single transition is the simplest case, not requiring
any special treatment. While its algorithm may be straightforward from theexplanation of steps (Subsection 4.3), we have not yet formally written it down.
In order to be complete, this is the basic algorithm for single transition steps:
Algorithm 1 To perform a step consisting of a single transition for agiven marked Petri net N = ((P, T, A), C, M ) with finite T , do the following:25

1. Create a set E of all enabled transitions, using Definition 5 to determine enabledness for all t ∈ T .
2. Pick any transition t ∈ E and fire it using Definition 6.
This method requires that T is finite. Note that conflicts are hidden because
in step two, “any” transition is picked, and thus a choice is made randomly,
avoiding conflicting situations and making simultaneous firing impossible.
A less efficient algorithm that only has the requirement that T is countable(so a random t can be picked reliably) is the following:
Algorithm 2 To perform a step consisting of a single transition for agiven marked Petri net N = ((P, T, A), C, M ) with countable T , do thefollowing:
1. Pick a random transition t ∈ T .
2. Using Definition 5, determine enabledness for t.
3. If t is enabled, fire it using Definition 6 and stop.
4. Otherwise, start over from 1.
This algorithm does not create a list of enabled transitions to pick from, butinstead picks a random transition and checks if it is enabled. Sadly, many nonenabled transitions can be picked before an enabled one is found. The complexityof Algorithm 1 is O(|T |) (because each transition is checked exactly once), while
the complexity of Algorithm 2 is potentially unknown and the algorithm maynever finish at all (for example when there are infinitely many transitions in T ,none of them enabled).

5.2

Concurrent transition steps

Next we will consider the case of transitions firing simultaneously with othertransitions (but not with themselves).
Note that from this point onward, we are making an important assumption:
we assume that combining a disabled arc with any other arc will always produce
a disabled arc. In other words, for the below algorithms we require that any
combination of arcs never has a wider range than any of the arcs it was createdfrom. As such, the algorithms from this point onward can only be used if thiscondition holds for the combination operator of the PetriClass of the marked
Petri net they are being used on.
To calculate concurrent steps, the PetriStructure is changed by adding a
new super transition T for each choice of transitions in T , thus defining a newnet. This new net simulates concurrent steps in the original net, and we can use
the same singleton step methods from Algorithms 1 or 2.

26

Algorithm 3 To create a new marked Petri net N 0 = ((P, T 0 , A0 ), C, M )representing concurrent transition steps for a given marked Petri net N =((P, T, A), C, M ) with finite T , let T 0 and A0 be defined by for every possible
finite subset S of T , extending T 0 with a new super transition T(S) as
described in Definition 7.
Note that (as mentioned in the preliminaries) (sub)sets can be seen as multisets, so Definition 7 may be used to construct super transitions even though
it only works on multisets and we are dealing with a set here.
If T is finite, then T 0 is also finite because it is constructed from all possiblecombinations of elements from T . Then the number of transitions in T 0 is at
most 2|T | (each transition has two possibilities: it is either in the set, or it isnot).
The main advantage of using Algorithm 3 is that it need only be done once,
during initialization, before the net is used. Afterwards, Algorithm 1 can beused to calculate the steps. This makes it a very generic method to handle
concurrency with a one-time cost regardless of the amount of steps that are
run.
Alternatively to using Algorithm 3, it is possible to change Algorithm 2 to
calculate concurrent transition steps. This is less efficient than using Algorithm
3 but can be used when T is infinite but countable.
This method works by “growing” super transitions, using the ⊕ operator as
mentioned in Demarcation 13. We keep adding transitions to a super transition
that do not disable the super transition, until at a randomly chosen point we
decide to fire it:
Algorithm 4 To calculate a concurrent transition step for a given marked
Petri net N = ((P, T, A), C, M ) with infinite but countable T , do the following:
1. T 0 = ∅2. Pick a random transition t ∈ (T \ T 0 ). (If T \ T 0 = ∅, stop.)
3. Add t to T 0 .
4. Determine if t is enabled, using Definition 5.
5. If t is not enabled, continue from 2 onward.
6. Randomly, either fire transition t and stop, or continue.
7. If T \ T 0 = ∅, fire transition t and stop.
8. Pick a random transition t0 ∈ (T \ T 0 ).
9. Add t0 to T 0 .

27

10. Determine if t ⊕ t0 is enabled, using Definition 5.
11. If t ⊕ t0 is not enabled, continue from 6 onward.
12. Set t := t ⊕ t0 .
13. Continue from 6 onward.
Note that because of the nature of infinite sets, the above algorithm has atendency to prefer combinations of smaller amounts of transitions over combinations of higher amounts of transitions, and is not guaranteed to pick fairly
from the various possible transitions that are enabled. This is because it is impossible to iterate over an infinite set. As such, using Algorithm 3 to create a
new net and then using Algorithm 1 is preferred and should be used when T is
not infinite.

5.3

Auto-concurrent transition steps

Now we consider the case of transitions firing concurrently with other transitions
including itself.
We would simply apply Algorithm 3 again, using a multiset S on T insteadof a subset. There is a problem with this, that the number of multisets definable
for a given non-empty set is infinite even if the set is finite. This means step 2of Algorithm 3 would never complete.
Instead, we will use a modified version of Algorithm 4, changed to deal withmultiple occurrences of transitions by removing the set that keeps track of usedtransitions (T 0 ) from the algorithm:
Algorithm 5 To calculate an auto-concurrent transition step for a given
marked Petri net N = ((P, T, A), C, M ) with countable T , do the following:
1. Pick a random transition t ∈ T .
2. Determine if t is enabled, using Definition 5.
3. If t is not enabled, start over from 1.
4. Randomly, either fire transition t and stop, or continue.
5. Pick a random transition t0 ∈ T .
6. Determine if t ⊕ t0 is enabled, using Definition 5.
7. If t ⊕ t0 is not enabled, continue from 4 onward.
8. Set t := t ⊕ t0 .
9. Continue from 4 onward.
Since this algorithm is based on Algorithm 4, it has the same disadvantage28

of having a bias towards smaller super transitions, and we’d like to avoid it if
at all possible.
Luckily, it is possible to alter the algorithm somewhat to make it fully consider all options equally, under the assumptions that T is finite and no transition
can be fired auto-concurrently infinitely. If these assumptions are true, we cando a full depth search to list all possible enabled super transitions created fromT , and then pick one from that list, giving them all an equal chance to occur
without bias. This is possible because we know in advance that we will not beable to keep adding transitions indefinitely and thus will not enter an infinite
loop.
This is a true limitation (but a natural one) on the marked Petri nets it canbe used on, as it means each transition must have at least one place connected
to it with an arc of limited range and an arc that causes a non-identity effecton the marking of this same place (this may be the same arc, but need not be).
In all other cases it would be possible to fire this transition infinite times once
enabled.
The new algorithm looks as follows:
Algorithm 6 To calculate an auto-concurrent transition step for a given
marked Petri net N = ((P, T, A), C, M ) with finite T and each transition
in T having a connected arc a where ar 6= Ir and a connected arc b where
be 6= Ie and ap = bp , do the following:
1. A = ∅, B = ∅, C = ∅2. For each transition t ∈ T :• Determine if t is enabled, using Definition 5.
• If t is enabled, add t to A, B and C.
3. For each transition t ∈ A:
• For each transition t0 ∈ B:
– Determine if t ⊕ t0 is enabled, using Definition 5.
– If t ⊕ t0 is enabled, add t ⊕ t0 to C and A.
• Remove t from A
4. If A 6= ∅, go to 3.
5. Fire a random transition in C.
This algorithm simply creates all possible enabled super transitions and thenpicks one from the list when all possibilities have been determined.

5.4

Maximal stepping

An additional requirement on (auto-)concurrent steps that are maximal (asspecified in [Bur83]) is that it will only ever fire an enabled (super or regular)29transition if it cannot be extended with more transitions in the net (using ⊕)without disabling it.
To do so, we can alter Algorithm 4 as follows to calculate maximal concurrent
steps:
Algorithm 7 To calculate a maximal concurrent transition step for agiven marked Petri net N = ((P, T, A), C, M ), do the following:
1. Create a new empty set of transitions T 0 .
2. Pick a random transition t ∈ (T \ T 0 ).
3. Add t to T 0 .
4. Determine if t is enabled, using the method from Definition 5.
5. If t is not enabled, continue from 2 onward.
6. Set T := t
7. If T \ T 0 = ∅, fire transition T and stop.
8. Pick a random transition t0 ∈ (T \ T 0 ).
9. Add t0 to T 0 .
10. Determine if T ⊕ t0 is enabled, using the method from Definition 5.
11. If T ⊕ t0 is enabled, set T := T ⊕ t0 .
12. Continue from 7 onward.
And as follows to calculate maximal auto-concurrent steps:
Algorithm 8 To calculate a maximal auto-concurrent transition step fora given marked Petri net N = ((P, T, A), C, M ), do the following:
1. Create a new empty set of transitions T 0 .
2. Pick a random transition t ∈ (T \ T 0 ).
3. Determine if t is enabled, using the method from Definition 5.
4. If t is not enabled, add t to T 0 and continue from 2 onward.
5. Set T := t
6. If T \ T 0 = ∅, fire transition T and stop.
7. Pick a random transition t0 ∈ (T \ T 0 ).
8. Determine if t ⊕ t0 is enabled, using the method from Definition 5.

30

9. If T ⊕ t0 is not enabled, add t0 to T 0 and continue from 6 onward.
10. Set T := T ⊕ t0 .
11. Continue from 6 onward.
Being maximal steps, neither of these two algorithms suffer from the problem
their non-maximal variants have, where there is a bias towards smaller transition
combinations. After all, these smaller combinations are not allowed to be fired at
all in maximal steps. Hence it is not necessary to determine all possible enabledtransition combinations and we can simply grow a single arbitrary combination,
instead.

31

32

6

Natural Petri nets

The previous sections go about as far as possible into the theory of marked
Petri nets without defining C in the tuple N = (S, C, M ). We will now define
a class of Petri nets (i.e.: nets that share a single PetriClass, as mentioned in
Definition 2) that we shall call natural Petri nets. All of these nets share thesame PetriClass that we shall call NatNetClass.
In the NatNetClass PetriClass the domain for the markings is represented
by natural numbers, the domain for range is N∞ , the domain for effect is Z, therange function is a simple bounds check, the effect function is an addition andthe combination operator consists of a near-trivial hybrid between addition andtaking the minimum and maximum.
NatNetClass can be seen as the most immediately intuitive instantiation ofPetriClass, and represents one of the most commonly accepted definitions of
a Petri net: an extended net as described in [Pet77] and later further explainedin more detail in [Mur89] and [DR98]. It fully expresses extended Petri nets
as described, with multiplicity on the arcs (and even with the inhibitor arc
extension).
The following definition is quite a bit of theory all at once, and thus is
explained step by step immediately afterwards.
Definition 8 The PetriClass NatNetClass = ((Dr , De , Dm ), fr , fe , L, ⊗, I)
where:• Dr consists of tuples (u, l, h), where l, h ∈ N∞ and u ∈ N.
• De is Z.
• Dm is N.
• fr ((u, l, h), v) =true if l ≤ v ≤ h and u ≤ v, where (u, l, h) ∈false otherwise

Dr and v ∈ Dm
• fe (e, v) = v + e, where e ∈ De and v ∈ Dm
• L comprises those ((u, l, h), e) where ((u, l, h), e) ∈ Dr × De and u ≥−e.
• ((u1 , l1 , h1 ), e1 ) ⊗ ((u2 , l2 , h2 ), e2 ) =(u1 + u2 , max(l1 , l2 ), min(h1 , h2 )), e1 + e2 )• I = ((0, 0, ∞), 0)
For convenience, we will define a shorthand for Petri nets with the NatNetClass PetriClass:33

Definition 9 A natural Petri net or NatNet = (S, M ) is a marked Petrinet (S, C, M ) where C = NatNetClass.

Natural Petri net domain
The marking domain of a NatNet is the natural numbers (N). In other words:
all positive whole numbers. This means markings may never become negative
in NatNets (since negative numbers are not in N).
The range domain of a NatNet is a tuple (u, l, h), where u, l, h ∈ N∞ . The
formal meaning is defined in subsection 6. l and h represent the lower and higher
bounds of the range, with the intended meaning that it is connected to a transition that is enabled if the markings corresponding to the connected places arewithin the bounds. u represents the amount of tokens “used” by the transition.
We need to differentiate between the lower bound and the actually used amountto accommodate the difference between checking tokens without using them andarcs that use tokens. An example of this can be found in subsection 6. The lower
bound may be higher than the upper bound. Such labels permanently disable
any connected transitions. As an example, the nonsensical range (3, 2, 1) will
never enable any transitions, as there are no values v that can make the statement 2 ≤ v ≤ 1 true. The addition of infinity to the domain of the range means
we can also define ranges that have no upper bound (when h = ∞), or are neverenabled (when l = ∞ or u = ∞) without the need to resort to nonsensicalvalues like above.
The effect domain of a NatNet is Z instead of N to allow the marking togo either up or down with all whole numbers. Since there is no upper limit(capacity) on the markings of places, any zero or positive effect is always avalid. Negative values could bring the marking outside of N, however — sothrough the restrictions placed on the set of arc labels we only allow effects thatare guaranteed to not make any marking negative (see subsection 6 for details).

Range and effect functions in NatNets
The range and effect functions of a NatNetare both near-trivial, and have beenchosen to most closely match their intuitive meaning:
The range function
 of a NatNet is:true if l ≤ v ≤ h and u ≤ v
fr ((u, l, h), v) =, where (u, l, h) ∈ Dr andfalse otherwisev ∈ Dm .
In other words, only when l ≤ v ≤ h and u ≤ v will arcs enable connectedtransitions. In plain English: the current value of the marking must be between
the lower and upper bound of the range, inclusive, and the current value of themarking must be at least the amount of used tokens. A quite straightforward
requirement which should not need further explanation.
The effect function of a NatNet is fe (e, v) = v + e. In plain English: add
the effect of the arc to the connected place’s current value of the marking to34

produce the new value of the marking for that place.

Allowed arc labels in NatNets
The requirement that ((u, l, h), e) ∈ Dr × De is already a requirement for all
marked Petri nets. It is not specific to NatNets.
NatNet add one other requirement to the set of arc labels, however. u ≥ −emust hold, to make sure the effect of an arc will never bring any given marking
outside of Dm . We’re requiring the negative effect of an arc to never be larger
than the lower bound on the range. This means the effect function will neverreduce the connected place’s marking below zero for any enabled transition, as
it can only be enabled when l ≤ the current marking while u ≤ l and u ≥ −e,thus u − e ≥ 0.

The combination operator of NatNets
As stated in Demarcation 9, the combination operator defines how any two arcs
connected to a shared place may be combined into a single arc with equal behaviour as the two arcs behaving simultaneously. In order to keep the definitionof Petri nets generic, the concept of “simultaneous behaviour” is not covered at
all by Petri nets. It is mentioned, but never defined or even explained. This iswith good reason: by tying the term to the combination operator, we move thetask of defining what simultaneous behaviour is to the combination operator
itself. To clarify: what for any given PetriClass is considered simultaneous behaviour, is defined by the semantics of that PetriClass’s combination operator.
In the specific case of NatNets, the combination operator formalizes thesimultaneous behaviour as seen in a traditional extended Petri net (as in [Pet77,
Mur89, DR98]): the used tokens and the effects are combined by accumulating
them, the ranges are combined by taking their intersection.
Taking the above quite literally, the following combination operator can beformally written down:((u1 , l1 , h1 ), e1 ) ⊗ ((u2 , l2 , h2 ), e2 ) =(u1 + u2 , max(l1 , l2 ), min(h1 , h2 )), e1 + e2 )Intuitively, this already looks correct, and using only the +, min and max
operators without mixing them guarantees that this operator is both commutative and associative (since each of the operators has those properties), which
are the requirements for the combination operator in PetriClasses.
Since u ≥ −e is already known to be true for both arcs going into the
combination operator, that means u1 + u2 ≥ −(e1 + e2 ), and thus u ≥ −e holds
in the new arc as well.
Some examples of arcs being combined are given in Figures 12 through 15,
with a table of further examples given in Figure 16.
35

((0, 0, ∞), 1)
combines into((0, 0, ∞), 3)((0, 0, ∞), 2)
Figure 12: Combination operator on two arcs that add tokens((1, 1, ∞), −1)
combines into((3, 2, ∞), −3)((2, 2, ∞), −2)
Figure 13: Combination operator on two arcs that remove tokens((1, 1, ∞), −1)
combines into((1, 1, ∞), 0)((0, 0, ∞), 1)
Figure 14: Combination operator on an arc that removes tokens and an arc that
adds tokens((0, 1, 5), 0)
combines into((0, 3, 5), 0)((0, 3, 6), 0)
Figure 15: Combination operator on two arcs that test for specific token counts.
a1((1, 1, ∞), 0)((1, 1, ∞), 0)((0, 5, 6), 0)((5, 5, 6), 0)((0, 5, 6), 8)((0, 5, 6), 0)((100, ∞, ∞), 1)((5, 10, 20), 0)((5, 10, 20), 0)a2((0, 1, ∞), 0)((0, 0, ∞), 1)((0, 2, 3), 0)((2, 2, 3), 0)((0, 2, 3), 3)((0, 0, ∞), 0)((0, 0, ∞), 1)((0, 0, ∞), 5)((2, 0, ∞), 5)

a1 ⊗ a2((1, 1, ∞), 0)((1, 1, ∞), 1)((0, 5, 3), 0)((7, 5, 3), 0)((0, 5, 3), 11)((0, 5, 6), 0)((100, ∞, ∞), 2)((5, 10, 20), 5)((7, 10, 20), 5)

Figure 16: Combination operator examples in table form.
36

(L, ⊗, I) is a commutative monoid
The requirement that (L, ⊗, I) is a commutative monoid is met:
• ⊗ can never bring any two values that are in L to result in a value notin L, since l1 + l2 ≥ −(e1 + e2 ) is true for all values where l1 ≥ −e1 andl2 ≥ −e2 .
• ⊗ is commutative and associative (see the paragraph preceding this one
for details).
• I is the identity for ⊗ since i + 0 = i, max(i, 0) = i and min(i, ∞) = i
within the respective domains where these operators are used.

37

38

7

Properties of NatNets

NatNets are a way to write down existing Petri net classes (extended and nonextended Petri nets as in [Pet77, Mur89, DR98]) in a new generalized manner,combined with a calculation method that works on this notation.
As such, the properties of these nets are quite interesting. So in this section
we will explore some of the properties of Petri nets in this notation, and NatNets
specifically.

7.1

Limitations to the expressive abilities of a single arc

Both Petri nets and NatNets focus on local effects only, meaning markings canonly be affected by transitions and arcs that are connected to their respective
place. This does not actually limit expressive abilities of the net itself, only
the expressive abilities of a single arc. By using multiple arcs and/or multiple
transitions, non-local behaviour can still be expressed indirectly.
Similarly, NatNets have a few restrictions that limit the expressive abilities
of a single transition, while not limiting the expressive abilities of the net itself:• The effect of an arc deals with a known static (non-variable) amount oftokens (thus reset or set arcs are not possible). This can be replaced bya construction that adds or removes tokens combined with an arc thatchecks for a specific range.
• Ranges may not have “gaps” or consist of multiple non-contiguous ranges.
This can be accomplished by using multiple transitions, one for each contiguous section of the wanted non-contiguous range.
That first limitation is only there to keep NatNets straightforward and simple. It is quite possible to extend NatNets with reset and set arcs, and this isactually done later in section 8.
The second limitation is purely to keep arc labels readable, as allowing noncontiguous ranges would make them very hard to note down while not increasing
the computational power of NatNets.

7.2

Arc label subtypes

In subsection 4.2 we already introduced the four main arc label types. Now
that we have domains for the range and effect, we can extend these types with
subtypes.
A full list in table form of all arc label subtypes is shown in Figure 17.
Since the range in a NatNet is a 3-tuple (u, l, h), this gives us eight possibilities for check arc label subtypes (which have a range but no effect), following
the original reasoning from subsection 4.2: used tokens or not, lower bound ornot, upper bound or not. That is 23 = 8 combinations.
However, the case where there is no used token amount, no lower bound andno upper bound is not a range arc label (but rather an identity arc label) and39

the option where there is a used token count but no lower bound effectively does
have a lower bound because of the used token count. This leaves six subtypes
for check arc labels:• Lower-bounded check arc labels: ((0, l, ∞), 0) with l > 0
These arc labels do not use tokens, but do have a lower bound on theactivating token range. These arc labels are analogous to activator arcs inextended Petri nets.
• Upper-bounded check arc labels: ((0, 0, h), 0) with h < ∞These arc labels do not use tokens, but do have an upper bound on theactivating token range. These arc labels are analogous to inhibitor arcs inextended Petri nets as described in [Pet77].
• Range arcs ((0, l, h), 0) with 0 < l ≤ h < ∞These arc labels do not use tokens, but do have both an upper boundas well as a lower bound on the activating token range. These arc labels
represent the combination of an activator arc and an inhibitor arc, andthis combination has already been described as a range in [KK10].
• Lower-bounded self-loops (((u, l, ∞), 0) with u > 0 and l > 0), upperbounded self-loops (((u, 0, h), 0) with u > 0 and h < ∞), and range selfloops (((u, l, h), 0) with u > 0 and l > u and h < ∞).
These arc labels are a form of self-loop: an equal amount of tokens goes inand goes out, giving a net effect of zero. They can have a lower bound fortheir activating token range, and may or may not have an upper boundfor their activating token range. As such, there can be lower-bounded selfloops, upper-bounded self-loops and range self-loops.
Radical arc labels (which have effect, but no range) can be divided into
source arc labels (((0, 0, ∞), e) with e > 0) and sink arc labels (((0, 0, ∞), e)
with e < 0). Since removing tokens unconditionally can lead to a negative
amount of tokens, sink arc labels may not appear in NatNets. This is enforcedby the u ≤ −e requirement on L.
Conditional arc labels can be broadly split into two main categories, one
based on arc labels with positive effect and one based on arc labels with negative
effect. Within these one can further classify the various check arc label types,
but it more interesting to base the classification on the amount of tokens being
used, since this tells us more about what the contextual effect of an arc label
really is. This leads to the following conditional arc types:• Amplification arc labels (((u, l, h), e) with u > 0 and e > 0)
These arc labels use tokens to add tokens to a place, thus amplifying thetoken count.
40

Major type
Identity

Check

RadicalConditional

Subclass—–
Lower-bounded
Upper-boundedRange
L-bounded self-loop
U-bounded self-loop
Ranged self-loop
Sink
SourceAmplification
Bootstrap
Clearing
Dampening
Negating

Range(0, 0, ∞)(0, l, ∞), l > 0(0, 0, h), h < ∞(0, l, h), l > 0, h < ∞(u, l, ∞), u > 0, l > 0(u, 0, h), h < ∞, u > 0(u, l, h), u < 0, l > 0, h < ∞(0, 0, ∞)(u, l, h), u > 0(0, 0, h), h < ∞(−e, −e, −e)(u, l, h), u ≥ −e(u, l, h), u < −eEffect
0

0

<0
e>0
>0
>0
<0
<0
<0

Figure 17: A full list of all theoretically possible arc label types in NatNets. The
sink and negating arc label types are not allowed in NatNets, but included forcompleteness.
• Bootstrap arc labels (((u, l, h), e) with u = 0 and e > 0)
These arc labels add tokens to a place without using tokens, thus bootstrapping the token count.
• Clearing arc labels (((u, l, h), e) with u = l = h = −e and e < 0)
These arc labels decrease the token count to exactly zero.
• Dampening arc labels (((u, l, h), e) with u ≥ −e and e < 0)
These arc labels decrease the token count by a set amount.
• Negating arc labels (((u, l, h), e) with u < −e and e < 0)
These arc labels can decrease the token count to below zero. This arc label
type is not allowed in NatNets because it violates the u ≥ −e requirement
on arc labels.

41

42

8

PetriCalc: Implementation in code

In order to to show the ability to do fast calculations of the model that ispresented in this paper, a practical implementation has been written in C++ thatwas named PetriCalc. PetriCalc is a NatNet calculation tool that simulates
running NatNets, following the ideas from this paper as closely as possible.
If reading this paper in digital PDF format, the full source code to the latest
version of PetriCalc at time of writing should be attached as a PDF attachment. Alternatively, the latest version can be obtained at https://github.com/
Thulinma/PetriCalc. Some of the most interesting parts will be highlighted in
the rest of this section, but having a copy of the full source available makes it
easier to follow along.

Converting (extended) Petri nets as used in the Snoopy
tool
In order to facilitate input (PetriCalc does purely simulation and nothing else
— there is no interface whatsoever), PetriCalc reads Snoopy ( [HHL+ 12])XML files containing Snoopy-style extended Petri nets (.spept file extension)or Snoopy-style Petri nets (.spped file extension). These files are converted toa NatNet in-memory during load.
The Snoopy tool ( [HHL+ 12]) defines five arc types for extended Petri nets.
By converting these arc types into NatNet arcs, we can translate any Snoopycreated extended Petri net into a NatNet as described in the earlier sections.
This is a description of the behaviour of the arc types available in Snoopy andhow to write them as natural net arcs:• An “edge” will either increase or decrease the marking of a place, where
possible. With weight x these can be labelled either ((0, 0, ∞), x) (whencoming out of a transition) or ((x, 0, ∞), −x) (when going into a transition).
• A “read edge” does not consume or produce any tokens and may only
fire if the tokens that would have been consumed otherwise are available.
With weight x these can be labelled as ((0, x, ∞), 0).
• An “inhibitor edge” does not consume or produce any tokens and may
only fire if the tokens that would have been consumed otherwise are notavailable. With weight x these can be labelled as ((0, 0, x − 1), 0).
• An “equal edge” does not consume or produce any tokens and may only
fire if there are exactly its weight in tokens available in the connected
place. With weight x these can be labelled as ((0, x, x), 0).
• A “reset edge”, when fired will consume all available tokens instead of theamount indicated by its weight. These cannot be modelled within NatNets,
so we have extended NatNets to allow for reset arcs.
43

In order to extend NatNets to allow reset arcs to be used, De had to bechanged from Z to a tuple (e, a) where e ∈ ZS and a ∈ N. Here ZS is Z extended
with Si where i ∈ Z, with the S-version of any number being a “setter”. To
calculate addition for ZS the rules n+Si = S(n+i), Si+n = S(i+n), Si+Sn =S(i + n) apply, where n, i ∈ Z.
The effect and range functions do not need to be changed and can be usedas-is. The combination operator requires a change though:⊗(((u1 , l1 , h1 ), (e1 , a1 )), ((u2 , l2 , h2 ), (e2 , a2 ))) =((u1 + u2 , max(l1 , l2 ), min(h1 , h2 )),(if e1 + e2 ∈/ Z then max(S0, a1 ) + max(S0, a2 )) else e1 + e2 ,max(0, a1 ) + max(0, a2 )))The reason we need the extra effect value is to keep track of the sum of all
positive effects so far. When a reset arc is used, we need to change this into a
set-arc to the value of the sum of all positive effects. Since the normal effectonly keeps track of the total effect as opposed to all changes, we need an extra
value that keeps track of the positive changes only. The S symbol is used torepresent set-arcs and their behaviour.
The code used to load Snoopy arcs into this NatNet-based representation is
the following:
1
2
3

4

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// / \ b r i e f Adds a s i n g l e a r c t o t h e net , from a Snoopy XML ←file .
// /// / This f u n c t i o n combines a r c l a b e l s u s i n g t h e c o m b i n a t i o n ←o p e r a t o r i f an a r c between t h e same p l a c e and t r a n s i t i o n ←already e x i s t s .
// / The r e s u l t o f t h i s i s t h a t a r c l a b e l s n e v e r need be ←combined l a t e r , a s they have been combined r i g h t h e r e ←during net load already .
void PetriNet : : addEdge ( TiXmlNode ∗ N , unsigned int E ) {TiXmlElement ∗ e ;e = N−>ToElement ( ) ;const char ∗ id = e−>Attribute ( " id " ) ;if ( ! id ) { return ; }unsigned long long SOURCE = atoi ( e−>Attribute ( " source " ) ) ;unsigned long long TARGET = atoi ( e−>Attribute ( " target " ) ) ;unsigned long long transition ;unsigned long long place ;long long multiplicity = 1 ;if ( transitions . count ( SOURCE ) ) {transition = SOURCE ;place = TARGET ;}if ( places . count ( SOURCE ) ) {transition = TARGET ;place = SOURCE ;

44

22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

}
TiXmlNode ∗ c = 0 ;while ( ( c = N−>IterateChildren ( c ) ) ) {e = c−>ToElement ( ) ;if ( ! e ) { continue ; }if ( ! e−>Attribute ( " name " ) ) { continue ; }std : : string name = e−>Attribute ( " name " ) ;if ( name == " Multiplicity " ) {multiplicity = atoi ( e−>GetText ( ) ) ;}}// I f t h e p l a c e i s t h e s o u r c e , e v e r y t h i n g i s n e g a t i v e
if ( place == SOURCE ) {multiplicity ∗= −1;}
unsigned long long aRLow , aRHigh , aRUsed ;long long aEffect ;bool aEffectSetter = false ;if ( E == EDGE_NORMAL ) {if ( multiplicity < 0 ) {aRLow = −multiplicity ;} else {aRLow = 0 ;}aRUsed = aRLow ;aRHigh = INFTY ;aEffect = multiplicity ;}if ( E == EDGE_ACTIVATOR ) {if ( multiplicity < 0 ) {aRLow = −multiplicity ;} else {aRLow = multiplicity ;}aRUsed = 0 ;aRHigh = INFTY ;aEffect = 0 ;}if ( E == EDGE_INHIBITOR ) {if ( multiplicity < 0 ) {aRHigh = −multiplicity − 1 ;} else {aRHigh = multiplicity − 1 ;}aRUsed = 0 ;aRLow = 0 ;aEffect = 0 ;45

}if ( E == EDGE_EQUAL ) {if ( multiplicity < 0 ) {aRLow = −multiplicity ;aRHigh = −multiplicity ;} else {aRLow = multiplicity ;aRHigh = multiplicity ;}aRUsed = 0 ;aEffect = 0 ;}if ( E == EDGE_RESET ) {aRLow = 0 ;aRUsed = 0 ;aRHigh = INFTY ;aEffect = 0 ;aEffectSetter = true ;
}

72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

if ( arcs . count ( transition ) && arcs [ transition ] . count ( place←) ){#if DEBUG >= 9
std : : cerr << " Combining arc " << transitions [ transition ] ←<< " <->" << places [ place ] << ": " ;#endifarcs [ transition ] [ place ] . combine ( PetriArc ( aRUsed , aRLow , ←aRHigh , aEffect , aEffectSetter ) ) ;} else {arcs [ transition ] [ place ] = PetriArc ( aRUsed , aRLow , aRHigh ←, aEffect , aEffectSetter ) ;#if DEBUG >= 10
std : : cerr << " Inserting arc " << transitions [ transition ] ←<< " <->" << places [ place ] << ": " << arcs [ ←transition ] [ place ] . label ( ) << std : : endl ;#endif
}

93
94
95
96
97
98
99
100

101
102
103

}

It works by looping over all the edges declared in the Snoopy XML file, parsing out the related place, transition and multiplicity as well as edge direction.
Then this information is used together with the type of edge to come up withthe range and effect values for the arc label.
Something particularly interesting happens when an arc between a given
place and transition already exists. The combination operator is used to combine
the arc labels of the existing arc and the new arc together:1arcs [ transition ] [ place ] . combine ( PetriArc ( aRUsed , aRLow , ←aRHigh , aEffect , aEffectSetter ) ) ;46

Since the combination operator is used to combine arc labels together thatconnect the same place and transition before either the effect function or therange function is used on any arc, no information or functionality is lost if we
do this ahead of time. It also results in a nice speed-up, as we no longer have todo this combining at run time.
The combination operator as given earlier in this section is translated almost
literally to code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// / \ b r i e f The c o m b i n a t i o n o p e r a t o r .
// /// / When c a l l e d , t h i s P e t r i A r c and g i v e n P e t r i A r c a r e ←combined i n t o t h i s P e t r i A r c ( i r r e v e r s i b l y ) .
void PetriArc : : combine ( PetriArc param ) {// S e t u t o t h e sum o f u1 and u2
rangeUsed += param . rangeUsed ;// S e t l t o t h e maximum o f l 1 and l 2
if ( param . rangeLow > rangeLow ) { rangeLow = param . rangeLow ; }// S e t h t o t h e minimum o f h1 and h2
if ( param . rangeHigh < rangeHigh ) { rangeHigh = param . ←rangeHigh ; }// S e t a t o t h e sum o f a1 and a2
effectAdded += param . effectAdded ;// I f e i t h e r i s a s e t t e r −arc , e i s t h e new a . Otherwise , i t ←i s e1+e2 .
if ( ! effectSetter && ! param . effectSetter ) {effect += param . effect ;} else {effectSetter = true ;effect = effectAdded ;}}Similarly, the code contains nearly verbatim copies of the range and effectfunctions from Definition 8.
true if l ≤ m ≤ h
The range fuction fr ((l, h), m) =:false otherwise
12
3bool PetriArc : : rangeFunction ( unsigned long long m ) {return ( rangeLow <= m && m <= rangeHigh && rangeUsed <= m ) ←;}And the effect function fe (e, m) = e + m:
1
2
3
4

void PetriArc : : effectFunction ( unsigned long long & m ) {if ( effectSetter ) {m = effect ;} else {

47

5
6
7

m += effect ;}}To then do single steps on this in-memory NatNet, again a nearly verbatim
copy of a definition from this paper is used. In this case, the steps from Algorithm
1:
1
2

3
4
5
6
7
8

if ( stepMode == SINGLE_STEP ) {// Every t r a n s i t i o n i s c he ck ed f o r e n a b l e d n e s s , and made ←p a r t o f a s u b s e t c o n s i s t i n g o f o n l y e n a b l e d ←transitions .
for ( T = arcs . begin ( ) ; T != arcs . end ( ) ; T++){if ( isEnabled ( T−>first ) ) { enabled . insert ( T−>first ) ; }}#if DEBUG >= 5
fprintf ( stderr , " Single - stepping : %u transitions enabled←\n" , ( unsigned int ) enabled . size ( ) ) ;#endif// Nothing e n a b l e d ? We a r e done . Cancel r u n n i n g n e t .
if ( enabled . size ( ) == 0 ) { return false ; }// p i c k a random e n a b l e d t r a n s i t i o nselector = enabled . begin ( ) ;std : : advance ( selector , rand ( ) % enabled . size ( ) ) ;#if DEBUG >= 4
fprintf ( stderr , " Single - stepping : picked transition %s\n←" , transitions [ ∗ selector ] . c_str ( ) ) ;#endif//Run t h e e f f e c t f u n c t i o n on each a r c o f t h e c h o s e n ←transition .
//We do not c a l c u l a t e t h e pt−combined a r c l a b e l here , ←s i n c e i t has been pre−c a l c u l a t e d d u r i n g n e t l o a d ←a l r e a d y f o r each t r a n s i t i o n
std : : map<unsigned long long , PetriArc> & selected = arcs←[ ∗ selector ] ;for ( A = selected . begin ( ) ; A != selected . end ( ) ; A++){A−>second . effectFunction ( marking [ A−>first ] ) ;}// Step completed .
return true ;

9
10
11
12
13
14
15
16
17
18
19

20
21
22
23
24
25
26

}

Maximal auto-concurrent stepping has also been implemented, following Algorithm 8:
12

if ( stepMode == MAX_AUTOCON_STEP ) {// Every t r a n s i t i o n i s c he ck ed f o r e n a b l e d n e s s , and made ←p a r t o f a s u b s e t c o n s i s t i n g o f o n l y e n a b l e d ←-

48

3
4
5
6
7
8

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

transitions .
for ( T = arcs . begin ( ) ; T != arcs . end ( ) ; T++){if ( isEnabled ( T−>first ) ) { enabled . insert ( T−>first ) ; }}#if DEBUG >= 5
fprintf ( stderr , " Maximal auto - concurrent stepping : %u ←transitions enabled \n" , ( unsigned int ) enabled . size ( ) ←);#endif// Nothing e n a b l e d ? We a r e done . Cancel r u n n i n g n e t .
if ( enabled . size ( ) == 0 ) { return false ; }// p r e p a r e empty l i s t o f c h o s e n t r a n s i t i o n s and empty ←PetriSuperTrans
std : : map<unsigned long long , unsigned long long> ←chosenTrans ;PetriSuperTrans super ;// p i c k a random e n a b l e d t r a n s i t i o nselector = enabled . begin ( ) ;std : : advance ( selector , rand ( ) % enabled . size ( ) ) ;chosenTrans [ ∗ selector ]++; // i n c r e m e n t c h o s e n t r a n s i t i o n ←countersuper . combine ( arcs [ ∗ selector ] ) ; // combine t h e c h o s e n ←t r a n s i t i o n i n t o the PetriSuperTrans// keep g o i n g u n t i l no e n a b l e d t r a n s i t i o n s a r e l e f t t o ←add
while ( enabled . size ( ) ) {// p i c k a random e n a b l e d t r a n s i t i o nselector = enabled . begin ( ) ;std : : advance ( selector , rand ( ) % enabled . size ( ) ) ;// would s u p e r s t i l l be e n a b l e d i f t h i s t r a n s i t i o n was ←added ?
if ( super . isCombinedEnabled ( arcs [ ∗ selector ] , marking ) ) ←{// i f so , add i tchosenTrans [ ∗ selector ]++; // i n c r e m e n t c h o s e n ←t r a n s i t i o n countersuper . combine ( arcs [ ∗ selector ] ) ; // combine t h e c h o s e n ←t r a n s i t i o n i n t o the PetriSuperTrans} else {// i f not , remove i t from t h e l i s t o f e n a b l e d ←transitions
enabled . erase ( selector ) ;}}#if DEBUG >= 449

std : : cerr << " Maximal auto - concurrent stepping : picked ←transitions :" ;std : : map<unsigned long long , unsigned long long > : : ←iterator pckd ;for ( pckd = chosenTrans . begin ( ) ; pckd != chosenTrans . end←( ) ; pckd++){std : : cerr << " " << transitions [ pckd−>first ] ;if ( pckd−>second > 1 ) {std : : cerr << " (X" << pckd−>second << ")" ;}}std : : cerr << std : : endl ;#endif//Run t h e e f f e c t f u n c t i o n on each a r c o f s u p e r .
std : : map<unsigned long long , PetriArc> & selected = ←super . myArcs ;for ( A = selected . begin ( ) ; A != selected . end ( ) ; A++){A−>second . effectFunction ( marking [ A−>first ] ) ;}// Step completed .
return true ;

40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

}

For completeness, here is the isEnabled function as used above as well. It’sa near verbatim copy of Definition 5:
1
2
3
4
5
6
7
8
9
10
11

bool PetriNet : : isEnabled ( unsigned int T ) {//We c o n s i d e r t r a n s i t i o n s w i t h o u t a r c s t o not be enabled , ←s i n c e t h a t i s t h e o n l y t h i n g t h a t makes s e n s e .
if ( ! arcs [ T ] . size ( ) ) {return false ;}// Loop o v e r a l l p i n P such t h a t p c o n n e c t e d t o t
std : : map<unsigned long long , PetriArc > : : iterator A ;for ( A = arcs [ T ] . begin ( ) ; A != arcs [ T ] . end ( ) ; A++){// Check fR (aR , M( p ) ) , i f f a l s e , r e t u r n f a l s e//We do not c a l c u l a t e t h e pt−combined a r c l a b e l here , ←s i n c e i t has been pre−c a l c u l a t e d d u r i n g n e t l o a d ←a l r e a d y f o r each t r a n s i t i o n
if ( ! A−>second . rangeFunction ( marking [ A−>first ] ) ) { return ←false ; }
}

12
13
14
15
16
17

// o n l y i f a l l fR (aR , M ( p ) ) a r e t r u e , r e t u r n t r u e
return true ;
}

50

9

Discussion and conclusion

The straightforwardness of the implementation as shown in Section 8 showsthat NatNets are a good notation to use for Petri net simulations. During thewriting and testing of the implementation, it became clear that the combination
operator of NatNets can also be used to simplify and classify collections of arcs
into more generic behaviours, which could assist the interpretation of (larger ormore complex) Petri nets by human eyes.
The extension to make NatNets compatible with reset arcs (and, as a result,
set arcs in general) only required minor changes, showing the extensibility ofthe method as well as producing the tool PetriCalc. PetriCalc was used in[BKH+ 15] to do calculations on nets with literally millions of tokens movingaround, as a means to experimentally verify theoretical models. Existing tools
at the time required days to weeks to complete those calculations only partially,
where PetriCalc needed only hours to reach end results. This not only showsthat PetriCalc (and the theory it is based on) has practical uses but also that
it is significantly more efficient than existing tools that do Petri net simulation/ animation.
However, [BKH+ 15] did not use PetriCalc in its current iteration. Boththe theory from this paper as well as the practical implementation in the formof PetriCalc went through iterative changes over a period of several years.
The calculations done using the earlier iteration were validated against the latest version of the theory and tool, and the results were identical. This is very
good, because the earlier version of PetriCalc wasn’t fully compatible with all
extended nets as produced by the Snoopy tool and this latest version is. So,
for nets that were compatible with the older version, the results were indeed
expected to be identical.
Further work could still be done, both on the theory and PetriCalc:
It is not clear why PetriCalc is so much more efficient than existing tools,
as it is hard to know what calculation methods those tools use and thus it is acomplicated task to compare these. This could be an area of further research.
Supporting coloured Petri nets would be a sensible next step, but creating
PetriClasses for timed Petri nets, stochastic Petri nets and continuous/hybrid
Petri nets would also be very interesting as they all have their own particularsemantics and challenges. The most readily visible class of net that could bemade to fit a PetriClass is perhaps coloured Petri nets. In stead of NatNets
scalars, here markings, ranges and effects could be represented by matrices ofscalars, for example.
Besides simply supporting more classes of nets, the algorithms could also
be improved upon. A great speed-up is possible when it is known in advancethat a net is deterministic, for example (as there is no need to check furthertransitions after finding the first enabled transition). More speed still could be
gained in auto-concurrent maximal stepping mode, as a single transition can
instantly be added as many times as it possibly could be without needing toworry about possible conflicts with other transitions. First experiments with51

this method have shown an increase in simulation speed that is incrementallyhigher as token counts go up.
PetriCalc only has implementations for single steps and for maximal autoconcurrent steps, implementing (maximal) concurrent steps as well as nonmaximal auto-concurrent steps are also good candidates for further work. The
algorithms for these have already been outlined in this paper, but a practicalimplementation is still lacking.
A visualizer that simplifies a net to no more than one arc per place/transition
combination and then highlights them depending on their arc label type could
also be a very interesting analysis tool based on the work in this paper. The
various arc types would make the effects of firing arcs immediately visible andthus much easier to analyse by human eye.
Finally, Snoopy is by far not the only Petri net tool out there, and PetriCalc
could benefit from being able to read nets created by other tools as well.

52

References[BKH+ 15]Laura M. F. Bertens, Jetty Kleijn, Sander C. Hille, Monika Heiner,
Maciej Koutny, and Fons J. Verbeek. Modeling biological gradientformation: combining partial differential equations and petri nets.
Natural Computing, pages 1–11, 2015.

[BM97]

Roberto Bruni and Ugo Montanari. Zero-safe nets, or transition
synchronization made simple. Electr. Notes Theor. Comput. Sci.,
7:55–74, 1997.

[BM00a]Roberto Bruni and Ugo Montanari. Executing transactions in zerosafe nets. In ICATPN, pages 83–102, 2000.

[BM00b]Roberto Bruni and Ugo Montanari. Zero-safe nets: Comparing thecollective and individual token approaches. Inf. Comput., 156(12):46–89, 2000.

[BM01]

Roberto Bruni and Ugo Montanari. Transactions and zero-safe
nets. In Hartmut Ehrig, Gabriel Juhás, Julia Padberg, and Grzegorz Rozenberg, editors, Unifying Petri Nets, Advances in PetriNets, volume 2128 of Lecture Notes in Computer Science, pages
380–426. Springer, 2001.

[Bur83]

Hans-Dieter Burhard. On priorities of parallelism: Petri nets underthe maximum firing strategy. In A. Salwicki, editor, Logics ofPrograms and Their Applications, volume 148 of Lecture Notes in
Computer Science, pages 86–97. Springer Berlin Heidelberg, 1983.

[DKPY08]

Philippe Darondeau, Maciej Koutny, Marta Pietkiewicz-Koutny,
and Alexandre Yakovlev. Synthesis of nets with step firing policies. In Kees M. van Hee and Rüdiger Valk, editors, Applications
and Theory of Petri Nets, 29th International Conference, PETRINETS 2008, Xi’an, China, June 23-27, 2008. Proceedings, volume 5062 of Lecture Notes in Computer Science, pages 112–131.
Springer, 2008.

[DMM96]

Pierpaolo Degano, José Meseguer, and Ugo Montanari. Axiomatizing the algebra of net computations and processes. Acta Inf.,
33(7):641–667, 1996.

[DR98]

Jörg Desel and Wolfgang Reisig. Place/transition Petri Nets. In
Wolfgang Reisig and Grzegorz Rozenberg, editors, Lectures on
Petri Nets I: Basic Models: Advances in Petri Nets, volume 1491
of Lecture Notes in Computer Science, pages 122–173. Springer,
Berlin / Heidelberg, June 1998.

[HHL+ 12]

Monika Heiner, Mostafa Herajy, Fei Liu, Christian Rohr, and Martin Schwarick. Snoopy a unifying petri net tool. In Serge Haddad
53

and Lucia Pomello, editors, Application and Theory of Petri Nets,
volume 7347 of Lecture Notes in Computer Science, pages 398–407.
Springer Berlin Heidelberg, 2012.
[HMR05]

Thomas A. Henzinger, Rupak Majumdar, and Jean-François
Raskin. A classification of symbolic transition systems. ACM
Trans. Comput. Log., 6(1):1–32, 2005.

[KK10]

Jetty Kleijn and Maciej Koutny. Petri nets with localities andtesting. In Johan Lilius and Wojciech Penczek, editors, Applications and Theory of Petri Nets, 31st International Conference,
PETRI NETS 2010, Braga, Portugal, June 21-25, 2010. Proceedings, volume 6128 of Lecture Notes in Computer Science, pages
19–38. Springer, 2010.

[KKPKR12] Jetty Kleijn, Maciej Koutny, Marta Pietkiewicz-Koutny, and Grzegorz Rozenberg. Step semantics of boolean nets. Acta Informatica,
50(1):15–39, 2012.
[MM90]

Jos Meseguer and Ugo Montanari. Petri nets are monoids. Information and Computation, 88(2):105 – 155, 1990.

[Mur89]T. Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4):541–580, Apr 1989.

[Pet77]

James L. Peterson. Petri nets. ACM Computing Surveys, 9:223–
252, 1977.

54