Skip to main content
main-content
Top

Table of Contents

Frontmatter

Theoretical Results on Cellular Automata

Information Transfer among Coupled Random Boolean Networks

Information processing and information flow occur at many levels in the course of an organism’s development and throughout its lifespan. Biological networks inside cells transmit information from their inputs (e.g. the concentrations of proteins or other signaling molecules) to their outputs (e.g. the expression levels of various genes). Moreover, cells do not exist in isolation, but they constantly interact with one another. We study the information flow in a model of interacting genetic networks, which are represented as Boolean graphs. It is observed that the information transfer among the networks is not linearly dependent on the amount of nodes that are able to influence the state of genes in surrounding cells.

Chiara Damiani, Stuart A. Kauffman, Roberto Serra, Marco Villani, Annamaria Colacci

Open Environment for 2d Lattice-Grain CA

An open cellular automata (CA) environment applied to the simulation of two-dimensional granular flows is presented herein. The CA belongs to the family of so-called “lattice-grain” (cellular) automata (LGrA) with one particle per cell. The time evolution is governed by a “request-exchange” synchronous mode which simulates a two-stage interaction-advection process. The transition rule follows a simple logic including three physical components: an external field, a set of kinematical exclusion rules and an inertial effect. After a short presentation of the CA logic, this paper describes the open user interface structured onto and emphasizes the versatility of the model.

Guillaume Cottenceau, Dominique Désérable

All-to-All Communication with CA Agents by Active Coloring and Acknowledging

We modeled a multi-agent system as a two-dimensional Cellular Automata and searched for a rule in order to solve the all-to-all communication task in shortest time. The rule contains two finite state machines (FSM) controlling the behavior of the uniform agents. The moving FSM controls the moving actions and the color FSM controls the changing of the cell’s color. Colors are used for indirect communication. In addition the agents receive an acknowledgment whenever they meet and communicate successfully. The FSMs were evolved by a genetic algorithm. It could be shown that acknowledging and especially coloring increases the performance of the agents. Certain initial configurations cannot be solved without coloring. Even with coloring, symmetric configurations cannot be solved when the initial colors are the same.

Patrick Ediger, Rolf Hoffmann

The Sandpile Model: Parallelization of Efficient Algorithms for Systems with Shared Memory

Having resisted successful parallelization so far, this paper shows how the sandpile cellular automaton can be efficiently parallelized on multicore computers with shared memory. New algorithms for both the sequential and parallel case are being introduced. Implementations in Java show a good speed-up which increases with the grid size.

Sebastian Frehmel

Theory and Application of Equal Length Cycle Cellular Automata (ELCCA) for Enzyme Classification

A special class of

n

cell null boundary invertible three neighborhood CA referred to as Equal Length Cycle CA (ELCCA) is proposed in this paper to represent the features of

n

bit symbol strings. Necessary and sufficient conditions for generation of ELCCA has been reported. A specific set of ELCCA cycles are selected by employing the mRMR algorithm [2] popularly used for feature extraction of symbol strings. An algorithm is next developed to classify the symbol strings based on the feature set extracted. The proposed CA model has been validated for analyzing symbol string of biomolecules referred to as Enzymes. These biomolecules are classified on the basis of the catalytic reaction they participate. The symbol string classification algorithm predicts the class of any input enzyme with accuracy varying from 90.4% to 98.6%. Experimental results have been reported for 22800 enzymes with wide variation in species.

Soumyabrata Ghosh, Tirthankar Bachhar, Nirmalya S. Maiti, Indrajit Mitra, P. Pal Chaudhuri

Cellular Automata Model for Size Segregation of Particles

This paper deals with the study of size segregation of particles where the size difference causes characteristic movement of particles inside granular media according to the induced vibration. In this study, segregation of particles due to the difference in size is simulated using Cellular Automata. A connected lattice automaton is introduced in the model, so that the variation of particle sizes as well as geometrical arrangement between particles can be represented. The Cellular Automata model can produce various characteristics which are observed in the actual granular systems. Furthermore, it is known from both numerical and experimental observations that the segregation progress is dependent on the amplitude of excitation as well as the particle size ratio.

Toshihiko Komatsuzaki, Yoshio Iwata

Convex Hulls on Cellular Automata

In the cellular automata domain, the discrete convex hull computation rules proposed until now only deal with a connected set of seeds in infinite space, or with distant set of seeds in finite space. We present a cellular automata rule that constructs the discrete convex hull of arbitrary set of seeds in infinite spaces. The rule is expressed using intrinsic and general properties of the cellular spaces, considering them as metric spaces. In particular, this rule is a direct application of metric Gabriel graphs. This allows the rule and its components to be used on all common 2D and 3D grids used in cellular automata.

Luidnel Maignan, Frédéric Gruau

Square Kufic Pattern Formation by Asynchronous Cellular Automata

Algorithms Design for pattern formation is an interesting science and many investigations are done about it. In this paper, a novel pattern formation method using asynchronous cellular automata for generating square Kufic patterns is explored. Square Kufic is a kind of script that is used in many Islamic architecture buildings. In our new method, cellular automata rules causing a specified kind of pattern are manually extracted. The implementation results show this fact by using some special patterns in replicators.

Seyyed Amir Hadi Minoofam, Azam Bastanfard

Modeling and Simulation with Cellular Automata

Development and Calibration of a Preliminary Cellular Automata Model for Snow Avalanches

Numerical modelling is a major challenge in the prevention of risks related to the occurrence of catastrophic phenomena. A Cellular Automata methodology was developed for modelling large scale (extended for kilometres) dangerous surface flows of different nature such as lava flows, pyroclastic flows, debris flows, rock avalanches, etc. This paper presents VALANCA, a first version of a Cellular Automata model, developed for the simulations of dense snow avalanches. VALANCA is largely based on SCIDDICA-SS2, the most advanced model of the SCIDDICA family developed for flow-like landslides. VALANCA adopts several of its innovations: outflows characterized by their mass centre position and explicit velocity. First simulations of real past snow avalanches occurred in Switzerland in 2006 show a satisfying agreement, concerning avalanche path, snow cover erosion depth and deposit thickness and areal distribution.

Maria Vittoria Avolio, Alessia Errera, Valeria Lupiano, Paolo Mazzanti, Salvatore Di Gregorio

