August 27-29, 2007
The Fields Institute
Cellular
Automata with Memory
by
Ramon Alonso-Sanz
ETSI Agronomos (Estadistica), GSC-UPM, C.Universitaria, 28040, Madrid,
Spain
Coauthors: Margarita Martin (Universidad Complutense de Madrid)
Cellular Automata (CA) are discrete, spatially explicit extended
dynamic systems. A CA system is composed of adjacent cells characterized
by an internal state whose value belongs to a finite set. The updating
of these states is made simultaneously according to a common local
transition rule involving only a neighborhood of each cell. Thus,
if s(T)i is taken to denote the value of cell i at time step T,
the site values evolve by iteration of the mapping : s(T+1)i = f({s(T)j}e
Ni), where f is an arbitrary function which specifies the cellular
automaton rule operating on Ni, i.e. the set of cells in the neighborhood
of the cell i .
Standard CA are ahistoric (memoryless): i.e., the new state of
a cell depends on the neighborhood configuration solely at the preceding
time step. The standard framework of CA can be extended by the consideration
of past states (history) in the application of the CA rules by implementing
memory capabilities in cells: s(T+1)i=f({s(T)j}e Ni), with s(T)j
being a state function of the series of states of the cell j up
to time-step T. Thus in CA with memory here: while the update rules
of the CA remain unaltered, historic memory of past iterations is
retained by featuring each cell by a summary of its past states.
Embedding memory in states (and in links if wiring is also dynamic)
broadens the spectrum of CA as a tool for modeling, in a fairly
natural way of easy computer implementation. It is likely that in
some contexts, a transition rule with memory could match the correct
behavior of the CA system of a given complex system (physical, biological,
social and so on). A major impediment in modeling with CA stems
from the difficulty of utilizing the CA complex behavior to exhibit
a particular behavior or perform a particular function. Average
memory in CA tends to inhibit complexity, inhibition that can be
modulated by varying the depth of memory, but memory not of average
type opens a notable new perspective in CA. This could mean a potential
advantage of CA with memory over standard CA as a tool for modeling.
Anyway, besides their potential applications, CA with memory (CAM)
have an aesthetic and mathematical interest on their own.
Thus, it seems plausible that further study on CA with memory should
turn out profitable, and, maybe that as a result of a further rigorous
study of CAM, it will be possible to paraphrase T.Toffoli in presenting
CAM as an alternative to (rather than an approximation of) integro-differential
equations in modeling phenomena with memory.
-Back to top
Boolean Derivatives, Chaos and Synchronization
in Cellular Automata
by
Franco Bagnoli, University of Florence (Italy)
Coauthors: Raul Rechtman
A cellular automata is a discrete dynamical system, the discrete
equivalent of a partial differential equation. The evolution of
an automata if given by a vectorial discrete function, i.e., a set
of functions defined on a finite set of values. In particular, we
consider Boolean functions and show how to define their derivatives
and series expansion. Using this concept, it is possible to define
also the Jacobian of a vector function (the evolution rule), that
is related to the problem of percolation of defects in the evolution
of automata. Similarly to what happens in continuous systems, we
can define a maximal Lyapunov exponent that measures the stability
of a trajectory with respect to perturbations. We show that the
maximal Lyapunov exponent is related to the stochastic synchronizability
of two replicas (pinching synchronization).
-Back to top
A Neuron-genetic approach for Pattern
Recognition in Cellular Automata
by
Stefania Bandini, Complex Systems & Artificial Intelligence
Research Center - University of Milano-Bicocca
Coauthors: L. Vanneschi, A Wuensche
In this work, a new technique for Cellular Automata pattern recognition
[Ganguly et al., 2002] [Bandini et al., 2006] is presented. The
contribution is focused on the presentation of a generic framework,
interfaced with the DDL platform [Wuensche, 2005], that allows the
search for rules that generate, in their dynamics, certain families
of patterns. Specifically, the framework returns a class of rules
that "resemble" (to a human observer) the one generated
by a given "prototype" rule (that is assumed to be known)
in a completely automatic way. We focus on 3-values and 6-neighbors
k-totalistic Cellular Automata rules defined on two-dimensional
hexagonal lattices and we chose as a prototype the so called "Burning
Paper" rule, introduced in [Wuensche, 2005]. Nevertheless,
this work also stresses the fact that our framework is general and
can be extended to any kind our Cellular Automata rule and also
to other pattern recognition applications, like in image analysis
or signal processing. The huge search space of all the possible
Cellular Automata rules is explored by means of a Genetic Algorithm
[Tomassini and Vanneschi, 2006], whose quality (or fitness) function
is based on the model returned by a set of Machine Learning methods,
including Feed-Forward Artificial Neural Networks [Mitchell, 1997]
and Support Vector Machines [Burges, 1998]. These methods are trained
to recognize similarities between patterns, where the concept of
similarity is a very general one, which may include modifications
in space and time, preserving shapes resemblances. At the same time,
the input of these methods consists in a set of features we have
carefully defined by means of some new and efficient feature selection
techniques. The obtained experimental results are encouraging and
should pave the way for the use of our framework for more sophisticated
real-life applications.
Bibliography
[Bandini et al., 2006] S. Bandini, S. Manzoni, G. Mauri, S. Redaelli;
“Emergent Pattern Interpretation in Vegetable Population
Dynamics”. In Journal of Cellular Automata, Vol. X, pp. 01–07,
2006.
[Burges, 1998] C. J. C. Burges; "A Tutorial on Support Vector
Machines for Pattern Recognition". In Data Mining and Knowledge
Discovery, 2(2): 121-167, 1998.
[Ganguly et al., 2002] N. Ganguly, P. Maji, S. Dahr, B. K. Silkdar,
P.P. Chaudhuri; "Evolving Cellular Automata as Pattern Classifier".
In Proceedings of the Fifth International Conference on Cellular
Automata for Research and Industry, ACRI 2002, Geneva, Switzerland,
pp. 56-68, 2002.
[Mitchell, 1997] T. M. Mitchell. Machine Learning. McGraw-Hill
Higher Education, 1997.
[Tomassini and Vanneschi, 2006] M. Tomassini and L. Vanneschi;
Evolutionary algorithms in problem solving and machine learning.
In F. Orsucci and N. Sala, editors, Reflecting Interfaces: The
Complex Coevolution of Information Technology Ecosystems. Idea
Group Inc., 2006.
[Wuensche, 2005] A. Wuensche; Discrete dynamic lab (ddlab). http://www.ddlab.com.
November 2005.
-Back to top
Are global epidemics predictable? The
SARS case study.
by
Vittoria Colizza, Institute for Scientific Interchange, Turin,
Italy
The global spread of the severe acute respiratory syndrome (SARS)
epidemic has clearly shown the importance of considering the long
range transportation networks in the understanding of emerging diseases
outbreaks. Here I will present a large-scale stochastic computational
approach for the study of the global spread of emerging infectious
diseases which explicitly incorporates real world transportation
networks and census data. The case study of the SARS world-wide
epidemic is considered for risk assessment analysis and comparison
with historical data. The model allows probabilistic predictions
on the likelihood of country outbreaks and their magnitude. The
level of predictability provided by the simulations can be quantitatively
analyzed and related to the appearance of robust epidemic pathways
which represent the most probable routes for the spread of the disease.
-Back to top
Cellular automaton modelling of spatio-temporal
pattern formation in interacting cell systems
by
Andreas Deutsch, Technische Universität Dresden
Examples of spatio-temporal pattern formation are life cycles of
bacteria and social amoebae, embryonic tissue formation, wound healing
or tumour growth. Thereby, development of a particular spatio-temporal
"multi-cellular" pattern may be interpreted as cooperative
phenomenon emerging from an intricate interplay of local (e.g. by
adhesion) and non-local (e.g. via diffusing signals) cell interactions.
What are cooperative phenomena in interacting cell systems and how
can they be studied?
Mathematical models are required for the analysis of cooperative
phenomena. Typical modeling attempts focus on a macroscopic perspective,
i.e. the models (e.g. partial differential equations) describe the
spatio-temporal dynamics of cell concentrations. More recently,
cell-based models have been suggested in which the fate of each
individual cell can be tracked. Cellular automata are discrete dynamical
systems and may be utilized as cell-based models.
Here, we analyze spatio-temporal pattern formation in cellular
automaton models of interacting discrete cells. We introduce lattice-gas
cellular automata and a cellular automaton based on an extended
Potts model that allows to consider cell shapes. Model applications
are bacterial pattern formation and tumour growth.
-Back to top
A Cellular Automata Approach for
Discrete-Time Distributed Parameters Systems
by
Samira El Yacoubi, Univ. of Perpignan, France
The prediction of the evolution of complex systems and the possibility
to influence and control their behaviour in a dynamic environment
is of fundamental importance. Spatio-temporal systems involving
inputs and outputs (controls and observations), called distributed
parameter systems are traditionally modelled by partial differential
equations (PDE's). In the last decades, a wide literature has been
devoted to the study of both continuous and discrete time linear
dynamical systems (infinite-dimensional and finite-dimensional cases).
The purpose of this paper is to present cellular automata as discrete-time
distributed parameter systems. The description is given in a similar
way than for PDE's or strongly continuous semi-groups operators.
In the literature cellular automata are viewed as simple models
for simulation of complex systems. We introduce the notions of control
and observation in cellular automata in order to allow analysis
of their behaviour using tools of systems theory.
-Back to top
Prolegomena to a theory of asynchronous
and probabilistic cellular automata
by
Nazim Fatès
LORIA, INRIA, Nancy, France
What is the influence of the updating scheme in the temporal evolution
of a cellular automaton ? To which extent is a cellular automaton
"robust" or "sensitive" to the perturbation
of its updating scheme ? Are asynchronous or probabilistic cellular
noisy versions of their deterministic counterparts or do they offer
new perspectives in understanding complex systems ?
Although these questions were posed in the early 1980s, it appears
that they have given birth to only a few publications so far. The
first part of my presentation is intended as a recollection of the
state of the art : experimental approaches will be presented, followed
by an analytical classification and then by a study of the phase
transitions observed on elementary cellular automata.
In a second time, I will present a rather prospective point of
view, showing how the previous tools may shed new light on probabilistic
cellular automata, especially focusing on results established by
Fuks et al. To conclude, I will briefly use some tools described
in the talk to analyse a bio-inspired model that couples reaction-diffusion
and chemotaxis.
-Back to top
Self-organized criticality and coevolution
of network structure and dynamics
by
Janusz A. Holyst
Faculty of Physics and Center of Excellence for Complex Systems
Research, Warsaw University of Technology, Koszykowa 75, PL-00-662
Warsaw , Poland
Coauthors: Piotr Fronczak and Agata Fronczak
We investigate by numerical simulations, how the avalanche dynamics
of the Bak-Tang-Wiesenfeld sandpile model can induce emergence of
scale-free networks and how this emerging structure affects dynamics
of the system. We show that an interplay between dynamics and structure
leads to self-organization in which the shapes of avalanche distribution
and degree distribution become identical. We suggest that the observed
phenomenon can be used to explain evolution of scientific collaboration.
References
Piotr Fronczak, Agata Fronczak, and Janusz A. Holyst, PHYSICAL
REVIEW E 73, 046117 (2006)
-Back to top
On the influence of symmetries and neighborhoods
on constructing two dimensional number-conserving cellular automata
rules
by
Katsunobu Imai
Hiroshima Univeristy
Coauthors: Naonori Tanimoto
A number-conserving cellular automaton is a cellular automaton
such that all states of cells are represented by integers and the
total number of its configuration is conserved throughout its computing
process. It is characterized by the movement of particles and can
be thought as a kind of modelization of the physical conservation
law of mass or energy.
In this talk, we discuss the influence of symmetric conditions
and the shape of neighborhoods on constructing two dimensional number-conserving
cellular automata rules.
-Back to top
Simple Dynamics for Complex Systems
by
Raymond Kapral
Chemical Physics Theory Group, Department of Chemistry, University
of Toronto
The investigation of the dynamics of complex systems often requires
knowledge of their time evolution on physically relevant long distance
and time scales. This is a challenging task for computer simulation.
This fact has prompted the development of a number of different
cellular automaton and coarse-grain molecular dynamics methods.
In this talk a highly simplified model of the dynamics, called multiparticle
collision dynamics or stochastic rotation dynamics, will be described.
It idealizes the nature of the collisions in the system but retains
the most important features of full molecular dynamics, namely,
it conserves mass, momentum and energy and preserves phase space
volumes. Because of its simplicity, the statistical mechanics of
systems with such dynamics can be analysed in detail, the macroscopic
Navier-Stokes equations can be derived and transport properties
can be computed easily. The mesoscopic dynamics can be combined
with molecular dynamics to study polymer, biomolecular and colloidal
dynamics, as well as a variety of other systems. The staistical
mechanical basis of the model will be discussed and its utility
illustrated by applications to conformational dynamics in solution,
dynamics of colloidal particles, reactions in crowded cells and
self-propelled motion.
-Back to top
Ensemble averageability in network spectra: complex yet similar
networks
by
Dong-Hee Kim
Department of Physics and Astronomy, Northwestern University
Coauthors: Adilson E. Motter
The extreme eigenvalues of connectivity matrices govern the influence
of the network structure on a number of network dynamical processes.
A fundamental open question is whether the eigenvalues of large
networks are well represented by ensemble averages. Here we investigate
this question explicitly and validate the concept of ensemble averageability
in random scale-free networks by showing that the ensemble distributions
of extreme eigenvalues converge to peaked distributions as the system
size increases. We discuss the significance of this result using
synchronization and epidemic spreading as example processes.
-Back to top
Traffic flow based on safety embedded
notions
by
María Elena Lárraga
Universidad Nacional Autónoma de México, 04510, Coyoacán
D.F., México. On leave from Universidad Autónoma del
Estado de Morelos
Coauthors: Luis Álvarez-Icaza
An improved one-dimensional CA (Cellular Automaton) traffic model
to describe the highway traffic under the periodic boundary conditions
is presented. A new set of rules is proposed to better capture driver
reactions to traffic that are intended to preserve safety on the
highway. As a result, three distances that represent the safety
distance that a driver must have with respect to preceding vehicle
if it is going to decelerate, keep its velocity or accelerate, were
included in the new model. Drivers behavior is derived from an analysis
that determines the most appropriate action for a vehicle based
on its headway and the synchronous motion of the vehicle ahead of
it. In this way, the velocity setting rules depend not only on the
relative velocity of neighbor vehicles, they now take into account
their relative distances. The model preserves simplicity of CA rules
and at the same time makes the results closer to real highway behavior.
Simulation results exhibit the three states observed in real traffic
flow: Free-flow states, synchronized states, and stop-and-go states.
Besides, it is found that there exists the metastability of traffic
flow in the neighborhood of critical density under different initial
conditions.
Simulating the spread of infectious disease
using a spatial, agent based model
by
Pietro Lio'
University of Cambridge
Most mathematical models for the spread of disease use differential
equations based on uniform mixing assumptions or ad hoc models for
the contact process. Using actual census, family age structure,
age infection propensity, land-use and population-mobility data
and information on contact network among people we have explored
the validity of a variety of models of disease propagation when
applied to the influenza epidemic in UK. The models consider that
flu season begins with preschoolers, i.e. that 3- and 4-year-olds
are early spreaders of influenza because of the preschool setting.
Those are kids who don't yet cover their sneezes and are apt to
pick their noses, "hotbeds of infection." Next as spreaders
are school-age children Older children may have better hygiene,
but also represent a much larger and more active population in the
community, giving them greater contact with the elderly who are
most vulnerable to influenza. High-risk people include those 65
or older; babies and toddlers ages 6-23 months; anyone with a chronic
illness such as heart or lung disease; pregnant women; and caregivers
of high-risk patients. We analyse the relative merits of several
proposed mitigation and targeted targeted vaccination strategies
combined with early detection without resorting to mass vaccination
of a population.
-Back to top
On cellular automata modeling of cardiac
pacemaker
by
Danuta Makowiec
Institute of Theoretical Physics and Astrophysics, Gdansk University
Coauthors: Lukasz Redlarski
The cardiac pacemaker is a group of cells within the heart, called
the sinoatrial (SA) node, that initiates the rhythmic beating of
the heart - electrical activity of the SA node is propagated to
the rest of the heart. The cells of SA node are characterized by
intrinsic dynamics which switches each cell from the passive to
active state periodically. The synchronization of the activation
of the cells is a required attribute to produce the electrical activity
of the SA node at a regular rate. Mechanisms by which cells with
different intrinsic rates maintain this synchronization is awaited
for explanation. The SA node is usually modeled by systems of coupled
differential equations.
We will present an ongoing research that aims at revealing the
SA node electrical activity by a system of stochastic cellular automata
with intrinsic oscillating dynamics.
-Back to top
Strutural properties of complex networks
by
José Mendes
University of Aveiro
Coauthors: S. N. Dorogovtsev and A.V. Goltsev
The k-core decomposition was recently applied to a number of real-world
networks. Rich k-core architectures of real networks were revealed.
We find the structure of k-cores, their sizes, and their birth points
— the bootstrap percolation thresholds. I will show a derivation
of exact equations describing the k-core organization of a randomly
damaged uncorrelated network with an arbitrary degree distribution.
This allows us to obtain the sizes and other structural characteristics
of k-cores in a variety of damaged and undamaged random networks
and find the nature of the k-core percolation in complex networks.
These general results will be applied to the classical random graphs
and to scale-free networks, in particular, to empirical router-level
Internet maps.
-Back to top
A classification scheme of fuzzy
cellular automata with applications to ECA
by
Angelo B. Mingarelli
Carleton University
Using methods from the theory of fuzzy cellular automata as formulated
over the past decade we present an analytic comprehensive derivation
of the classification of elementary cellular automata into the various
classes (I-IV) as defined originally by Wolfram. Since these fuzzy
cellular automata include the usual Boolean ones in the limit, we
can derive, in part, the Wolfram classification scheme. We do this
by introducing a special function dubbed the G-function whose values
define the various classes. It is remarkable that the classes so
defined contain, with few exceptions, Wolfram's original classification
and share many common characteristics with other classes so defined.
-Back to top
On universal 1-d reversible cellular
automata
by
Kenichi Morita
Hiroshima University
So far, several methods for proving computation-universality of
one-dimensional reversible cellular automata have been proposed.
They are to simulate reversible Turing machines, to simulate cyclic
tag systems, and others. In this talk, we compare these methods,
and investigate new methods to obtain simple universal 1-d reversible
cellular automata.
-Back to top
Phase Space Equivalences of Sequential
Dynamical Systems
by
Henning S. Mortveit
Virginia Tech
Coauthors: Matthew Macauley, UCSB
Sequential dynamical systems (SDS) belong to the class of graph
dynamical systems. SDS are defined over a finite graph where each
vertex has a state and an update function. The system update is
asynchronous and is specified by a word over the vertex set of the
graph. This presentation will give an overview of phase space characterizations
of these systems in terms of their graphs, update orders and functions.
Recent results on attractor equivalence will be presented, but notions
and results on functional equivalence and dynamical equivalence
will be reviewed.
-Back to top
Evolutionary computation techniques
to look for cellular automata rules
by
Pedro P.B. de Oliveira
Universidade Presbiteriana Mackenzie, Brazil
The density classification task and the parity problem have been
paradigmatic benchmark problems in the cellular automata literature
related to searching for rules able to exhibit a given global behaviour.
In these two problems, the rule must decide about global properties
of the number of 1-bits in the initial configuration of binary cellular
automata. Here, aspects of various evolutionary computation techniques
I have worked with during the past years, with several collaborators,
will be reviewed, in the context of the aforementioned problems,
in terms of their usage primarily to search for good individual
rules with radius 3, but also for determining adequate temporal
sequences and spatial arrangements of elementary rules.
-Back to top
Emergent Defect Dynamics in Two-dimensional
Cellular Automata
by
Marcus Pivato
Trent University
Coauthors: Martin Delacourt (École Normale Supérieure
de Lyon)
Many cellular automata (CA) exhibit `emergent defect dynamics'
(EDD): under the action of the CA, a generic initial configuration
rapidly condenses into a collection of large, homogeneous domains
exhibiting some regular pattern, punctuated by small, irregular
regions called `defects', which propagate through space and occasionally
collide or interact. All known `naturally occuring' examples of
EDD are in one-dimensional CA (e.g. elementary CA numbers 18, 22,
54, 62, 110, 184). However, much of the theoretical machinery we
have developed to understand EDD makes just as much (or more) sense
in higher dimensions, despite the lack of good examples. We have
recently conducted a large-scale computer search for EDD in the
space of two-dimensional CA. We will discuss some of the interesting
examples uncovered in this search.
Entropy and Chaos in a Discrete Hydrodynamical
System
by
Raul Rechtman
Centro de Investigacion en Energia, Universidad Nacional Autonoma
de Mexico
Coauthors: Franco Bagnoli, University of Florence (Italy)
We investigate the dynamical properties of a lattice gas cellular
automata, which is a discrete dynamical system with hydrodynamical
behavior. We define the discrete maximum Lyapunov exponent by exploiting
the idea of of Boolean derivatives. Due to the discreteness of the
system, we are able to measure the Boltzmann's H function, that
in equilibrium approximates the entropy of the system. We show that
both in equilibrium and out of equilibrium, the Lyapunov exponent
and the Boltzmann's H function are (roughly) proportional. We can
therefore illustrate in this simple toy model the correspondence
between statistical and dynamical indicators.
-Back to top
Transformations of Binary Valued Additive
Rules
by
Burton Voorhees
Athabasca University
I discuss a class of transformations acting on the space of binary
valued additive cellular automata rules. This class includes reversals,
duality (binary complementation), and index transformations. The
rule space is partitioned into interesting equivalence classes.
Within these classes, subclasses of rules with isomorphic state
transition diagrams appear. A connection to rule representation
in terms of polynomials in roots of unity described.
The Cell-DEVS formalism: modeling and
simulating discrete-event cell spaces
by
Gabriel Wainer
Carleton University, Dept. of Systems and Computer Engineering
Grid-shaped models have gained popularity and they have received
a tremendous impulse in the recent years. The use of a discrete
time base constrains the precision of the model and their performance,
being unable to adequately describe most of existing physical systems
(which are asyncrhonous in nature).
The Cell-DEVS formalism is based on DEVS, a continuous time technique.
The goal of Cell-DEVS is to build discrete-event cell spaces, improving
their definition by making the timing specification more expressive.
As DEVS models have hierarchical and modular specification (and
different formalisms - including Petri Nets, StateCharts, Queuing
Networks, Finite State Machines, etc. were successfully mapped into
DEVS), we have a mechanism to build cellular models that can interact
with others described using different modeling techniques, providing
a multiformalism/multimodeling approach.
DEVS and Cell-DEVS formalisms were implemented in a modeling and
simulation tool (CD++), which was successfully used to develop different
types of systems: biological (ecological models, heart tissue, ant
foraging systems, fire spread, etc.), physical (diffusion, binary
solidification, excitable media, surface tension, etc.), artificial
(robot trajectories, traffic problems, heat seeking devices, etc.),
and others.
In this talk, we will introduce the main characteristics of the
formalisms, and will show how to model complex cell spaces in an
asynchronous environment. We will focus in showing how the application
of these techniques can improve model definitionand in how to create
models that can be executed automatically in a parallel environment
without any modifications to the original models. We will present
different examples of application, and discuss open research issues
in this area.
Back to top
Applying cellular automata in topology
control of wireless sensor networks
by
Jian Yuan
Department of Electronic Engineering, Tsinghua University, Beijing
100084, China
Coauthors: Wenzhu Zhang, Zhe Yu, Zanxin Xu, Xiuming Shan
Since sensors are constrained by limited energy and small communication
diameters, topology control is a primary problem of wireless sensor
network engineering. In this paper, we propose a cellular automaton
(CA)-based model for addressing the topology control problem of
minimizing nodal transmission power with guarantees of network connectivity.
Our CA-based model can capture well the essential features of “local-global”
behaviors of sensor networks. By defining metrics for network coverage
and connectivity, we better understood how to design local interaction
rules to achieve desired emergent properties.
Back to top
