scroll identifier for mobile
main-content

## Über dieses Buch

Reaction-diffusion and excitable media are amongst most intriguing substrates. Despite apparent simplicity of the physical processes involved the media exhibit a wide range of amazing patterns: from target and spiral waves to travelling localisations and stationary breathing patterns. These media are at the heart of most natural processes, including morphogenesis of living beings, geological formations, nervous and muscular activity, and socio-economic developments.

This book explores a minimalist paradigm of studying reaction-diffusion and excitable media using locally-connected networks of finite-state machines: cellular automata and automata on proximity graphs. Cellular automata are marvellous objects per se because they show us how to generate and manage complexity using very simple rules of dynamical transitions. When combined with the reaction-diffusion paradigm the cellular automata become an essential user-friendly tool for modelling natural systems and designing future and emergent computing architectures.

The book brings together hot topics of non-linear sciences, complexity, and future and emergent computing. It shows how to discover propagating localisation and perform computation with them in very simple two-dimensional automaton models. Paradigms, models and implementations presented in the book strengthen the theoretical foundations in the area for future and emergent computing and lay key stones towards physical embodied information processing systems.

## Inhaltsverzeichnis

### Introduction

Cellular automata are regular uniform networks of locally-connected finite-state machines, called cells. A cell takes a finite number of states. Cells are locally connected: every cell updates its state depending on states of its geographically closest neighbours. All cells update their states simultaneously in discrete time steps. All cells employe the same rule to calculate their states. Cellular automata are discrete systems with non-trivial behaviour. They are mathematical models of computation and computer models of natural systems.

### Reaction-Diffusion Binary-State Automata

Here we consider a simplest version of reaction-diffusion automaton: a two-dimensional cellular automaton, where a cell has eight closest neighbours and takes two states, 0 and 1. We earmark state 0 as a substrate and state 1 as a reagent. To imitate diffusion and reaction we allow state 1 to spread: a cell in state 0 takes state 1 – under certain conditions – if it has some neighbours in state 1.

### Retained Excitation

In classical models of excitation an excited cells returns to refractory states either immediately or in few steps but in any case independently on a state if its neighbourhood. How space-time dynamics of excitation will change if we allow excited cells to stay excited for certain configurations of excitation in their neighbourhoods? Let us consider excitation rules which allow excitation to persist by enabling excited cells ‘support’ their already excited neighbours.

### Mutualistic Excitation

In a classical Greenberg-Hasting model of excitation a resting cell excites depending on number of its excited neighbours. What if the process of being excited depends also on refractory states? Let every cell

x

of an automaton imitating mutualistic excitation take three states: resting ·, excited ∙, refractory ∘. and updates its state by the rule

$x^{t+1} = \begin{cases} \bullet, \text{ if } x^t=\cdot \text{ and } \sigma_+^t(x) \in[\theta_1, \theta_2] \text{ and } \sigma_-^t(x) \in[\delta_1, \delta_2]\\ \circ, \text{ if } x^t=\bullet\\ \cdot, \text{ otherwise } \end{cases}$

(4.1)

### Dynamical Excitation Intervals: Diversity and Localisations

Back in 1998 [7], we introduced an excitable cellular automaton,where a resting cell is excited if a number of its excited neighbours belong to a fixed interval [

θ

1

,

θ

2

]. The interval [

θ

1

,

θ

2

] is called an excitation interval. For two-dimensional cellular automaton with eight-cell neighbourhood 1 ≤

θ

1

≤

θ

2

≤ 8. We found that by tuning

θ

1

and

θ

2

we can persuade the automaton to imitate almost all kinds of excitation dynamics, from classical target and spiral waves observed in physical and chemical excitable media to wave-fragments inhabiting sub-excitable media [7].

### Excitable Delaunay Triangulations

Given a planar finite set

V

the Delaunay triangulation [92]

${\mathcal D}$

(

V

)= 〈

V

,

E

〉 is a graph subdividing the space onto triangles with vertices in

V

and edges in

E

where the circumcircle of any triangle contains no points of

V

other than its vertices. Neighbours of a node

v

∈

V

are nodes from

V

connected with v by edges from

E

.

The set

V

is constructed as follows. We take a disc-container of radius 480 and fill it with up to 15,000 disc-nodes. We assume that each disc-node has radius 2.5, thus a minimal distance between any two nodes is 5. The Voronoi diagram, and its dual triangulation, are appropriate representations of such identical sphere packing on two-dimensional surface, where planar points of

V

represent centres of the spheres.

### Excitable β-Skeletons

Given a set

$\mathbf V$

of planar points, for any two points

p

and

q

we define

β

-neighbourhood

U

β

(

p

,

q

) as an intersection of two discs with radius

β

|

p

−

q

| / 2 centered at points

$((1-\frac{\beta}{2})p,\frac{\beta}{2}q)$

and

$(\frac{\beta}{2}p, (1-\frac{\beta}{2})q)$

,

β

≥ 1 [150, 160], see examples of the lunes in Fig.7.1. Points

p

and

q

are connected by an edge in

β

-skeleton if the pair’s

β

-neighbourhood contains no other points from

$\mathbf V$

.

### Evolving Localizations in Reaction-Diffusion Automata

We consider a ternary-state totalistic hexagonal cellular automaton, where a cell updates its state depending on just the numbers, not positions, of different cell-states in its neighbourhoods. One cell-state,

S

, is a dedicated substrate state: a cell in state

S

, whose neighbourhood is filled only with states

S

, does not change its state (

S

is a an analogue of quiescent state in cellular automaton models). Two other states,

A

and

B

, are assigned to be reactants.

### Population Dynamics in Automata

Let us consider a two-dimensional hexagonal cellular automaton, every cell of which takes two states: species