Tracking Uncertainty in a Spatially Explicit Susceptible-Infected Epidemic Model

In this paper we conceive an interval-valued continuous cellular automaton for describing the spatio-temporal dynamics of an epidemic, in which the magnitude of the initial outbreak and/or the epidemic properties are only imprecisely known. In contrast to well-establish-ed approaches that rely on probability distributions for keeping track of the uncertainty in spatio-temporal models, we resort to an interval representation of uncertainty. Such an approach lowers the amount of computing power that is needed to run model simulations, and reduces the need for data that are indispensable for constructing the probability distributions upon which other paradigms are based.

Jan M. Baetens, Bernard De Baets

A Proximal Space Approach for Embedding Urban Geography into CA Models

In the great majority of urban models based on Cellular Automata (CA), the concept of proximity is assumed to reflect two fundamental sources of spatial interaction: (1) the accessibility of places and (2) the distance “as the crow flies”. While the geographical space defined by the latter clearly has an Euclidean representation, the former, based on the accessibility, does not admit such a regular representation. Very little operational efforts have been undertaken in CA-based urban modelling to investigate and provide a more coherent and cogent treatment of such irregular geometries, which indeed are essential and crucial feature of urban geography. In this paper, we suggest an operational approach – entirely based on cellular automata techniques – to model the complex topology of proximities arising from urban geography, and to entangle such proximity topology with a CA model of spatial interactions.

Ivan Blecic, Arnaldo Cecchini, Giuseppe A. Trunfio

Bone Remodelling: A Complex Automata-Based Model Running in BioShape

Bone remodelling, as many biological phenomena, is inherently multi-scale, i.e. it is characterised by interactions involving different scales at the same time. At this aim, we exploit the

Complex Automata

paradigm and the

BioShape

3D spatial simulator respectively (i) for describing the bone remodelling process in terms of a 2-scale aggregation of

uniform

Cellular Automata

coupled by a

well-established

composition pattern, and (ii) for executing them in a

uniform

and integrated way in terms of shapes equipped with perception and movement capabilities.

On the one hand, the proposed model confirms the high expressiveness degree of Complex Automata to describe multi-scale phenomena. On the other hand, the possibility of executing such a model in

BioShape

highlights the existence of a general mapping - from Complex Automata into the

BioShape

native modelling paradigm - also enforced by the fact that both approaches result to be suitable for handling different scales in a uniform way, for including spatial information and for bypassing inter-scale homogenization problems.

Diletta Cacciagrano, Flavio Corradini, Emanuela Merelli

CANv2: A Hybrid CA Model by Micro and Macro-dynamics Examples

Cellular Automata (CA), one of the most challenging computational paradigms in microscopic and macroscopic complex systems simulation, can be successfully addressed also by using a modified CA classical approach. In this contribution we discuss related aspects in applying the CANv2 approach in examples of micro and macro dynamics such as: superconductive devices and forest fire simulation. Advantages and limitations are introduced when both microscopic and macroscopic dynamics are taken into account justifying the introduction of hybrid components between single cellular automata, i.e. a network in which global behavior and local interactions can coexist with side effects in computational parallelism addressing.

Claudia R. Calidonna, Adele Naddeo, Giuseppe A. Trunfio, Salvatore Di Gregorio

Simulation of Traffic Flow at a Signalised Intersection

We have developed a Nagel-Schreckenberg cellular automata model for describing of vehicular traffic flow at a single intersection. A set of traffic lights operating either in fixed-time or traffic adaptive scheme controls the traffic flow. Closed boundary condition is applied to the streets each of which conduct a uni-directional flow. Extensive Monte Carlo simulations are carried out to find the model characteristics. In particular, we investigate the dependence of the flows on the signalisation parameters.

Somayyeh Belbasi, M. Ebrahim Foulaadvand

A Novel Method for Simulating Cancer Growth

We propose probabilistic cellular automata on a square lattice for simulating the dynamic of cancer growth in a reaction-diffusion frame. In the reaction step each cancerous cell can proliferate, be quiescent, or die due to apoptosis or necrosis phenomenon. The three-state Potts model is used for calculating the probabilities in the reaction step. We consider the effect of nutrient in the tumor growth in order to improve the precision of the model. We use a simple and suitable method for the diffusion step to simplify movement of cells and nutrient in the model. In the diffusion step the lattice is partitioned by 3×3 blocks. In each block we count the number of different types of cells and redistribute them in the block. In the next time step, each block will be shifted one row down and one column to the right and the operation will be continued. The redistribution step for nutrient molecules is same as cells. It is shown tumor growths asymmetrically toward nutrient source. It has been shown such a simple model could simulate tumor growth with good accuracy, which is based on the well known physical ground i.e. the three-state Potts model.

Mehrdad Ghaemi, Omid Naderi, Zahra Zabihinpour

Towards Cellular Automata Football Models with Mentality Accounting

In this paper we deal with mathematical modeling of team sport games based on cellular automata (CA). We describe some developments of CA models of football. Presumable learning and optimization problems in team modeling based on CA are discussed. Some general problems are discussed which are related to the accounting of mentality of game participants.

Alexander Makarenko, Dmitriy Krushinski, Anton Musienko, Boris Goldengorin

The Complexity of Three-Dimensional Critical Avalanches

In this work we study the complexity of the three-dimensional sandpile avalanches triggered by the addition of two critical configurations. We prove that the algorithmic problem consisting in predicting the evolution of three dimensional critical avalanches is the hardness core of the three-dimensional Abelian Sandpile Model. On the other hand we prove that three-dimensional critical avalanches are superlinear long on average. It suggests that the prediction problem is superlinear-hard on average.

Carolina Mejía, J. Andrés Montoya

Using Cellular Automata on a Graph to Model the Exchanges of Cash and Goods

This paper investigates the behaviors and the properties of a “Give and Take” cellular automaton on a graph. Using an economical metaphor, this model implements the exchange of cash against goods, among the nodes of a graph

G

, with a local pricing mechanism. During the time evolution of this model, the strongly connected components (SCC) emerge, mimicking the creation of independent sub-markets. In the steady state, each SCC is characterized by a unique price obeying the supply and demand law for that sub-market. We also show that the distributions of cash and goods are proportional to the indegree of the cells, reproducing a Zipf’s law of wealth distribution in case of a scale-free graph topology.

