Difference between revisions of "Vol-3170/paper5"
Jump to navigation
Jump to search
(modified through wikirestore by wf) |
(edited by wikiedit) |
||
| Line 8: | Line 8: | ||
|authors=Michael Köhler-Bussmeier,Heiko Rölke | |authors=Michael Köhler-Bussmeier,Heiko Rölke | ||
|dblpUrl=https://dblp.org/rec/conf/apn/Kohler-Bussmeier22 | |dblpUrl=https://dblp.org/rec/conf/apn/Kohler-Bussmeier22 | ||
| + | |wikidataid=Q117351490 | ||
}} | }} | ||
==Analysing Adaption Processes of Hornets== | ==Analysing Adaption Processes of Hornets== | ||
Latest revision as of 12:15, 31 March 2023
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
