Vol-3170/paper5
Jump to navigation
Jump to search
Paper
| Paper | |
|---|---|
 edit
| |
| description | |
| id | Vol-3170/paper5 |
| wikidataid | Q117351490βQ117351490 |
| title | Analysing Adaption Processes of Hornets |
| pdfUrl | https://ceur-ws.org/Vol-3170/paper5.pdf |
| dblpUrl | https://dblp.org/rec/conf/apn/Kohler-Bussmeier22 |
| volume | Vol-3170βVol-3170 |
| session | β |
Analysing Adaption Processes of Hornets
Analysing Adaption Processes of Hornets
Michael KΓΆhler-Bussmeier1 , Heiko RΓΆlke2
1
University of Applied Science Hamburg, Berliner Tor 7, D-20099 Hamburg
2
FH GraubΓΌnden, PulvermΓΌhlestrasse 57, CH-7000 Chur
Abstract
In this paper we study the dynamics of self-adapting systems. Our main objective is to compare adaption
dynamics of similar systems, i.e. systems that differ only in their organisational networks. We specify
adaption in the formalisms of Hornets β a formalism that uses nets as tokens, i.e. they follow the
nets-within-nets approach. We identify different abstractions of the reachability graph that focus on the
adaption aspects of the processes. We develop key measures for adaption processes on these abstracted
graphs. The key measures are used e.g. to compare two variations of the same adapting system. The ap-
proach is illustrated by a case study: We analyse a Hornet-model of Axelrodβs well-known tournament
where the playing agents adapt their strategies during the game.
Keywords
Adaption, Hornets, nets-within-nets, key measures, organisational networks
1. Introduction: The Dynamics of Adaption Processes
In general the evolution (i.e. adaption) of a system is determined by the interaction aspect of
adaptivity, i.e. how adaption is performed (e.g. via a cross-over of genes) and how the gene pool
looks like (the βhowβ). But, on the other hand it is relevant which objects have the possibility
to interact: Is there a opportunity for each pair of genes to meet and perform a cross-over in
the system β or are they too separated? This aspect relates to the network aspect of adaptivity
(the βwhoβ). A companyβs workflow management system constitutes an example: The set of
workflows is the gene pool, while the evolution of the workflows during the companyβs lifetime
strongly relates to the organisational network.
In this paper we like to study adaption processes where the network part plays a significant
role which cannot be ignored. We like to study these adaption processes, i.e. the trajectories
of the gene pool, in the setting of discrete event system, namely in the formal framework of
Hornets [1] as this formalism has been developed to study adaptive systems. In the context
of Hornets these two aspects β how and whom β are naturally addressed: Hornets are Petri
nets where the tokens are Petri nets again. The surrounding net is called system net and the
net-tokens are called object nets. The object nets model the adapting objects β as they define
what can happen; and the system net models the network part together with the adaption logic
PNSEβ22, International Workshop on Petri Nets and Software Engineering, Bergen, Norway, 2022
" michael.koehler-bussmeier@haw-hamburg.de (M. KΓΆhler-Bussmeier); heiko.roelke@fhgr.ch (H. RΓΆlke)
~ https://www.haw-hamburg.de/michael-koehler-bussmeier (M. KΓΆhler-Bussmeier);
https://www.fhgr.ch/personen/person/roelke/ (H. RΓΆlke)
οΏ½ 0000-0002-3074-4145 (M. KΓΆhler-Bussmeier)
Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org)
80
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
itself β as the system net defines which object nets are involved and how adaption looks like. In
the example of a workflow management system the object nets describe the set of workflows
and the net-tokens are the workflow instances while the system net models the whole adaption
process of workflows.
A state π of a Hornet is a nested multiset, where a place πΜοΈπ of the system net is marked with
net-tokens of the form [ππ , ππ ]; the topology of a net-token is defined by the object net ππ and
each net-token has its own marking ππ :
system net net-token
π
βοΈ β β β β
π= πΜοΈπ [ ππ , ππ ]
β β β β
π=1 object net ON marking
For Hornets the gene pool of this state π is given as the set of object nets, i.e. the set of possible
net-token types: {π1 , . . . , ππ }. We are interested in the dynamics of this set. More specifically,
our main objective is to compare adaption dynamics of similar systems. For the example of
a workflow management system we like to compare two companies with the same initial set
of workflows but with different organisational networks, i.e. we like to study the impact of
the network on the adaption dynamics. We like to develop key values for these dynamics to
answer questions like: βWhich company adapts faster?β, βWhich company develops a gene pool
of greater diversity?β etc.
The paper has the following structure: Section 2 recalls the definition of Hornets and
eHornets. The main purpose is to recall the defininition of the reachability graph of Hornets.
It can be skipped on first reading. The main contribution is given in Section 3, which describes
how adaption process can be studied in the formal framework of Hornets. We will derive a
structure describing the core adaption processes as an abstraction of the reachability graph of a
given Hornet. The dynamics of the gene pool is somehow in between two other dynamics: on
the one hand, it is much coarser than the dynamics of the whole Hornet as it abstracts from
the internal actions of the net-tokens; on the other hand is much finer than the dynamics of the
system net alone when considered as a normal p/t net. Different key values will be considered
to capture essential aspect of the adaption dynamics. In Section 4 we exemplify the theoretical
framework with a generalisation of Axelrodβs well-known tournament. The tournament is a
well-known example for adaption, especially in the context of genetic algorithms [2]. Here, we
study the impact of differences in the agentsβ neighbourhood for the adaption dynamics: We
compare the dynamics on a ErdΕs-RΓ©nyi graph [30] to that on a Watts-Strogatz graph [31]. The
work ends with a conclusion and an outlook.
2. Hornets and Object Nets
We have defined Hornets in [1] as a generalisation of our object nets [3, 4], which follow the
nets-within-nets paradigm as proposed by Valk [5]. Approaches adapting the nets-within-nets
approach are nested nets [6], mobile predicate/transition nets [7], Reference nets [8], PN2 [9],
hypernets [10], Mobile Systems [11], and adaptive workflow nets [12]. Object Nets can be seen
as the Petri net perspective on contextual change, in contrast to the Ambient Calculus [13] or
the π-calculus [14].
81
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
Figure 1: An Elementary Object Net System (Eos)
With object nets we study Petri nets where the tokens are nets again, i.e. we have a nested
marking. Events are also nested. We have three different kinds of events β as illustrated by the
example given in Figure 1:
1. System-autonomous: The system net transition ΜοΈ π‘ fires autonomously, which moves the
net-token from πΜοΈ1 to πΜοΈ2 without changing its marking.
2. Object autonomous: The object net fires transition π‘1 βmovingβ the black token from π1
to π2 . The object net remains at its location πΜοΈ1 .
3. Synchronisation: Whenever we add matching synchronisation inscriptions at the system
net transition ΜοΈ
π‘ and the object net transition π‘1 , then both must fire synchronously: The
object net is moved to πΜοΈ2 and the black token moves from π1 to π2 inside. Whenever
synchronisation is specified, autonomous actions are forbidden.
For Hornets we extend object nets with algebraic concepts that allow to modify the structure
of the net-tokens as a result of a firing transition. This is a generalisation of the approach of
algebraic nets [15], where algebraic data types replace the anonymous black tokens.
Example We consider a Hornet with two workflow nets π1 and π2 as tokens β cf. Figure 2.
To model a run-time adaption, we combine π1 and π2 resulting in the net π3 = (π1 βπ2 ). This
modification is modelled by transition π‘ of the Hornets in Fig. 2. In a binding πΌ with π₯ β¦β π1
and π¦ β¦β π2 the transition π‘ is enabled. Assume that (π₯βπ¦) evaluates to π3 for πΌ. If π‘ fires it
removes the two net-tokens from π and π and generates one new net-token on place π. The
net-token on π has the structure of π3 and its marking is obtained as a transfer from the token
on π£ in π1 and the token on π in π2 into π3 . This transfer is possible since all the places of π1
and π2 are also places in π3 and tokens can be transferred in the obvious way. c
N2 π π π net-token produced on π by π‘
i2- π - i
r - π - i2
π-
h π’ - h π£ - hπ1
ZZ
} N3 1
π- h - π r- π
q
Zls Hπ¦ hπ-
3 οΏ½ π3
R - h
@
r
- l
j (π₯βπ¦)
H
Rh π2 - π ποΏ½
π - rh - π - h
pοΏ½ t @ 2
s οΏ½π₯β
l
οΏ½
βοΏ½
οΏ½
N1 π1 π’ π£ π
i - π - i - π - ri - π - i1
Figure 2: Modification of the net-tokenβs structure
It is not hard to prove that the general Hornet formalism is Turing-complete. In [1] we have
proven that there are several possibilities to simulate counter programs: One could use the
82
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
nesting to encode counters. Another possibility is to encode counters in the algebraic structure
of the net operators.
The use of algebraic operations in Hornets relates them to algebraic higher-order (AHO)
systems [16], which are restricted to two-levelled systems but have a greater flexibility for the
operations on net-tokens, since each net transformation is allowed. There is also a relationship to
Nested Nets [17], which are used for adaptive systems, and to distributed graph transformations
[18].
2.1. Adaption: Complexity Issues for eHornets
Let us recall our results on complexity issues of Hornets. We introduced different restrictions
to guarantee that the system has a finite state space: First, we allow at most one token on each
place, which results in the class of safe Hornets. However, this restriction does not guarantee
finite state spaces, since we have the nesting depth as a second source of undecidability [4].
Second, we restrict the universe of object nets to finite sets. Finally, we restrict the nesting depth
and introduce the class of elementary Hornets, which have a two-levelled nesting structure.
This is done in analogy to the class of elementary object net systems (Eos) [3], which are the
two-level specialisation of general object nets [3, 4]. If we rule out these sources of complexity
the remaining origin of complexity is the use of algebraic transformations, which are still
allowed for safe, elementary Hornets β a class defined in analogy to safe Eos [19].
Safe, elementary Hornets have greater complexity when compared to their Eos counterpart:
On the one hand, we have shown in [19, 20, 21] that most problems for safe Eos are PSpace-
complete. More precisely: All problems that are expressible in LTL or CTL, which includes
reachability and liveness, are PSpace-complete. This means that with respect to these problems
safe Eos are no more complex than P/T nets. On the other hand, we have shown in [22] that
safe, elementary Hornets are beyond PSpace: We have shown a lower bound, i.e. that βthe
reachability problem requires exponential spaceβ for safe, elementary Hornets β similarly to
well known result of for bounded P/T nets [23]. In [24] we give an algorithm that needs at most
exponential space, which shows that lower and upper bound coincide.
In [25] we studied further restrictions of Elementary Hornets β among them state machines.
The main result is that the reachability problem is PSpace-complete for this class.
2.2. Formal Definition of Elementary Hornets (eHornets)
In the following we recall the definition of eHornets from [22] which is specialised from the
general formalism of Hornets [1].
Multisets and P/T Nets A multiset m on the set π· βοΈ is a mapping m : π· β N. Multisets can
also be represented as a formal sum in the form m = ππ=1 π₯π , where π₯π β π·.
Multiset addition is defined component-wise: (m1 + m2 )(π) := m1 (π) + m2 (π). The empty
multiset 0 is defined as 0(π) = 0 for all π β π·. Multiset-difference m1 β m2 is defined by
(m1 β m2 )(π) := max(m1 (π) β m2 (π), 0).βοΈ
The cardinality of a multiset is |m| := πβπ· m(π). A multiset m is finite if |m| < β.
The set of all finite multisets over the set π· is denoted MS (π·). The domain of a multiset is
83
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
dom(m) := {π β π· | m(π) > 0}.
Multiset notations are used for sets as well. The meaning will be apparent from its use.
AnyβοΈmapping π :βοΈπ· β π·β² extends to a multiset-homomorphism π β― : MS (π·) β MS (π·β² )
by π ( ππ=1 π₯π ) = ππ=1 π (π₯π ).
β―
A p/t net π is a tuple π = (π, π, pre, post), such that π is a set of places, π is a set of
transitions, with π β© π = β
, and pre, post : π β MS (π ) are the pre- and post-condition
functions. A marking of π is a multiset of places: m β MS (π ). We denote the enabling of π‘ in
π‘ π‘
marking m by m β β . Firing of π‘ is denoted by m β
β mβ² .
Net-Algebras We define the algebraic structure of object nets. For a general introduction of
algebraic specifications cf. [26].
Let πΎ be a set of net-types (kinds). A (many-sorted) specification (Ξ£, π, πΈ) consists of a
signature Ξ£, a family of variables π = (ππ )πβπΎ , and a family of axioms πΈ = (πΈπ )πβπΎ .
A signature is a disjoint family Ξ£ = (Ξ£π1 Β·Β·Β·ππ ,π )π1 ,Β·Β·Β· ,ππ ,πβπΎ of operators. The set of terms of
type π over a signature Ξ£ and variables π is denoted TπΞ£ (π).
We use (many-sorted) predicate logic, where the terms are generated by a signature Ξ£ and
formulae are defined by a family of predicates Ξ¨ = (Ξ¨π )πβN . The set of formulae is denoted
PLΞ , where Ξ = (Ξ£, π, πΈ, Ξ¨) is the logic structure.
Object Nets and Net-Algebras Let Ξ£ be a signature over πΎ. A net-algebra assigns to each
type π β πΎ a set π°π of object nets β the net universe. Each βοΈ object π β π°π , π β πΎ net is a p/t
net π = (ππ , ππ , preπ , postπ ). We identify π° with πβπΎ π°π in the following. We assume
the family π° = (π°π )πβπΎ to be disjoint.
The nodes of the object nets in π°π are not disjoint, since the firing rule allows to transfer
tokens between net tokens within the same set π°π . Such a transfer is possible, if we assume
that all nets π β π°π have the same set of places ππ . ππ is the place universe for all object nets
of kind π. In the example of Fig. 2 the object nets π1 , π2 , and π3 must belong to the same type
since otherwise it would be impossible to transfer the markings in π1 and π2 to the generated
π3 .
In general, ππ is not finite. Since we like each object net to be finite in some sense, we
require that the transitions ππ of each π β π°π use only a finite subset of ππ , i.e. βπ β π° :
|β ππ βͺ ππ β | < β.
The family of object nets π° is the universe of the algebra. A net-algebra (π°, β) assigns to
each constant π β Ξ£π,π an object net π β β π°π and to each operator π β Ξ£π1 Β·Β·Β·ππ ,π with π > 0 a
mapping π β : (π°π1 Γ Β· Β· Β· Γ π°ππ ) β π°π .
A net-algebra is called finite if ππ is a finite set for each π β πΎ.
Since all nets π β π°π have the same set of places ππ , which is required to be finite for
eHornets, there is an upper bound for the cardinality of π°π .
Theorem 1 (Lemma 2.1 in [22]). For each π β πΎ the cardinality of each net universe π°π is
4|ππ |
bound as follows: |π°π | β€ 2(2 ).
84
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
A variable assignment πΌ = (πΌπ : ππ β π°π )πβπΎ maps each variable onto an element of the
algebra. For a variable assignment πΌ the evaluation of a term π‘ β TπΞ£ (π) is uniquely defined
and will be denoted as πΌ(π‘).
A net-algebra, such that all axioms of (Ξ£, π, πΈ) are valid, is called net-theory.
Nested Markings A marking of an eHornet assigns to each system net place one or many
net-tokens. The places of the system net are typed by the function k : πΜοΈ β πΎ, meaning that a
place πΜοΈ contains net-tokens of kind k (ΜοΈ
π). Since the net-tokens are instances of object nets, a
marking is a nested multiset of the form:
π
βοΈ
π= πΜοΈπ [ππ , ππ ] where πΜοΈπ β πΜοΈ, ππ β π°k (πΜοΈπ ) , ππ β MS (πππ ), π β N
π=1
Each addend πΜοΈπ [ππ , ππ ] denotes a net-token on the place πΜοΈπ that has the structure of the object
net ππ and the marking ππ β MS (πππ ). The set of all nested multisets is denoted as β³π» . We
define the partial order β on nested multisets by setting π1 β π2 iff βπ : π2 = π1 + π.
The projection Ξ 1π (π) is the multiset of all system-net places that contain the object net π :
(οΈβοΈπ )οΈ βοΈπ
Ξ 1π πΜοΈπ [ππ , ππ ] := 1π (ππ ) Β· πΜοΈπ (1)
π=1 π=1
where the indicator function 1π is defined as: 1π (ππ ) = 1 iff ππ = π .
Analogously, the projection Ξ 2π (π) is the multiset of all net-tokensβ markings (that belong to
the object net π ): (οΈβοΈπ )οΈ βοΈπ
Ξ 2π πΜοΈπ [ππ , ππ ] := 1π (ππ ) Β· ππ (2)
π=1 π=1
The projection Ξ 2π (π) is the sum of all net-tokensβ markings belonging to the same type
π β πΎ: βοΈ
Ξ 2π (π) := Ξ 2π (π) (3)
π βπ°π
Synchronisation The transitions in an Hornet are labelled with synchronisation inscrip-
tions. We assume a fixed set of channels πΆ = (πΆπ )πβπΎ .
β’ The function family ΜοΈ ππΌπ )πβπΎ defines the synchronisation constraints. Each transition
ππΌ = (ΜοΈ
of the system net is labelled with a multiset ΜοΈ π‘) = (π1 , π1 ) + Β· Β· Β· + (ππ , ππ ), where the
ππ (ΜοΈ
expression ππ β TΞ£ (π) describes the called object net and ππ β πΆπ is a channel. The
π
intention is that ΜοΈ
π‘ fires synchronously with a multiset of object net transitions with the
same multiset of labels. Each variable assignment πΌ generates the function ΜοΈ π‘) defined
ππΌπ (ΜοΈ
as: βοΈ βοΈ
ππΌπ (ΜοΈ
ΜοΈ π‘)(π ) := 1β€πβ€π ππ for ΜοΈ ππ (ΜοΈ
π‘) = (ππ , ππ ) (4)
πΌ(ππ )=π
1β€πβ€π
Each function ΜοΈ π‘) assigns to each object net π a multiset of channels.
ππΌπ (ΜοΈ
β’ For each π β π°π the function ππ assigns to each transition π‘ β ππ either a channel
π β πΆπ or β₯π , whenever π‘ fires without synchronisation, i.e. autonomously.
85
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
System Net Assume we have a fixed logic Ξ = (Ξ£, π, πΈ, Ξ¨) and a net-theory (π°, β). An
elementary higher-order object net (eHornet) is composed of a system net π ΜοΈ and the set of
object nets π°. W.l.o.g. we assume π ΜΈβ π°. To guarantee finite algebras for eHornets, we
ΜοΈ
require that the net-theory (π°, β) is finite, i.e. each place universe ππ is finite.
The system net is a net π ΜοΈ where each arc is labelled with a multiset
ΜοΈ = (πΜοΈ, πΜοΈ, pre, post, πΊ),
of terms: pre, post : πΜοΈ β (πΜοΈ β MS (TΞ£ (π))). Each transition is labelled by a guard
predicate πΊ ΜοΈ : πΜοΈ β PLΞ . The places of the system net are typed by the function k : πΜοΈ β πΎ.
As a typing constraint we have that each arc inscription has to be a multiset of terms that are
all of the kind that is assigned to the arcβs place:
k (ΜοΈ
π)
pre(ΜοΈ
π‘)(ΜοΈ
π), post(ΜοΈ
π‘)(ΜοΈ
π) β MS (TΞ£ (π)) (5)
For each variable binding πΌ we obtain the evaluated functions preπΌ , postπΌ : πΜοΈ β (πΜοΈ β
MS (π°)) in the obvious way.
Definition 1 (Elementary Hornet, eHornet). Assume a fixed many-sorted predicate logic
Ξ = (Ξ£, π, πΈ, Ξ¨).
An elementary Hornet is a tuple EH = (π
ΜοΈ , π°, β, k , π, π0 ) such that:
1. πΜοΈ is an algebraic net, called the system net.
2. (π°, β) is a finite net-theory for the logic Ξ.
3. k : πΜοΈ β πΎ is the typing of the system net places.
4. π = (ΜοΈπ, ππ )π βπ° is the labelling.
5. π0 β β³π» is the initial marking.
Events The synchronisation labelling generates the set of system events Ξ. We have three
kinds of events:
1. Synchronised firing: There is at least one object net that has to be synchronised, i.e. there
is a π such that ΜοΈ π‘)(π ) is not empty.
π(ΜοΈ
Such an event is a pair π = ΜοΈ π‘πΌ [π], where ΜοΈπ‘ is a system net transition, πΌ is a variable
binding, and π is a function that maps each object net to a multiset of its transitions, i.e.
π(π ) β MS (ππ ). It is required that ΜοΈ π‘ and π(π ) have matching multisets of labels, i.e.
β― β―
π(ΜοΈ
ΜοΈ π‘)(π ) = ππ (π(π )) for all π β π°. (Remember that ππ denotes the multiset extension
of ππ .)
The intended meaning is that ΜοΈ π‘ fires synchronously with all the object net transitions
π(π ), π β π°.
2. System-autonomous firing: The transition ΜοΈ π‘ of the system net fires autonomously, when-
ever ΜοΈ π‘) is the empty multiset 0.
π(ΜοΈ
We consider system-autonomous firing as a special case of synchronised firing generated
by the function πid , defined as πid (π ) = 0 for all π β π°.
3. Object autonomous firing: An object net transition π‘ in π fires autonomously, whenever
ππ (π‘) = β₯π .
Object autonomous events are denoted as id π,π ΜοΈ [ππ‘ ], where ππ‘ (π ) = {π‘} if π = π and
β² β²
0 otherwise. The meaning is that in object net π fires π‘ autonomously within the place π. ΜοΈ
86
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
For the sake of uniformity we define for an arbitrary binding πΌ:
{οΈ
β² β² β² β² 1 if πΜοΈβ² = πΜοΈ β§ π β² = π
preπΌ (id π,π )(ΜοΈ
π )(π ) = postπΌ (id π,π )(ΜοΈ
π )(π ) =
0 otherwise.
ΜοΈ ΜοΈ
The set of all events generated by the labelling π is Ξπ := Ξ1 βͺ Ξ2 , where Ξ1 contains
synchronous events (including system-autonomous events as a special case) and Ξ2 contains
the object autonomous events:
{οΈ }οΈ
β―
Ξ1 := πΜοΈπΌ [π] | βπ β π° : ΜοΈππΌ (ΜοΈ
π‘)(π ) = ππ (π(π ))
{οΈ }οΈ (6)
Ξ2 := ΜοΈ [ππ‘ ] | π
id π,π ΜοΈ β π , π β π°k (ΜοΈπ) , π‘ β ππ
ΜοΈ
Firing Rule A system event π = πΜοΈπΌ [π] removes net-tokens together with their individual
internal markings. Firing the event replaces a nested multiset π β β³π» that is part of the
current marking π, i.e. π β π, by the nested multiset π. The enabling condition is expressed by
the enabling predicate πEH (or just π whenever EH is clear from the context):
πEH π πΌ [π], π, π) ββ βπ β πΎ :
(ΜοΈ
π β k β1 (π) : βπ β π°π : Ξ 1π (π)(ΜοΈ
βΜοΈ π) = preπΌ (ΜοΈ π)(π ) β§
π )(ΜοΈ
π β k β1 (π) : βπ β π°π : Ξ 1π (π)(ΜοΈ
βΜοΈ π) = postπΌ (ΜοΈ π)(π ) β§
π )(ΜοΈ (7)
2
βοΈ β―
Ξ π (π) β₯ π βπ°π preπ (π(π )) β§
Ξ 2π (π) = Ξ 2π (π) + π βπ°π postβ―π (π(π )) β preβ―π (π(π ))
βοΈ
The predicate πEH has the following meaning: Conjunct (1) states that the removed sub-
marking π contains on πΜοΈ the right number of net-tokens, that are removed by πΜοΈ. Conjunct (2)
states that generated sub-marking π contains on πΜοΈ the right number of net-tokens, that are
generated by πΜοΈ. Conjunct (3) states that the sub-marking π enables all synchronised transitions
π(π ) in the object π . Conjunct (4) states that the marking of each object net π is changed
according to the firing of the synchronised transitions π(π ).
Note, that conjunct (1) and (2) assures that only net-tokens relevant for the firing are included
in π and π. Conditions (3) and (4) allow for additional tokens in the net-tokens.
For system-autonomous events ΜοΈ π‘πΌ [πid ] the enabling predicate πEH can be simplified further:
Conjunct (3) is always true since preπ (πid (π )) = 0. Conjunct (4) simplifies to Ξ 2π (π) = Ξ 2π (π),
which means that no token of the object nets get lost when a system-autonomous events fires.
Analogously, for an object autonomous event πΜοΈ[ππ‘ ] we have an idle-transition πΜοΈ = id π,π ΜοΈ
and π = ππ‘ for some π‘. Conjunct (1) and (2) simplify to Ξ 1π β² (π) = πΜοΈ = Ξ 1π β² (π) for π β² = π
and to Ξ 1π β² (π) = 0 = Ξ 1π β² (π) otherwise. This means that π = π[π ΜοΈ ], π enables π‘, and
ΜοΈ β preπ (ΜοΈ
π = π[π π‘) + postπ (ΜοΈπ‘)].
Definition 2 (Firing Rule). Let EH be an eHornet and π, πβ² β β³π» markings.
β’ The event πΜοΈπΌ [π] is enabled in π for the mode (π, π) β β³2π» iff π β π β§ πEH (ΜοΈ
π [π], π, π)
holds and the guard πΊ( π‘) holds, i.e. πΈ |=πΌβ πΊ(ΜοΈ
ΜοΈ ΜοΈ ΜοΈ π ).
πΜοΈπΌ [π](π,π)
β’ An event πΜοΈπΌ [π] that is enabled in π can fire β denoted π βββββββ πβ² .
EH
87
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
β’ The resulting successor marking is defined as πβ² = π β π + π.
Note, that the firing rule has no a-priori decision how to distribute the marking on the
generated net-tokens. Therefore we need the mode (π, π) to formulate the firing of πΜοΈπΌ [π] in a
functional way.
Reachability Graph Firing is extended to sequences π€ β Ξ*π in the usual way:
β’ The empty sequence π€ = π is enabled iff πβ² = π.
π€ π (π€Β·π)
β’ Whenever π βββ πβ² and πβ² βββ πβ²β² then π ββββ πβ² .
EH EH EH
* π€
We denote π βββ πβ² whenever there is some π€ such that π βββ πβ² holds. We omit the
EH EH
subscript EH whenever it is clear from the context. The set of reachable markings is defined as:
{οΈ }οΈ
*
RS (EH ) := RS (π0 ) := π | π0 βββ π (8)
EH
The reachability graph RG(EH ) = (π, πΈ, π0 ) contains all nested markings π = RS (EH )
π
as vertices (or: nodes), πΈ = {(π, πβ² ) | π β
β πβ² } as edges and the initial marking π0 as a
distinguished node.
3. Adaption Processes
For eHornets it is quite obvious how to define the gene pool of a system state: Obviously, we
are interested in the (multi-)set of object nets that are contained in the marking π. These are
given by the projection Ξ π°π (π):
(οΈβοΈπ )οΈ βοΈπ
Ξ π°π πΜοΈπ [ππ , ππ ] := 1π°π (ππ ) Β· ππ (9)
π=1 π=1
where the indicator function 1π°π is defined as: 1π°π (ππ ) = 1 iff ππ β π°π .
For the complete universe we define:
βοΈ βοΈπ
Ξ π° (π) := Ξ π°π (π) = ππ (10)
πβπΎ π=1
We define Ξ Μπ° := dom β Ξ π° to obtain the set of object nets. We use the metaphor that
Ξ Μπ° (π) = {π1 , . . . , ππ } is the gene pool of the marking π.
Note, that for safe Hornets we have no more object nets than system net places and therefore
|Ξ Μπ° (π))| β€ |Ξ π° (π)| β€ |πΜοΈ|, i.e. the gene pool is bounded.
88
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
3.1. Adaption in the Reachability Graph
The set of reachable object nets of EH , defined as:
βοΈ
π°(EH ) := π°(π0 ) := Ξ Μπ° (π) (11)
πβRS (π0 )
describes the universe of reachable genes, but it does not contain any information about the
adaption dynamics at all. So, we look at the reachability graph. But, the RG of a Hornet is
usually too large to analyse, since the reachability problem requires exponential space for safe
eHornets [22]. Fortunately, the RG contains much information that is not relevant when
studying the adaption process. We like to define an abstracted version of the RG that describes
the evolution of the gene pool (as specified by the Hornet).
As we are interested in the adaption dynamics of object nets we start with the reachability
graph and abstract from βirrelevantβ events. Roughly speaking, an event is considered as
irrelevant whenever the set of object nets Ξ ^ (π) doesnβt change when firing the event (i.e. the
π°
Hornet is stuttering with respect to the set of object nets).
Definition 3. The marking ππ+1 is π°-reachable in (π, πΈ) from π1 whenever there is a sequence
π1 π2 Β· Β· Β· ππ+1 such that for all π β {1, . . . , π} we have:
ππ
βππ : ππ β
β ππ+1 β§ Ξ Μπ° (ππ ) = Ξ Μπ° (ππ+1 )
Given RG(EH ) = (π, πΈ) we define the following relations on reachable markings:
β’ (π1 , π2 ) β π
1 iff π2 is π°-reachable from π1 in (π, πΈ) β and vice versa.
β’ (π1 , π2 ) β π
1β² iff π2 is π°-reachable from π1 in (π, πΈ).
β’ (π1 , π2 ) β π
2 iff π2 is π°-reachable from π1 in the undirected graph (π, (πΈ βͺ πΈ β1 )).
β’ (π1 , π2 ) β π
3 iff Ξ Μπ° (π1 ) = Ξ Μπ° (π2 )
In other words, π
1 relates markings that are strongly connected in the reachability graph
via irrelevant events; for π
1β² the connection may hold in only one direction; and π
2 relates
markings that are weakly connected via irrelevant events. Unlike the other relations, π
3 does
not assume any reachability relation between the markings.
Obviously, the relations have the following properties:
Lemma 1. β’ π
1 is reflexive, symmetric, and transitive.
β’ π
1β² is reflexive and transitive, but in general not symmetric.
β’ π
1 = π
1β² β© (π
1β² )β1
β’ π
2 is reflexive, symmetric, and transitive.
β’ π
3 is reflexive, symmetric, and transitive.
Since π
1 , π
2 , and π
3 are equivalences we can use them to factor the RG, i.e. equivalence
classes are condensed to a single node. All these graphs have π£0 := [π£0 ]π
π as a designated initial
node.
89
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
Definition 4. Let πΊ = (π, πΈ, π£0 ) be a graph with initial node and let β β π 2 be an equivalence
on the vertices. The factorised graph is defined as πΊ/β = (π β² , πΈ β² , π£0β² ) with
π β² = [π ]β , πΈ β² = {([π]β , [πβ² ]β ) | (π, πβ² ) β πΈ}, and π£0β² := [π£0 ]β
Then, the abstracted graph RG(EH )/π
π where π = 1, 2, 3 describes the evolution of the gene
pool that is specified by the Hornet.
The three relations leads to different kinds of abstraction due to the following inclusions:
Lemma 2 (Abstraction Hierarchy). π
1 β π
1β² β π
2 β π
3
Here, a finer equivalence leads to a larger factorised graph. With Lemma 2 we obtain
that RG(EH )/π
1 is closer to the original RG, while RG(EH )/π
3 leads to a more abstract
factorisation. More specifically:
β’ The graph AG 1 (EH ) := RG(EH )/π
1 collapses areas in the reachability graph where
the set of used object nets (i.e. the gene pool) doesnβt change, i.e. it abstracts away from
stuttering.
β’ The graph AG 2 (EH ) := RG(EH )/π
2 collapses greater areas in the RG since it is
sufficient that there is a weak connectivity of the markings in the RG.
β’ The graph AG 3 (EH ) := RG(EH )/π
3 collapses all markings into one single vertice
whenever the projection Ξ Μπ° (π) is the same.
3.2. Key Values of Abstract Graphs
In the following, we identify suitable graph theoretic measures to give key values of the abstract
graph (π, πΈ, π£0 ). Assume that π = |π | and π = |πΈ|. For more aspects of graph measures cf.
[27, Chapter 17].
3.2.1. Number of Adaptivity Options
On a macroscopic scale the average degree π1 Β· π£βπ deg(π£) tells us about how many evolution
βοΈ
options the system has. A higher value indicates that the system has many options to adapt.
Similarly, the density π(πβ1)
π
tells us something about the specificity of the adaption process
on a macroscopic scale, where a higher value indicates that the system has no specific direction
to evolve.
Graph transitivity looks at density on a more microscopic scale. It is the probability that π£βs
neighbours are connected, too:
|{(π’, π£, π€) | (π’, π£), (π£, π€), (π’, π€) β πΈ}|
πΆπ := (12)
|{(π’, π£, π€) | (π’, π£), (π£, π€) β πΈ}|
Transitivity tells us how dense the adaption process is on a small scale, i.e. when considering
triplets of nodes. A higher value indicates that there are many ways of achieving the same
adaption state, while a lower value indicates that some adaption states are reachable via a more
specific process, only
90
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
3.2.2. Measures for the Length of Adaption Processes
We are interested in measurements of the length of the adaption process. The path length tells
us something about the convergence speed. Let π(π£ β π£ β² ) denote the shortest path length
from node π£ to π£ β² . Then, the distances π(π£0 β π£) describes how long the adaption dynamics is
extended from initial node. A greater path length means a longer adaption dynamics.
The maximal distance from a given node is called its eccentricity π(π£):
π(π£) := max
β²
π(π£ β π£ β² ) (13)
π£ βπ
The eccentricity π(π£0 ) tells us about the gene pool that is farthest away. We also consider the
normalised variant π(π£0 )/π.
3.2.3. Identifying central Gene Pools
We also identify the most βcentralβ states in the dynamics, which are in some sense the discrete,
graph-theoretical analogon of an attractor. There are several concepts of centrality in graph
theory. Here, we use betweeness centrality ππ΅ (π£) that is the probability for the shortest path
between two nodes to go through that node π£.
π£
1 βοΈ ππ π (π’ β
β π€)
ππ΅ (π£) := (14)
(π β 1)(π β 2) ππ π (π’ β π€)
π’,π€βπ :π’ΜΈ=π£,π€ΜΈ=π£,π’ΜΈ=π€
π£
Here, ππ π (π’ β π€) is the number of shortest paths from node π’ to node π€ and ππ π (π’ β β π€)
is the number of the shortest paths that go through node π£.
We use the stochastic distribution of betweeness centrality ππ (π£) to identify which of the
nodes/genes are very central in the dynamics. The variance indicates whether the distribution
is tight around its average value: a higher variance indicates that some nodes are more central
than others.
3.3. Directedness of Adaption
Assumed that adaption always leads to an improvement, the abstract graph would contain no
cycles. In general, a system will allow for some regression for exploration issues β a try-and-error
strategy. But it is reasonable that on larger time scales adaption will lead to an improvement. So,
longer cycles are typically less common than short ones. When βignoringβ cycles, the abstract
graph describes a partial order. Therefore, we have to find a maximal sub-graph that describes
a partial order, i.e. a maximal DAG (directed acyclic graph). This sub-graph is interpreted as an
underlying dynamics of improvement β when ignoring small phases of regression. We require
that all the nodes remain reachable from the initial node π£0 in the DAG. So, we generate a
maximal spanning DAG. The set of all such sub-graphs of πΊ = (π, πΈ, π£0 ) being a DAG is:
π·π΄πΊπ (π, πΈ, π£0 ) := {π· | π· = (π, πΈπ· , π£0 ) is a DAG β§
*} (15)
πΈπ· β πΈ β§ βπ£ β π : (π£0 , π£) β πΈπ·
91
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
We are interested in a sub-DAG of maximal size:
π0 (πΊ) := max{|πΈπ· | | (π, πΈπ· , π£0 ) β π·π΄πΊπ (πΊ)} (16)
In other words, |πΈ| β π0 (πΊ) is the minimal number of edges to be deleted to obtain an acyclic
graph from the abstracted reachability graph πΊ.
Definition 5. The degree of adaption directedness is dad (πΊ) := π|πΈ|
0 (πΊ)
.
The degree of adaption directedness indicates, how much the dynamics is going into a certain
direction (which can be interpreted as an improvement). When πππ(πΊ) is close to 1, then the RG
is acyclic, and the adaption dynamics goes (almost) strictly into one direction; while a dad (πΊ)
close to 0 indicates an adaption process heavily running in cycles. Of course, we hope for a
dynamics with dad (πΊ) β 1, since they are easier to interprete.
Any subgraph π· = (π, πΈπ· , π£0 ) of πΊ = (π, πΈ, π£0 ) being a DAG with maximally many edges,
i.e. |πΈπ· | = π0 (πΊ), is a candidate for the underlying improvement dynamics.
π·π΄πΊπ0 (πΊ) := {(π, πΈπ· , π£0 ) β π·π΄πΊπ (πΊ) | π0 (πΊ) = |πΈπ· |} (17)
We use depth and width of all the DAGs π· β π·π΄πΊπ0 (π, πΈ, π£0 ) as our central key measures:
β’ The DAG-depth is the largest line, i.e. a maximal clique w.r.t. li, which is the dependence
relation of a DAG π· = (π, πΈ, π£0 ) defined as li := πΈ * βͺ (πΈ * )β1 βͺ id π :
depth π· (π·) := max{|πΏ| | πΏ is maximal li-clique } (18)
A greater depth tell us that the system is very productive with respect to adaption, since
it is going very straight into one direction.
β’ The DAG-width is the largest cut, i.e. a maximal independent set, or, alternatively, a
maximal clique w.r.t. the independence relation co := li βͺ id π :
width π· (π·) := max{|πΆ| | πΆ is maximal co-clique } (19)
A greater width tells us that for a given gene pool there is a large amount of options to
adapt β depending on structural aspects we have abstracted from in the adaption graph.
β’ The depth-width ratio depth(πΊ)/width(πΊ) tells us something about the number of
adaption options given per productive evolution step.
We average the depth and width over all the DAGs in π·π΄πΊπ0 (π, πΈ, π£0 ):
1 βοΈ
depth(πΊ) := depth π· (π·) (20)
|π·π΄πΊπ0 (πΊ)|
π·βπ·π΄πΊπ0 (πΊ)
Analogously for width(πΊ).
92
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
3.4. Relationship between exploration and exploitation
We can transform the DAG π· = (π, πΈ, π£0 ) into a tree by using a different copy of a node for
each path π from the initial node to this node. (The definition is unproblematic, since our DAGs
have finitely many nodes, and therefore also only finitely many paths.)
Definition 6. Define the tree unfolding of a DAG π· = (π, πΈ, π£0 ) as tree(π·) = (ππ‘π , πΈπ‘π , π£0 )
with
ππ‘π = {π | π = π£0 . . . π£ is a path in π· }
πΈπ‘π = {(π, πβ² ) | πβ² = π Β· π£ β² }
The tree structure reveals information about the relationship between exploration of the
adaption space, i.e. when the systems tests different options (and this accepts regression), and
its exploitation, i.e. when the systems sticks to a pretty good option and tries to improve it with
minor changes instead of evaluating some completely other option.
When the tree is growing the systems explores the adaption space. When the growth stagnates
the system exploits the information gained. We try to capture this in the following measures:
The adaption tree π has a different branching structure, i.e. less successors here and more over
there; additionally, exploration and exploitation does not necessarily come in two successive
phases, but in many, intertwined ones. So, we compare our tree with a very βtidyβ reference
tree, namely a tree that starts with the exploration phase followed by the exploitation phase.
When the root is drawn at the top the tree has a β³ β‘ -like shape, where the triangle describes the
exploration (with a high branching degree) and the rectangle describes the exploitation (with
no branching). A dynamics that has a maximal exploration leads to a tree that consists of the
triangle part only.
Assume that the original tree π has height β0 and π0 leaves and π0 nodes. Let β be the height
of the exploration-triangle and ββ² the height of the exploitation-rectangle in the reference tree.
Similarly, the triangle has π nodes and π leaves; the rectangle has πβ² nodes and πβ² leaves. As the
rectangle has no branching, it has the same number of leaves as the triangle: π = πβ² . We want
to have a β³ β‘ -like tree that the same height and also the same number of nodes as the original
tree: β0 = β + ββ² and π0 = π + πβ² . We also require that the number of leaves does not change:
π0 = π = πβ² .
The new tree must have a (yet unknown) branching π such that πβ = π = π0 in the β³-part
πβ+1 β1
of the β³β‘ -like shape. Thus the complete triangle then has π = πβ1 nodes and π = π leaves.
β
The rectangle has as many leaves as the triangle, as we have no branching here, and πβ² = ββ² Β· πβ
nodes. So, we obtain:
πβ+1 β 1
π0 = π + πβ² = + ββ² Β· πβ β πβ + ββ² Β· πβ = πβ (1 + ββ² ) = π0 (1 + ββ² )
πβ1
Therefore, the exploitation rectangle β‘ has the height ββ² β ππ00 β 1. From this we obtain the
height β of the exploration triangle β³ as β = β0 β ββ² β β0 β ππ00 + 1.
Let π· = (π, πΈ, π£0 ) be a DAG and assume that its tree unfolding π = tree(π·) has π0 leaves,
π0 nodes, and height β0 . Then, the exploitation rate of π = tree(π, πΈ, π£0 ) is the ratio of the
93
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
rectangle height ββ² to the total height β0 :
ββ²
(οΈ )οΈ
1 π0
π(π ) := β β1 (21)
β0 β0 π0
Correspondingly, the exploration rate is given as (1 β π(π )).
We are interested in the corresponding exploration and exploitation rates in the adaption
dynamics.
Definition 7 (exploration and exploitation rates). For the DAG π· we define π(π·) :=
π(tree(π·)). For an abstract reachability graph πΊ we define:
1 βοΈ
π(πΊ) := π(π·) (22)
|π·π΄πΊπ0 (πΊ)|
π·βπ·π΄πΊπ0 (πΊ)
These rates are used to characterise adaption dynamics: Systems with a high exploration
rate could be considered as adventurous, while systems with a high exploitation rate could be
considered as more conservative.
4. Case Study: Axelrodβs Tournament
In Axelrodβs Tournament [28] several agents are playing the well known prisonersβ dilemma. If
both agents cooperate (C) they both obtain a payoff, e.g. π = 3; If only one agent cooperate the
defecting (D) gets a higher payoff of e.g. π‘ = 5, while the cooperating one obtains nothing π = 0.
If both agents defect they both obtain a small payoff, e.g. π = 1. In general, π‘ > π > π > π β₯ 0
is assumed.
cooperate (C) defect (D)
cooperate (C) 3,3 0,5
defect (D) 5,0 1,1
In the tournament version π agents are playing this game pairwise over several rounds. The
agents are allowed to adapt their strategy over time. We assume that each agent remembers a
finite history of games already played with a given opponent. Assuming a history of size 3 a
history is β = π3 π2 π1 = (π3 , π3 )(π2 , π2 )(π1 , π1 ) where ππ , ππ β {πΆ, π·}. A strategy is therefore
a function π : {πΆ, π·}6 β {πΆ, π·}. When describing strategies by automata each history
β β {πΆ, π·}6 is a state and the action chosen for the current game is given by state changes.
6
Even for this very restricted history size we have 22 = 264 different strategies, i.e. the
strategy space is far too large to be explored directly. The classical approach to adaption is
genetic programming. The main idea is simple ([2, pg 80ff]): Each strategy evaluates its payoff
so far. The higher the payoff the higher the number of offsprings. An offspring is generated
via a cross-over mechanism, i.e. the two parentsβ histories are split at some fixed point and
recombined in a cross-over fashion.
We generalise the setting: We assume that there is a network that connects the agents and
only connected agents can play the game. We assume that a network also determines which
94
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
Figure 3: The eHornetβs System Net for the Tournament
agents may be chosen as parents when generating a cross-over. For simplicity we assume both
networks to be equal.
We have specified this scenario as an eHornet. Here, the object nets specify the agents,
i.e. the strategy automata. The system net (shown in a simplified version in Fig. 3) specifies
which agents are chosen for playing the game. It also specifies which agents are chosen in the
adaption process for the cross-over. The system net is parametrised with the connection graph.
The details of this case study can be found in [29].
adaption dynamics ErdΕs-RΓ©nyi Watts-Strogatz
average degree π1 Β· π£βπ deg(π£)
βοΈ
3.42 3.14
π
density π(πβ1) 0.13 0.26
transitivity πΆπ 0.07 0.00
eccentricity π(π£0 ) 4 3
variance of betweeness centrality ππ΅ (π£) 0.05 0.10
adaption directedness dad (πΊ) 0.63 0.55
width(πΊ)/depth(πΊ) 7/4 = 1.75 4/3 = 1.33
rate of exploitation π(πΊ) 0.20 0.25
Table 1
Summary of Key Measures of Adaption Processes for different Topologies
We study two different random graph topologies for the connection graph, namely a ErdΕs-
RΓ©nyi graph [30] and a Watts-Strogatz graph [31] with a rewiring probability of π½ = 0.01 β
both with the same number of nodes (π = 28) and the same number of edges (π = 3π = 84),
modelled by the eHornets EH 1 and EH 2 . We have chosen these two graphs because they are
both well known random graph structures. Moreover, the ErdΕs-RΓ©nyi graph is the special case
of a Watts-Strogatz graph where π½ = 1. It is well known that for small values of π½ each pair of
nodes is connected in a Watts-Strogatz graph via a quite short path of length β log(π), a fact
that is also known as the small world property.
We generate the abstract adaption graphs AG 3 (EH π ), π = 1, 2 for the two topologies. The
key measures of the two abstracted reachability graphs are given in Table 1. One can observe,
95
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
for example, that the ErdΕs-RΓ©nyi graph is more exploring than Watts-Strogatz graph as it has
a higher average degree, a higher width/depth-ratio, and a lower exploitation rate π(πΊ). One
may hypothesize that the reason for this lies in the small world property of the Watts-Strogatz,
i.e. we have long-range connections and therefore every node is only some steps away from
any other node, which is not the case for an ErdΕs-RΓ©nyi graph. Therefore, the Watts-Strogatz
graph is faster in spreading good genes over the entire population.
5. Conclusion
In this contribution we developed key measures to compare adaption processes, usually adaption
processes of variants of the same system. We used the nets-within-nets formalism of Hornets
as our formal model as they provide a natural description of what is adapted within the system:
the set Ξ Μπ° (π)) of net-types occurring in the current marking π. Here, the system net describes
the general system, while the markingβs set of object net types describe the changing gene-pool.
For the analysis we abstract from events in the Hornet that doesnβt effect the gene pool and
use network theoretical measures to describe a fingerprint of the adaption process.
Here, we abstracted from events that do not change the gene-pool. Currently, we are relaxing
this even further by ignoring events that change the gene-pool only slightly, i.e. we use a
distance π between gene-pools as an additional parameter. In future work we also like to analyse
the adaption dynamics via static properties of the Petri nets, like invariants etc. For most cases
it may be sufficient to study an under- or an over-approximation of the state space.
References
[1] M. KΓΆhler-BuΓmeier, Hornets: Nets within nets combined with net algebra, in: K. Wolf,
G. Franceschinis (Eds.), International Conference on Application and Theory of Petri Nets
(ICATPNβ2009), volume 5606 of Lecture Notes in Computer Science, Springer-Verlag, 2009,
pp. 243β262.
[2] J. H. Holland, Hidden Order: How Adaptation builds complexity, Helix Books, 1995.
[3] M. KΓΆhler, H. RΓΆlke, Properties of Object Petri Nets, in: J. Cortadella, W. Reisig (Eds.),
International Conference on Application and Theory of Petri Nets 2004, volume 3099 of
Lecture Notes in Computer Science, Springer-Verlag, 2004, pp. 278β297.
[4] M. KΓΆhler-BuΓmeier, F. Heitmann, On the expressiveness of communication channels for
object nets, Fundamenta Informaticae 93 (2009) 205β219.
[5] R. Valk, Object Petri nets: Using the nets-within-nets paradigm, in: J. Desel, W. Reisig,
G. Rozenberg (Eds.), Advanced Course on Petri Nets 2003, volume 3098 of Lecture Notes in
Computer Science, Springer-Verlag, 2003, pp. 819β848.
[6] I. A. Lomazova, Nested Petri nets β a formalism for specification of multi-agent distributed
systems, Fundamenta Informaticae 43 (2000) 195β214.
[7] D. Xu, Y. Deng, Modeling mobile agent systems with high level Petri nets, in: IEEE
International Conference on Systems, Man, and Cyberneticsβ2000, 2000.
[8] O. Kummer, Referenznetze, Logos Verlag, 2002.
96
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
[9] K. Hiraishi, PN2 : An elementary model for design and analysis of multi-agent systems, in:
F. Arbab, C. L. Talcott (Eds.), Coordination Models and Languages, COORDINATION 2002,
volume 2315 of Lecture Notes in Computer Science, Springer-Verlag, 2002, pp. 220β235.
[10] M. A. Bednarczyk, L. Bernardinello, W. Pawlowski, L. Pomello, Modelling mobility with
Petri hypernets, in: J. L. Fiadeiro, P. D. Mosses, F. Orejas (Eds.), Recent Trends in Algebraic
Development Techniques (WADT 2004), volume 3423 of Lecture Notes in Computer Science,
Springer-Verlag, 2004, pp. 28β44.
[11] C. Lakos, A Petri net view of mobility, in: Formal Techniques for Networked and
Distributed Systems (FORTE 2005), volume 3731 of Lecture Notes in Computer Science,
Springer-Verlag, 2005, pp. 174β188.
[12] I. A. Lomazova, K. M. van Hee, O. Oanea, A. Serebrenik, N. Sidorova, M. Voorhoeve, Nested
nets for adaptive systems, in: Application and Theory of Petri Nets and Other Models of
Concurrency, Lecture Notes in Computer Science, Springer-Verlag, 2006, pp. 241β260.
[13] L. Cardelli, A. D. Gordon, G. Ghelli, Mobility types for mobile ambients, in: Proceedings
of the Conference on Automata, Languages, and Programming (ICALPβ99), volume 1644
of Lecture Notes in Computer Science, Springer-Verlag, 1999, pp. 230β239.
[14] R. Milner, J. Parrow, D. Walker, A calculus of mobile processes, parts 1-2, Information and
computation 100 (1992) 1β77.
[15] W. Reisig, Petri nets and algebraic specifications, Theoretical Computer Science 80 (1991)
1β34.
[16] K. Hoffmann, H. Ehrig, T. Mossakowski, High-level nets with nets and rules as tokens, in:
Application and Theory of Petri Nets and Other Models of Concurrency, volume 3536 of
Lecture Notes in Computer Science, Springer-Verlag, 2005, pp. 268 β 288.
[17] I. Lomazova, Nested petri nets for adaptive process modeling, in: A. Avron, N. Dershowitz,
A. Rabinovich (Eds.), Pillars of Computer Science, volume 4800 of Lecture Notes in Computer
Science, Springer-Verlag, 2008, pp. 460β474.
[18] G. Taentzer, Distributed graphs and graph transformation, Applied Categorical Structures
7 (1999) 431β462.
[19] M. KΓΆhler-BuΓmeier, F. Heitmann, Safeness for object nets, Fundamenta Informaticae 101
(2010) 29β43.
[20] M. KΓΆhler-BuΓmeier, F. Heitmann, Liveness of safe object nets, Fundamenta Informaticae
112 (2011) 73β87.
[21] M. KΓΆhler-BuΓmeier, A survey on decidability results for elementary object systems,
Fundamenta Informaticae 130 (2014) 99β123.
[22] M. KΓΆhler-BuΓmeier, On the complexity of the reachability problem for safe, elementary
Hornets, Fundamenta Informaticae 129 (2014) 101β116. Dedicated to the Memory of
Professor Manfred Kudlek.
[23] R. J. Lipton, The reachability problem requires exponential space, Research Report 62,
Dept. of Computer science, 1976.
[24] M. KΓΆhler-BuΓmeier, F. Heitmann, An upper bound for the reachability problem of safe,
elementary hornets, Fundamenta Informaticae 143 (2016) 89β100.
[25] M. KΓΆhler-BuΓmeier, Restricting Hornets to support adaptive systems, in: W. van der Aalst,
E. Best (Eds.), PETRI NETS 2017, Lecture Notes in Computer Science, Springer-Verlag,
2017.
97
οΏ½Michael KΓΆhler-Bussmeier et al. CEUR Workshop Proceedings 80β98
[26] H. Ehrig, B. Mahr, Fundamentals of algebraic Specification, EATCS Monographs on TCS,
Springer-Verlag, 1985.
[27] H. Sayama, Introduction to the Modeling and Analysis of Complex Systems, Open SUNY
Textbooks, 2015.
[28] R. Axelrod, The Evolution of Cooperation, Basic Books, 1984.
[29] M. Jankowski, P. B. Dang, J. Krukenberg, Analyse evolutionΓ€rer Strategien, Term Paper,
HAW Hamburg, 2022.
[30] P. ErdΓΆs, A. RΓ©nyi, On random graphs, Publicationes Mathematicae 6 (1959) 290β297.
[31] D. J. Watts, S. H. Strogatz, Collective dynamics of βsmall-worldβ networks, Nature 393
(1998) 440β442.
98
οΏ½