Ranaivo Mahaleo Razakanirina, Bastien Chopard

Montebello: A Metapopulation Based Model of Carcinogenesis

The dynamics of the lengthy process by which tumors arise from normal tissues is not well understood. We developed a stochastic cellular automaton model based on the ecological concept of metapopulations to explore the role of mutation, exogenous disturbance, and selection in the genesis of tumors. The operation of the model shows how disturbances (e.g. inflammation) acting on tissues can cause tumors by modifying the dynamics among metapopulations of cells. Simulations demonstrate that disturbance, without change in mutation rates, can drive tumor formation. Changes in the distribution of genetic alterations among metapopulations in the tissue can predict the emergence of a tumor, thus providing a measure of risk. Modifying the disturbance regimen can prevent the emergence of tumors. Thus, the model provides insights into how mutation rates and disturbance interact in the causation of cancer, and illustrate how measuring metapopulation distributions can provide surrogate end points for preventive intervention.

David Tuck, Willard Miranker, Jose Costa

CA Dynamics, Control and Synchronization

Towards Generalized Measures Grasping CA Dynamics

In this paper we conceive Lyapunov exponents, measuring the rate of separation between two initially close configurations, and Jacobians, expressing the sensitivity of a CA’s transition function to its inputs, for cellular automata (CA) based upon irregular tessellations of the

n

-dimensional Euclidean space. Further, we establish a relationship between both that enables us to derive a mean-field approximation of the upper bound of an irregular CA’s maximum Lyapunov exponent. The soundness and usability of these measures is illustrated for a family of 2-state irregular totalistic CA.

Jan M. Baetens, Bernard De Baets

Synchronization and Control of Cellular Automata

We study the problem of targeted synchronization of

stable chaotic

extended systems,

i.e.

, systems which are not chaotic in the usual sense, but are unpredictable for finite perturbations. Examples are cellular automata, which are completely discrete dynamical systems. We show that the usual approach may lead to counter intuitive results, but that it is possible to exploit the characteristics of the system in order to reduce the distance between two replicas with less control.

Franco Bagnoli, Samira El Yacoubi, Raúl Rechtman

Discovery by Genetic Algorithm of Cellular Automata Rules for Pattern Reconstruction Task

This paper presents results of the study on application of two-dimensional, three-state cellular automata with von Neumann neighborhood to perform pattern reconstruction task. Searching efficient cellular automata rules is conducted with use of a genetic algorithm. Experiments show a very good performance of discovered rules in solving the reconstruction task despite minimum radius of neighborhood and only partial knowledge about neighborhood states available. The paper also presents interesting reusability possibilities of discovered rules in reconstructing patterns different but similar to ones used during artificial evolution.

Anna Piwonska, Franciszek Seredynski

Addition of Recurrent Configurations in Chip Firing Games: Finding Minimal Recurrent Configurations with Markov Chains

Generalizing the Abelian Sandpile Model by Bak, Tang and Wiesenfeld to general undirected graphs, one gets a variation of the Chip Firing Game intoduced by Chung and Ellis in 2002, which still contains most of the nice algebraic properties of the Abelian Sandpile Model. Particularly the group structure of the recurrent configurations is retained.

Using a Markov Chain, we show how a pair consisting of one minimal recurrent configuration and one nearly minimal recurrent configuration can be constructed whose sum is the same as the sum of a given pair of recurrent configurations.

Computer simulations of this Markov Chain for the Abelian Sandpile Model suggest that the number of steps needed to reach a final pair usually is proportional to the width of the grid, but can become proportional to the square of the width if one chooses particular configurations.

Matthias Schulz

A Seven-State Time-Optimum Square Synchronizer

The firing squad synchronization problem on cellular automata has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms have been proposed for not only one-dimensional arrays but two-dimensional arrays. In the present paper, we propose a seven-state optimum-time synchronization algorithm that can synchronize any square arrays of size

n

×

n

with a general at one corner in 2

n

 − 2 steps, which is a smallest realization of time-optimum square synchronizer known at present. The implementation is based on a new, simple zebra-like mapping scheme which embeds synchronization operations on one-dimensional arrays onto square arrays.

Hiroshi Umeo, Keisuke Kubo

Codes and Cryptography with Cellular Automata

Null Boundary 90/150 Cellular Automata for Multi-byte Error Correcting Code

Cellular Automata(CA) is a well known tool to generate byte error correcting code. In this paper, we propose a CA-based multi-byte Error Correcting Code (ECC) which overcomes the weaknesses and limitation of existing scheme. As a case study three and four bytes ECC are discussed in detailed. A complete decoding algorithm of CA-based 3-byte error correcting code is presented in this work. Proposed 3-byte ECC scheme can correct errors when errors are distributed within information and check bytes or concentrated in any one of them. In case of CA-based 4-byte ECC, at most 4-byte errors can be corrected if all the errors are concentrated in information or check bytes.

Jaydeb Bhaumik, Dipanwita Roy Chowdhury, Indrajit Chakrabarti

Generating Cryptographically Suitable Non-linear Maximum Length Cellular Automata

Non-linearity as well as randomness are essential for cryptographic applications. The Linear Cellular Automata (CA), particularly maximum length CA, are well known for generating excellent random sequences. However, till date, adequate research has not been done to generate maximal length Cellular Automata using non-linear rules; a fact that limits the application of CA in cryptography. This paper devices a method to generate non-linear Maximal Length Cellular Automata. It manipulates the number of clock cycles, based on inputs, in a maximum length additive CA and generates a series of non-linear boolean mappings. It shows that the bit streams generated in this manner are highly non-linear and pass all the statistical tests for randomness. These maximum length CA can be used as a non-linear primitive in cryptographic applications.

Sourav Das, Dipanwita Roy Chowdhury

Chaotic Cellular Automata with Cryptographic Application

In this paper, a method of generating cryptographic sequences based on discrete linear chaotic cellular automata is presented. The importance of the proposal is due to the fact that such cryptographic sequences are also output sequences of a nonlinear keystream generator known as Generalized Self-Shrinking Generator. Moreover, such a keystream generator is still considered secure in symmetric cryptography. Thus, it must be noticed that the linearity of the proposed chaotic model based on additive one-dimensional cellular automata might be used to mount a cryptanalytic attack against such a nonlinear generator.

