July 12, 2024

Automata 2007
13th International Workshop on Cellular Automata

August 27-29, 2007
The Fields Institute

Cellular Automata with Memory
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
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
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.


[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). November 2005.

-Back to top

Are global epidemics predictable? The SARS case study.
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
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
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
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
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.


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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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