a

and species

b

, and updates its state in discrete time indexautomaton!population depending on its own state and just the numbers of cell-states of its six neighbours. Let

$\sigma_a^t(x)$

and

$\sigma_b^t(x)$

be sums of cell

x

’s neighbours in state

a

and

b

, respectively, at time step

t

.

### Automaton Mechanics of Mutualism

We simulate mutualistic relationships in a two-dimensional hexagonal cellular automaton. Every cell takes three states: 0, 1 and 2. States 1 and 2 represent species species ‘1’ and species ‘2’. State 0 represents an ‘empty space’, or a substrate. Two processes must be simulated: propagation of species and survival of species. A cell of the hexagonal cellular automaton can be occupied exclusively by ‘empty space’, state 0, or by one of the species, states 1 or 2.

### Voronoi Automata

Let

P

be a nonempty finite set of planar points. A planar Voronoi diagram [253] of the set

P

is a partition of the plane into such regions, that for any element of

P

, a region corresponding to a unique point

p

contains all those points of the plane which are closer to

p

than to any other node of

P

. A unique region

vor

(

p

) = {

z

∈

R

2

:

d

(

p

,

z

) <

d

(

p

,

m

) ∀

m

∈

R

2

,

m

≠

z

} assigned to point

p

is called a Voronoi cell of the point

p

[211]. The boundary ∂

vor

(

p

) of the Voronoi cell of a point

p

is built of segments of bisectors separating pairs of geographically closest points of the given planar set

P

. A union of

VD

(

P

) = ∪

p

∈

P

∂

vor

(

p

) all boundaries of the Voronoi cells determines the planar Voronoi diagram [211]. A variety of Voronoi diagrams and algorithms of their construction can be found in [162, 206].

### Adders and Multipliers in Sub-excitable Automata

To implement binary arithmetics we employ a cellular-automaton model of an excitable medium — the 2

+

-medium, [2, 3, 8]. The 2

+

-medium is a two-dimensional three-state — resting (·), excited (+) and refractory (–) — cellular automaton where a resting cell becomes excited only exactly two neighbours are excited. The transitions from excited state to refractory state, and from refractory state to resting state are unconditional.

### Computing in Hexagonal Reaction-Diffusion Automaton

We design a totalistic cellular automaton, where a cell updates its state depending on just the numbers of different cell-states in its neighbourhoods.Consider a ternary state automaton, where every cell takes one of the following cell-states: substrate

S

, activator

A

and inhibitor

I

.

### Semi-memristive Automata: Retained Refractoriness

A cellular automaton

$\mathcal{A}$

is an orthogonal array of uniform finite-state machines, or cells. Each cell takes the finite number of states and updates its states in discrete time depending on states of its closest neighbours. All cells update their states simultaneously by the same rule. We consider eight-cell neighbourhood and three cell-states: resting ∘, excited +, and refractory –. Let

u

(

x

) = {

y

: |

x

−

y

|

L

∞

= 1} be a neighbourhood of cell

x

. Let

$\sigma^t_x = \sum_{y \in u(x)} \chi(y^t, +)$

be the sum of excited neighbours of cell

x

at time step

t

, where

χ

(

y

t

, + ) = 1 if

y

t

= + and

χ

(

y

t

, + ) = 0 otherwise. Let Θ = [

θ

1

,

θ

2

], 1 ≤

θ

1

≤

θ

2

≤ 8, be an excitation interval, and Φ = [

φ

1

,

φ

2

], 1 ≤

φ

1

≤

φ

2

≤ 8, be a recovery interval.

### Structural Dynamics: Memristive Excitable Automata

A memristive automaton is a structurally-dynamic excitable cellular automaton where a link connecting two cells is removed or added if one of the cells is in excited state and another cell is in refractory state.

A cellular automaton

$\mathcal{A}$

is an orthogonal array of uniform finite-state machines, or cells. Each cell takes finite number of states and updates its states in discrete time depending on states of its closest neighbours. All cells update their states simultaneously by the same rule. We consider eight-cell neighbourhood and three cell-states: resting ∘, excited +, and refractory −. Let

u

(

x

) = {

y

: |

x

−

y

|

L

∞

= 1} be a neighbourhood of cell

x

. A cell

x

has a set of incoming links {

l

xy

:

y

∈

u

(

x

)} which take states 0 and 1. A link

l

xy

is a link of excitation transfer from cell

y

to cell

x

. A link in state 0 is considered to be high-resistant, or non-conductive, and link in state 1 low resistant, or conductive. A link-state

$l^t_{xy}$

is updated depending on states of cells

x

and

y

at time step

t

:

$l^t_{xy} = f(x^t, y^t)$

. Resting state gives little indication of cell’s previous history, therefore we will consider only non-resting cells contributing to a link state updates. When cells

x

and

y

are in the same state (bother cells are in state + or both are in state −) no ’current’ can flow between the cells, therefore scenarios

x

t

=

y

t

are not taken into account.

### Backmatter

Weitere Informationen

## BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

## Whitepaper

- ANZEIGE -

### Technisches Interface Design - Beispiele aus der Praxis

Eine gute Theorie besticht nur darin, dass am Ende einer Entwicklung sinnvolle und nutzergerechte Produkte herauskommen. Das Forschungs- und Lehrgebiet Technisches Design legt einen starken Wert auf die direkte Anwendung der am Institut generierten wissenschaftlichen Erkenntnisse. Die grundlegenden und trendunabhängigen Erkenntnisse sind Grundlage und werden in der Produktentwicklung angewendet. Nutzen Sie die Erkenntnisse aus den hier ausführlich dargestellten Praxisbespielen jetzt auch für Ihr Unternehmen.