Amparo Fúster-Sabater, Pino Caballero-Gil

d-Monomial Tests of Nonlinear Cellular Automata for Cryptographic Design

Pseudorandom generation is a key to any cryptographic application. Linear Cellular Automata are known as good pseudorandom generators. However, for cryptographic applications nonlinearity is essential for its security. But, nonlinear Cellular Automaton shows high correlation between the input to the automaton and its generated sequence. Hence, for cryptography Cellular Automata rules need to be nonlinear as well as satisfy additional properties. With this motivation, in this paper, we analyze nonlinear Cellular Automata with a newly developed statistical measure called

d

-monomial test. Finally, we propose a process of

d-monomial characteristics addition

to get cryptographically suitable Cellular Automata.

Sandip Karmakar, Debdeep Mukhopadhyay, Dipanwita Roy Chowdhury

Programmable Cellular Automata (PCA) Based Advanced Encryption Standard (AES) Hardware Architecture

This paper reports an AES (Advances Encryption Standard) hardware architecture based on Programmable Cellular Automata (PCA) operated with a program. Verilog code has been designed for PCA and associated hardware modules to realize the AES functions. The PCA replaces the irregular logic circuit necessary for hardwired implementation of AES. The design has been simulated on Xilinx platform using ISE simulator.

Nirmalya S. Maiti, Soumyabrata Ghosh, Biplab K. Shikdar, P. Pal Chaudhuri

Exhaustive Evaluation of Radius 2 Toggle Rules for a Variable-Length Cryptographic Cellular Automata-Based Model

A cellular automata (CA) model in cryptography is investigated. A previous work analyzed the usage of reverse algorithm for pre-image computation as an encryption method. The main conclusion was that the simple adoption of such method is not viable, since it does not have 100% of guarantee of pre-image existence. A new approach was proposed that uses extra bits when the pre-image computation is not possible. It is expected that in practice few failures happens and the ciphertext size will be close to the plaintext. Encryption always succeeds and the final length of the ciphertext is not fixed. We better investigate the secret key specification by using a more representative set formed by all radius 2 right-toggle rules, totalizing 65536 rules. An exhaustive analysis of this rule space has shown that using adequate specification the method has a good protection against differential cryptanalysis and a small increase in ciphertext length.

Gina M. B. Oliveira, Luiz G. A. Martins, Leonardo S. Alt, Giordano B. Ferreira

Cellular Automata and Networks

Network Decontamination with Temporal Immunity by Cellular Automata

Network decontamination (or disinfection) is a widely studied problem in distributed computing. Network sites are assumed to be contaminated (e.g., by a virus) and a team of agents is deployed to decontaminate the whole network. In the vast literature a variety of assumptions are made on the power of the agents, which can typically communicate, exchange information, remember the past, etc.

In this paper we consider the problem in a much weaker setting; in fact we wish to describe the global disinfection process by a set of cellular automata local rules without the use of active agents. We consider the grid, which is naturally described by a 2-dimensional cellular automata, and we devise disinfection rules both in the common situation where after being disinfected a cell is prone to re-contamination by contact, and in a new setting where disinfection leaves the cells immune to recontamination for a certain amount of time (

temporal immunity

). We also distinguish between Von Neuman and Moore neighborhood, showing that, not surprisingly, a bigger neighborhood allows for a more efficient disinfection.

Yassine Daadaa, Paola Flocchini, Nejib Zaguia

Characterization of CA Rules for SACA Targeting Detection of Faulty Nodes in WSN

The single attractor cellular automata (SACA) is of prime interest in devising schemes for different applications specially in authentication and cryptography. The synthesis of SACA in linear/additive domain has been proposed in literature. This work reports characterization of such a special class of CA beyond linear domain. The characterization is based on the analysis of individual CA rule and its potential to form the single length cycle attractors (point states). The proposed characterization targets design of a CA based scheme for detection of faulty nodes in a wireless sensor network. It enables identification of faults even in multiple nodes with out major computation overhead.

Sukanta Das, Nazma N. Naskar, Sukanya Mukherjee, Mamata Dalui, Biplab K. Sikdar

Cellular Automata Applied in Remote Sensing to Implement Contextual Pseudo-fuzzy Classification

Nowadays, remote sensing is used in many environmental applications, helping to solve and improve the social problems derived from them. Examples of remotely sensed applications include soil quality studies, water resources searching, environmental protection or meteorology simulations. The classification algorithms are one of the most important techniques used in remote sensing that help developers to interpret the information contained in the satellite images. At present, there are several classification processes, i.e., maximum likelihood, paralelepiped or minimum distance classifier. In this paper we investigate a new satellite image classification Algorithm based on Cellular Automata (ACA), a technique usually used by researchers on complex systems. There are not previous works related to satellite image classification with cellular automata. This new kind of satellite image classifier, that improves the results obtained by classical algorithms in several aspects, has been validated and experimented in the SOLERES framework.

Moisés Espínola, Rosa Ayala, Saturnino Leguizamón, Luis Iribarne, Massimo Menenti

Impact of Coupling of Distributed Denial of Service Attack with Routing on Throughput of Packet Switching Network

We study the effects of coupling of the Distributed Denial of Service (DDoS) attack with routing on a packet switching network (PSN) performance measured by throughput. We conduct our study using PSN model that it is an abstraction of the Network Layer of the 7-Layer ISO OSI Reference Model. Our study demonstrates that even a very “weak” DDoS attack on a network using static routing causes degradation of the network throughput. The values of the throughput almost immediately decrease with each onset of a DDoS attack and they decrease with the increase of the number of attackers. However, this is not the case when the network uses an adaptive routing instead. We consider two different types of adaptive routings and our study shows that the adaptive routings have ability to process efficiently extra packet traffic generated by DDoS attacks without compromising the network throughput when the total amount of the incoming packet traffic, i.e. the regular one and the one coming from an attack, is lower than the one corresponding to the critical source load value.

Anna T. Lawniczak, Hao Wu, Bruno Di Stefano

CA-Based Hardware

A Cellular Automata-Based Modular Lighting System

The term Ambient Intelligence refers to environments enhanced by the presence of electronic devices that are sensitive and responsive to the presence of people. The scenario described in the paper envisages an environment endowed with a set of sensors (to perceive humans or other physical entities), interacting with a set of actuators (lights) that adjust their state of illumination in an attempt to improve the overall experience of these users. The model for the interaction and action of sensors and actuators is an asynchronous Cellular Automata (CA) supporting a self-organization of the system as a response to the presence and movements of people inside it. The paper will introduce the model as well as its implementation in a specific hardware component supporting the realization of modular adaptive lighting systems.

Stefania Bandini, Andrea Bonomi, Giuseppe Vizzari, Vito Acconci

Modeling and Programming Asynchronous Automata Networks: The MOCA Approach

This paper introduces a model and a language for the specification and simulation of networks of automata, a generalization of Cellular Automata characterized by a possibly irregular structure, asynchronous cell transition rule activation, heterogeneity and openness to external influences. The model as well as the derived language are discussed in details, and its possible applications are briefly introduced.

Stefania Bandini, Andrea Bonomi, Giuseppe Vizzari

Efficient Circuit Construction in Brownian Cellular Automata Based on a New Building-Block for Delay-Insensitive Circuits

A Brownian cellular automaton (BCA)(Lee & Peper, 2008) is an asynchronous cellular automaton, where configurations representing signals propagate randomly in the cellular space, resembling particles under Brownian motion. Depending on merely three kinds of local transition rules, this BCA model can be used to construct all primitives in an universal set of delay-insensitive circuit elements, such that all well-known logic circuits can be realized in the cellular space. Though Brownian-like movements of signals enable spontaneous searching for solutions through the state space of computation, their diffusive behavior may induce substantial overhead in the operation of the circuits. In this paper, we propose a novel kind of primitive element that can be employed as a new building-block for the delay-insensitive circuits. Moreover, construction of this new element in the BCA can utilize the spontaneous fluctuations of signals more effectively, while at the same time restricts the Brownian behavior into possibly smaller configurations as compared to the construction of the previous elements, thus will improve the efficiency of the realized logic circuits in the BCA.

Jia Lee, Ferdinand Peper

A Cellular Automaton Controlled Shading for a Building Facade

A practical implementation of cellular automata (CA) in the field of architecture is presented, where a CA drives a modular shading system of a building facade. Application of a 2-color, 1- dimension, range- 2 (2C-1D-R2) CA on a square grid for a regular type of a building facade and the prototype of a CA controlled shading device is presented. The problem of average grayness of a pattern is presented. The solutions for problems of linear gradual change of average grayness as a function of sequence of initial conditions and the sequence of initial conditions which cause desired opacity change of the shading array are presented. The fabrication of the CA shading prototype consists of: design of the logic circuits, fabrication of the units, followed by design of the LCD panel and the acrylic casings.

Machi Zawidzki

FPGA Design of a Cellular Automaton Model for Railway Traffic Flow with GPS Module

In this paper, an electronic system able to reproduce the complex dynamic behaviors of the train movement is presented. In particular, a Cellular Automaton (CA) model inspired by Li et al. corresponding model was developed in order to provide efficient control of the railway traffic flow. The proposed model was implemented on a (Field Programmable Gate Array) FPGA to take full advantage of the inherent parallelism of CAs. The FPGA design which results from the automatically produced synthesizable VHDL code of the CA model is considered as basic component of a portable, low total cost electronic system. The later also includes a high performance Global Positioning System (GPS) wireless communication module for the monitoring of train activity in the under study railway. The aforementioned module in conjunction with the proposed fully automatically programmable FPGA device minimizes the design burden offering the chance of real-time train control operation based on the presented CA model.

Anastasios Tsiftsis, Georgios Ch. Sirakoulis, John Lygouras

ACA - Int. Workshop on Asynchronous CA

What Do We Mean by Asynchronous CA? A Reflection on Types and Effects of Asynchronicity

The aim of this paper is to introduce the problematics deriving from the adoption of an asynchronous CA model. First of all, several cellular automata update schemes and a tentative classification of such schemes are introduced. In order to study the effects of the different update schemes, we introduced a class of simple CA, called One Neighbor Binary Cellular Automata (1nCA). An overview of the general features of 1nCA is described, then the effects of six different updates schemes on all the class of 1nCA are described.

Stefania Bandini, Andrea Bonomi, Giuseppe Vizzari

Parallel Composition of Asynchronous Cellular Automata Simulating Reaction Diffusion Processes

A method of constructing asynchronous cellular automata (ACA) as a parallel composition of two interacting ACA is presented. The resulting ACA is intended to simulate a process with more than one species being involved in it. Two cases of such a composition are considered: (1) when one ACA is functioning independently affecting the evolution of the other, and (2) when both ACA evolute interacting at each iteration.

Olga Bandman

Comparative Study of Parallel Algorithms for Asynchronous Cellular Automata Simulation on Different Computer Architectures

Overview and experimental comparative study of parallel algorithms of asynchronous cellular automata simulation is presented. The algorithms are tested for the model of physicochemical process of surface

CO

 + 

O

2

reaction over the supported Pd nanoparticles on different parallel computers. For testing we use shared memory computers, distributed memory computers (i.e. clusters), and graphical processing unit. Characterization of these algorithms in respect of methods of parallelism maintenance is given.

Konstantin Kalgin

Coxeter Groups and Asynchronous Cellular Automata

The dynamics group of an asynchronous cellular automaton (ACA) relates properties of its long term dynamics to the structure of Coxeter groups. The key mathematical feature connecting these diverse fields is involutions. Group-theoretic results in the latter domain may lead to insight about the dynamics in the former, and vice-versa. In this article, we highlight some central themes and common structures, and discuss novel approaches to some open and open-ended problems. We introduce the state automaton of an ACA, and show how the root automaton of a Coxeter group is essentially part of the state automaton of a related ACA.

Matthew Macauley, Henning S. Mortveit

Some Formal Properties of Asynchronous Cellular Automata

We study the dynamical behaviour of asynchronous cellular automata by considering some formal properties of classical cellular automata and adapting them to the asynchronous case.

Luca Manzoni

A Study on the Automatic Generation of Asynchronous Cellular Automata Rules by Means of Genetic Algorithms

We present a framework based on genetic algorithms to automatically generate cellular automata rules under four different asynchronous update models (fixed random sweep, random new sweep, clock and independent random ordering). We consider four different rules (18, 56, 110 and 180) with well known dynamics under synchronous update scheme. We try to reconstruct the same dynamics by means of a genetic algorithm using asynchronous update schemes. We show that in many cases it is impossible, by means of an asynchronous update scheme, to perfectly reconstruct these dynamics. Nevertheless, we show that the genetic algorithm finds the rules that more closely approximate the target behavior and the dynamics of the rules found by the genetic algorithm are rather similar to the target ones. In particular, we can always recognize a similar patter and we can also identify some differences in small details, which can be minimal (as for rule 18) or rather visible (as for rule 110). This paves the way to a deeper investigation on this track: does using asynchronous updates allow us to find more stable rules, i.e. rules that are less affected by noise, and thus do not overfit training data? This question remains open and answering it is one of the main goals of our current research.

Andrea Valsecchi, Leonardo Vanneschi, Giancarlo Mauri

C&CA - Int. Workshop on Crowds and CA

Towards Patterns of Comfort: A Multilayered Model Based on Situated Multi-agent Systems

The paper presents the agent-based model we developed to study crowd dynamics in multi-cultural aggregation contexts. Social and cultural aspects (in particular derived from proxemics theory) are explicitly modeled in order to study the social network resulting from local spatial interactions and cultural differences. To this aim, an agent-based model based on SCA*PED (Situated Cellular Agents for PEdestrian Dynamics) is presented, where pedestrian dynamics result from the local interaction and behavior of an heterogeneous system of autonomous entities situated into a structured environment. The proposed model represents pedestrians’ behaving according to local information and knowledge on two separated yet interconnected layers representing different aspects of the overall system dynamics (i.e. Spatial and Proxemic layer). The model explicitly represents on Proxemic layer how cultural differences can influence the perception of neighbors. The model is presented as a formal approach to study comfort properties in spaces where multicultural crowds share a limited structured environment.

Paola Lembo, Lorenza Manenti, Sara Manzoni

A Pedestrian Movement Model That Takes into Account the Capacity Drop Phenomenon in the Motion of Crowd

In this paper we propose a CA movement model based on the “Cell Transmission Model” developed by Daganzo. The cell transmission model was developed as a discrete approximation to the hydrodynamic theory of vehicular traffic flow. The proposed movement model refers instead to the motion of crowd and is required to simulate the dynamic of an egress process in tall buildings taking into account not only queue and spillback phenomena but also the capacity drop phenomenon. In fact we performed experiments that show important evidence that, for a given cross section, in presence of jam upstream the section, the pedestrian flow through the section is not always equal to the section capacity but suddenly it can drop (dropped capacity). This finding is coherent with recent empirical studies of pedestrian behavior at an exit and in contrast with many previous works where it is assumed that in presence of jam upstream a cross section, the flow through the section equals its capacity. The movement model has been used for simulating evacuation processes in high rise buildings. The target is to assess to which extend the capacity drop phenomenon affects the building evacuation time.

Elvezia M. Cepolina, Alessandro Farina

A Cellular Automaton Model for Crowd Evacuation and Its Auto-Defined Obstacle Avoidance Attribute

In this paper, a crowd evacuation model based on Cellular Automata (CA) is described. The model takes advantage of the inherent ability of CA to represent sufficiently phenomena of arbitrary complexity and to be simulated precisely by digital computers as well. Pedestrian movement depends on their distance from the closest exit, which is defined dynamically. The adoption of Manhattan distance as the reference metric provides calculation simplicity, computational speed and improves significantly computational performance. Moreover, the model applies an efficient method to overcome obstacles. The latter is based on the generation of a virtual field along obstacles. A pedestrian moves along the axis of the obstacle towards the direction that the field increases its values, leading her/him to avoid the obstacle effectively. Distinct features of crowd dynamics and measurements on different distributions of pedestrians have been used to evaluate the response of the model.

Ioakeim G. Georgoudas, Georgios Koltsidas, Georgios Ch. Sirakoulis, Ioannis Th. Andreadis

A Learning Algorithm for the Simulation of Pedestrian Flow by Cellular Automata

Cellular Automata was applied to model the pedestrian flow, where the local neighbor and transition rules implemented to each person in the crowd were determined automatically by the experience of pedestrians. The experience was based on two parameters; the number of continuous vacant cells in front of the cell to proceed, and the number of pedestrian in the cell to proceed. The experience was evaluated numerically, and a pedestrian selected the cell to proceed by the evaluated index. The flow formations by pedestrians in the opposite direction on a straight pathway and on a corner were simulated, and the number of rows was discussed in relation to the density of pedestrian on the simulation space.

Hideaki Ishii, Shin Morishita

On Influencing of a Space Geometry on Dynamics of Some CA Pedestrian Movement Model

In this paper we show an effect that a shape of way contributes to dynamics of one Cellular Automata pedestrian movement model. The fundamental diagrams for a closed and strait pathes are presented and discussed.

Ekaterina Kirik, Tat’yana Yurgel’yan, Dmitriy Krouglov

The Dynamic Distance Potential Field in a Situation with Asymmetric Bottleneck Capacities

This contribution discusses the application of a fast and sloppy solution of the Eikonal equation – namely the dynamic distance potential field – for the simulation of the flow of a group of pedestrian agents through two bottlenecks with different capacity (width) but identical walking distance toward the destination. It is found that using the method leads to a better distribution of agents on the two corridors.

Tobias Kretz

Solving the Direction Field for Discrete Agent Motion

Models for pedestrian dynamics are often based on microscopic approaches allowing for individual agent navigation. To reach a given destination, the agent has to consider environmental obstacles. We propose a direction field calculated on a regular grid with a Moore neighborhood, where obstacles are represented by occupied cells. Our developed algorithm exactly reproduces the shortest path with regard to the Euclidean metric.

Michael Schultz, Tobias Kretz, Hartmut Fricke

Phase Coexistence in Congested States of Pedestrian Dynamics

Experimental results for congested pedestrian traffic are presented. For data analysis we apply a method providing measurements on an individual scale. The resulting velocity-density relation shows a coexistence of moving and stopping states revealing the complex structure of pedestrian fundamental diagrams and supporting new insights into the characteristics of pedestrian congestions. Furthermore we introduce a model similar to event driven approaches. The velocity-density relation as well as the phase separation is reproduced. Variation of the parameter distribution indicates that the diversity of pedestrians is crucial for phase separation.

Armin Seyfried, Andrea Portz, Andreas Schadschneider

Stochastic Transition Model for Discrete Agent Movements

We propose a calibrated two-dimensional cellular automaton model to simulate pedestrian motion behavior. It is a v

max

= 4 (3) model with exclusion statistics and random shuffled dynamics. The underlying regular grid structure results in a direction-dependent behavior, which has in particular not been considered within previous approaches. We efficiently compensate these grid-caused deficiencies on model level.

Michael Schultz, Hartmut Fricke

Analysis of Obstacle Density Effect on Pedestrian Congestion Based on a One-Dimensional Cellular Automata

This is a study on a situation where pedestrians walk through a crowded area. The 1-D Cellular Automata model ultimately resulting to the Asymmetric Simple Exclusion Process is studied. Numerical and analytical study is carried out to investigate how pedestrian behaviour is affected.

Kenichiro Shimura, Yuki Tanaka, Katsuhiro Nishinari

Excluded Volume Effect in a Pedestrian Queue

We have introduced excluded volume effect, which is a significant factor to model a realistic pedestrian queue, into queueing theory. The model has been exactly solved. Concretely, probability distributions and means of the number of waiting pedestrians, length of a queue, and waiting time have been derived. Due to the excluded volume effect, the process of closing up is included in our new model, so that the mean number of pedestrians increases as pedestrian arrival probability (

λ

) and leaving probability (

μ

) increase even if the ratio between them (i.e.,

ρ

 = 

λ

/

μ

) remains constant. Moreover, interval distance between pedestrians is included in our model because of the excluded volume effect, thus, length of a queue is considered more realistically than previous model. A queueing experiment is also performed to verify the validity of our model.

Daichi Yanagisawa, Yuki Tanaka, Rui Jiang, Akiyasu Tomoeda, Kazumichi Ohtsuka, Yushi Suma, Katsuhiro Nishinari

T&CA - Int. Workshop on Traffic and CA

Simulation on Vehicle Emission by the Brake-Light Cellular Automata Model

Vehicle emission has become a major source of air pollution. In this paper, the brake-light cellular automaton model incorporated with a vehicle emission model is utilized to investigate emitted exhaust pollution by traffic flow. First, both macro- and microscopic features of traffic flow are reproduced quantitatively and compared with empirical findings. Then the model is used to simulate the vehicle emission of a moving fleet of vehicles. It is shown qualitatively that the emission rate is significantly increased in the medium density range with considering instantaneous velocity and acceleration together. Usually the total amount of pollutant discharge from vehicles is underestimated by considering average velocity alone. It is believed that a good driving strategy, e.g. eco-driving, is an effective way to reduce vehicle emission.

Liyun Dong, Peng Zhang, Shiqiang Dai

Bidirectional Traffic on Microtubules

Intracellular transport involves the processive displacement of molecular motors on microtubules. These motors are specialized to walk in one or the other direction on the microtubule. It is not known yet how this bi-directional traffic is organized in order to be efficient. Here we use some modeling based on cellular automata models to point out the problems caused by bidirectional transport, we discuss the role of confinement around the microtubule, and we illustrate how the dynamics of the microtubules could help preventing jam formation.

Maximilian Ebbinghaus, Cécile Appert-Rolland, Ludger Santen

Cellular Automata for a Traffic Roundabout

We propose a cellular automaton model for a typical traffic roundabout to regulate traffic flow from four different directions. In the four-way symmetrical case, the number of parameters reduce from sixteen to four. As these four parameters change, we observe three distinct traffic phases: free flow, congestion, and gridlock. As the inflow increases, free flow transits to congestion when the interweaving traffic is light. When the interweaving traffic is heavy, free flow transits directly to gridlock instead. The traffic interweave is characterized by a new parameter

X

. We present both numerical simulations and analytical discussions.

Ding-wei Huang

Cellular Automata for a Cyclic Bus

We propose a simple cellular automaton model to study the dynamics of a cyclic bus. The nontrivial fluctuations are prescribed by the stochastic moving of bus interacting with the stochastic arrival of passengers. As passengers increase, the bus schedule shows a clear transition. Both numerical and analytical results are presented. The divergence of bus schedule can be taken as an analogy to the gridlock of 4-way traffic. We also comment on the strategy to keep a stable schedule.

Ding-wei Huang, Wei-neng Huang

Dynamics of a Tagged Particle in the Asymmetric Exclusion Process with Particlewise Disorder

We consider the one-dimensional totally asymmetric asymmetric simple exclusion process. We particularly concentrate on the case where each hopping rate depends on each particle. In the step initial condition, where all sites from the left of some site are occupied and all other sites are empty, we discuss a dynamics of a particular particle (tagged particle). We show that the position fluctuation of the tagged particle is equivalent to the largest eigenvalue fluctuation of the Gaussian Unitary Ensemble (GUE) in the random matrix theory.

Takashi Imamura

Chase and Escape in Groups

We study here a recently proposed theme of one group chasing another, called “group chase and escape”. Rather rich and complex behavior such as self-organized structures can arise from a model with simple rules. We discuss models with various cases of different speeds between the two groups, search ranges, and motion fluctuations.

Atsushi Kamimura, Shigenori Matsumoto, Nobuyasu Ito, Toru Ohira

A Velocity-Clearance Relation in the Rule-184 Cellular Automaton as a Model of Traffic Flow

In this article, we investigate the velocity-clearance relation of vehicles in CA models for traffic flow using a calibration of the cell size (length) which we already proposed. We can mimic a more realistic behaviour of vehicles in traffic flow changing the cell size according to the density of particles in cellular automaton models. As a result, the velocity of particles in the rule-184 cellular-automaton model becomes dependent on the clearance, i.e., the distance to the next particle in front (in the right-hand side). Also, we show that the calibration is valid in that it reproduces a realistic flow-density diagram.

Masahiro Kanai

CA and MAS – With the NaSch as Example

This is a contribution to the discussion of the interrelation between multi agent systems (MAS) and cellular automata (CA). The claim is that the Nagel Schreckenberg Model is a MAS, while at the same time it can perfectly be formulated as a CA. To underline this and to demonstrate the difference to and the benefit of a MAS formulation the rule table for the NaSch Model with

v

max

= 2 is given.

Tobias Kretz

Productivity Enhancement through Lot Size Optimization

We propose a simple model of a production plant that is based on the ASEP and simulate the dependence of the lead time

T

on the lot size

r

. Then, we derive an analytical description of the simulation results based on exact results for the single-species ASEP. Furthermore, we determine the optimum lot size

r

c

and investigate dependence of

r

c

on several parameters used in the simulations.

Takumi Minemura, Katsuhiro Nishinari, Andreas Schadschneider

Multilane Single GCA-w Based Expressway Traffic Model

We show how, by applying relaxation and extension of Elementary Cellular Automata Rule 184, we can model realistic highway traffic. In particular, we examine some of the available options for modeling variable acceleration, variable speed, multi-lane traffic, lane-changing for the purpose of avoiding obstacles or overtaking slower vehicles, suddenly stalled vehicles, and drivers’ ability to account for the “brake lights” information and react to it. We describe the main features of our multilane expressway model developed adopting such extensions of Cellular Automata as “Global Cellular Automata” and “Global Cellular Automata with Write access”.

Anna T. Lawniczak, Bruno Di Stefano

Properties of Cellular Automaton Model for On-ramp System

The on-ramp, as a typical bottleneck, has been widely studied by using Cellular Automata model. There are two different kinds of Cellular Automata models for on-ramp. This paper investigate the difference in traffic dynamics between the two kinds of models. The results show that they both have realistic and unrealistic features. The strong points of the two kinds of models should be combined together to model the on-ramp system.

Xin-Gang Li, Zi-You Gao, Bin Jia

Inversion of Flux between Zipper and Non-Zipper Merging in Highway Traffic

For easing heavy traffic jams on weaving and merging sections on highway traffic, we compare the efficiency of zipper merging and non-zipper merging. Zipper merging is the merging of vehicles on two lanes by turns and achieved by only vehicle-to-vehicle interactions before merging. Non-zipper merging is the merging without any interactions before merging. In this comparison we use a cellular automaton model on multiple lanes with slow-to-start rules. Simulations and mean-field analysis show that the flux of zipper merging is larger (smaller) than that of random merging in the case of large (small) slow-to-start effect.

Ryosuke Nishi, Hiroshi Miki, Akiyasu Tomoeda, Daichi Yanagisawa, Katsuhiro Nishinari

Clustering and Transport Efficiency in Public Conveyance System

Traffic efficiency of the public conveyance system on a given route is numerically and analytically investigated by introducing a new quantitative measure, so-called

transportation volume

, which is defined by the product of velocity and the number of on-board passengers. In terms of this measure, the optimal density of vehicles, at which the average velocity becomes maximum or the flow of particles becomes maximum, does not always make the transportation volume maximum. Moreover, under both with and without information-based control system, we have shown that this transportation volume shows some constant value almost everywhere in the density, even though the average velocity and the number of on-board passengers per unit bus decrease in the higher density of vehicles.

A. Tomoeda, R. Nishi, K. Nishinari

Clusters in the Helbing’s Improved Model

The formation of clusters in Helbing’s improved model is studied by an iterative method. It is shown that after certain density we will always obtain a density profile which has the structure of a soliton. Its characteristics such as the amplitude and width are determined by the parameters in the model.

Rosa María Velasco, Patricia Saavedra

Phase Transitions in Cellular Automata for Cargo Transport and Kinetically Constrained Traffic

A probabilistic cellular automaton for cargo transport is presented that generalizes the totally asymmetric exclusion process with a defect from continuous time to parallel dynamics. It appears as an underlying principle in cellular automata for traffic flow with non-local jumps for the kinetic constraint to drive as fast as possible. The exactly solvable model shows a discontinuous phase transition between two regions with different cargo velocities.

Marko Woelki

A New Computational Methodology Using Infinite and Infinitesimal Numbers

Traditional computers work numerically only with finite numbers. Situations where the usage of infinite or infinitesimal quantities is required are studied mainly theoretically. In this lecture, a new computational methodology (that is not related to non-standard analysis approaches) is described. It is based on the principle ‘The part is less than the whole’ applied to all quantities (finite, infinite, and infinitesimal) and to all sets and processes (finite and infinite). The new methodology has allowed the author to introduce the Infinity Computer working numerically with infinite and infinitesimal numbers. The new computational paradigm both gives possibilities to execute computations of a new type and simplifies fields of Mathematics and Computer Science where infinity and/or infinitesimals are required. Examples of the usage of the introduced computational tools are given during the lecture.

Yaroslav D. Sergeyev

IWNC - Int. Workshop on Natural Computing

Molecular Implementations of Cellular Automata

Cellular Automata (CA) have a long history as computation models, but only in the last few years have serious attempts started to implement them in terms of molecules. Such nano-technological innovations promise very cost-effective fabrication because of the regular structure of CA, which allows assembly through molecular self-organization. The small sizes of molecules combined with their availability in Avogadro-scale numbers promises a huge computational power, in which the massive parallelism inherent in CA can be effectively exploited. This paper discusses critical background aspects of our recent results on the implementation of a CA by a molecular assembly (Bandyopadhyay

et al.

, Nature Physics 2010).

Satyajit Sahu, Hiroshi Oono, Subrata Ghosh, Anirban Bandyopadhyay, Daisuke Fujita, Ferdinand Peper, Teijiro Isokawa, Ranjit Pati

Achieving Universal Computations on One-Dimensional Cellular Automata

We show how natural universal computations can be achieved on one-dimensional cellular automata. That model of computation is obviously Turing complete but how can we effectively program any given computation is far less known. In this paper we are interested in intrinsic universality; we want a CA in which any other CA can be represented and simulated with no intermediate coding relevant to another computation model. The first step is to abstract from the space-time diagram in favor of a more essential dependency graph. Then such dependency graph can be projected on grids. This work shows that grids put forward causality in place of space-time contingencies.

Jean-Baptiste Yunès

Backmatter

Additional information