Cellular Automata

Although several studies addressed the dynamical properties of cellular automata (CAs) in general and the sensitivity to the initial condition from which they are evolved in particular, only minor attention has been paid to the interference between a CA’s dynamics and its underlying topology, by which we refer to the whole of a CA’s spatial entities and their interconnection. Nevertheless, some preliminary studies highlighted the importance of this issue. Henceforth, in contrast to the sensitivity to the initial conditions, which is frequently quantified by means of Lyapunov exponents, to this day no methodology is available for grasping this so-called topological sensitivity. Inspired by the concept of classical Lyapunov exponents, we elaborate on the machinery that is required to grasp the topological sensitivity of CAs, which consists of topological Lyapunov exponents and Jacobians. By relying on these concepts, the topological sensitivity of a family of 2-state irregular totalistic CAs is characterized.

This paper reports characterization of 1-D cellular automata (CA) state space to count the cycles of reversible CA. The reachability tree provides theoretical framework to identify number of cycles in reversible CA. However, we concentrate here on a special class of reversible CA that follow

right independence

property. The right independence property implies, the cells of CA are independent of right neighbor. To our knowledge, no work till now has been done to find the number cycles of reversible CA by analyzing the CA state space.

The void propagation defines a long-range interaction in granular matter. We detail a logic scheme simulating the propagation and implemented in a 2

d

cellular automata applied to granular flow. The CA belongs to the family of “lattice-grain” automata (LGrA) with one particle per cell. We focus first on the influence of inertia, or “memory effect”, on the flow patterns. The propagative mode is presented afterwards: it implies that transition and timestep must be considered at two different time scales. Although a CA is usually driven by local, nearest-neighbor communications, it follows here that the timestep termination must be detected at each transition, that involves a perpetual and global communication within the network to synchronize the timestep. An all-to-all “systolic gossiping” underlies the framework of this void propagation model.

We know that a few uniform cellular automata have maximum cycle lengths. However, there are many uniform cellular automata, and checking the cycles of all uniform cellular automata is impractical. In this paper, we define a cellular automaton by composition and show how its cycles are related.

We investigate the descriptional complexity of little resources added to deterministic one-dimensional real-time iterative arrays. More precisely, we study the impact of adding sublinearly more time obtaining time complexities strictly in between real time and linear time, adding dimensions, allow the communication cell to perform a few nondeterministic steps, and increase the number of bits that may be communicated to neighboring cells slightly. In all cases it is shown that there are arbitrary savings in the size of the descriptions of the arrays which cannot be bounded by any computable function.

The paper characterizes a special class of Cellular Automaton (CA) called Two Predecessor Single Attractor CA (TPSA-CA). We show that the transition graphs of the TPSA-CA can be used to realize pseudo-random regular graphs with good expansion properties. The elegance of the scheme lies in the fact that the storage required to capture the graph is

O

(

log

N

), where

N

is the total number of vertices in the graph.

This paper reports a scheme to identify cyclic/acyclic states from the state space of cellular automata (CA). We analyze the reachability tree to do this. An algorithm is presented to count the cyclic states. We introduce a concept of tree merging for identifying cyclic and acyclic states. To our knowledge, this is the first work to efficiently identify cyclic/acyclic states from the state space of nonlinear CA. Since cyclic states can only form attractors, the identification of cyclic states would help us to characterize CA attractors.

In this paper, we examine rule 20 elementary cellular automaton of Wolfram class II and show that the rule has 2-step 2-right and 2-step 2-left shift dynamical subsystems, and combining these two subsystems moving in the opposite direction, we have a confliction-like dynamical sub-system which cannot be imagined from that the rule belongs to Wolfram class II. Furthermore we show

$g^{2}_{20}=\max\{f_{20RE},f_{20LE}\}$

suggesting that the rule 20 is composed of two simpler cellular automata

f

20

RE

and

f

20

LE

corresponding to 2-step 2-right and 2-step 2-left shift dynamical subsystems, respectively. We also mention that there exist several rules of class II showing confliction-like dynamics similar to rule 20 but all of them have not yet been fully examined. Rule 14, one of them, especially shows an interesting movement called reversing and right shift.

From these observations we know that even a single cellular automaton has not necessarily only one dynamical property but also includes several entirely different subsystems and each of them emerges depending on patterns of initial configurations. And furthermore we may say that there exist some basic cellular automata and methods, perhaps Boolean functions, to combine them to generate other cellular automata.

This paper proposes a simple algorithm to find the critical temperature of the continuous-state Game of Life (GoL). The algorithm conducts the transitions of cells and the update of the temperature parameter alternatingly. The temperature starts from a low value and it increases gradually, while a fixed GoL pattern evolves. This process continues, but before the temperature exceeds the critical temperature, the update algorithm acts to decrease it, so as to prevent overshoot of the temperature, which would make the cell states deviate from the normal GoL behavior. An oscillatory value of the temperature can be observed, but it converges towards a fixed value, indicating that its critical point is being approached.

The cellular automata approach to the analysis of the electorate voting is presented. We show the analysis of the proportionality of elections by using different update rules for the cellular automata representing the voters space. There exist many methods of performing system update which can be generally classified into two classes: outward, when the individual’s opnion is spread over his neighbors and inward when the individual is under pressure of his environment. In the paper we show the relaxation, stability and the Gallagher index value for at the successive stages of CA simulation run. We find that the majority of methods leads to similar results however few of them is promising when trying to reproduce some social phenomena.

Firing Squad Synchronization Problems are well known to be solvable by voluminous transition tables describing signals traveling and colliding. In this paper, we show that it is possible to solve it by expressing directly the fact that we want a recursive division of the space into two parts of equal size, and a notification when no further division is possible. Using fields – objects associating a value to every point in space and time – as primitive objects, the solution is designed algorithmically by a semantically-intuitive decomposition of the global evolution into simpler evolutions.

The system we obtain has several interesting characteristics : it is understandable, time-optimal, tackles many initial configurations, and allows a new interpretation of the traditional signals and collisions point of view. We will quickly sketch how we can obtain a finite state automaton by reduction of the system using the Lipschitz-continuity of involved fields, and a kind of tail-recursivity property of the dependencies.

Cellular Automata (CA) have been proposed for task scheduling in multiprocessor architectures. CA-based models aim to be fast and decentralized schedulers. Previous models employ an off-line learning stage in which an evolutionary method is used to discover cellular automata rules able to solve an instance of a task scheduling. A central point of CA-based scheduling is the reuse of transition rules learned for one specific program graph in the schedule of new instances. However, our investigation about previous models showed that evolved rules do not actually have such generalization ability. A new approach is presented here named multigraph coevolutionary learning, in which a population of program graphs is evolved simultaneously with rules population leading to more generalized transition rules. Results obtained have shown the evolution of rules with better generalization abilitywhen they are compared with those obtained using previous approaches.

This paper proposes a cellular automata-based solution of a two-dimensional binary classification problem. The proposed method is based on a two-dimensional, three-state cellular automaton (CA) with the von Neumann neighborhood. Since the number of possible CA rules (potential CA-based classifiers) is huge, searching efficient rules is conducted with use of a genetic algorithm (GA). Experiments show an very good performance of discovered rules in solving the classification problem. The best found rules perform better than the heuristic CA rule designed by a human and also better than one of the most widely used statistical method: the k-nearest neighbors algorithm (

k-NN

). Experiments show that CAs rules can be successfully reused in the process of searching new rules.

The role of cellular automata in optimization is a current area of research. This paper presents a multi-objective approach to cellular optimization. A typical nonlinear problem of spatial resource allocation is treated by two alternative methods. The first one is based on a specially designed operative genetic algorithm and the second one on a hybrid annealing – genetic procedure. Pareto front approximations are computed by the two methods and also by a non-cellular version of the second approach. The better performance of the cellular methods is demonstrated and questions for further research are discussed.

We modify the transition rule of the

N

-color cyclic particle system, such that the arising system is applied for social dynamics. An asynchronous update is examined, where each two neighboring sites of a social network interact at exponential rate, and one of the sites adopts the color (opinion) of a randomly chosen neighbor, provided that their colors are adjacent on the cycle

C

N

that represents the colors. We show that starting from independent and uniformly distributed colors on the integer lattice, each site fixates to a final color with probability 1 if

N

 ≥ 5, which is sharp due to Lanchier (2012). Moreover, we conduct simulations with appropriate cellular automata and find that the frequency of the long observed Condorcet’s paradox of voting increases in the fixation region of the six-color automaton.

We generalize the clustering theorem by Lanchier (2012) on the infinite one-dimensional integer lattice ℤ for the constrained voter model and the two-feature two-trait Axelrod model to multitype biased models with confidence threshold. Types are represented by a connected graph Γ, and dynamics is described as follows. At independent exponential times for each site of type

i

, one of the neighboring sites is chosen randomly, and its type

j

is adopted if

i

,

j

are adjacent on Γ. Starting from a product measure with positive type densities, the clustering theorem dictates that fluctuation and clustering occurs, i.e., each site changes type at arbitrary large times and looking at a finite interval consensus is reached asymptotically with probability 1, if there is one or two vertices of Γ adjacent to all other vertices but each other. Additionally, we propose a simple definition of clustering on a finite set, in which case one can apply the clustering theorem that justifies known previous claims.

The stable patterns formed as a result of evolution of totalistic cellular automata (CA) with weighed templates are investigated. A formal definition of the CA with the weighed templates is presented. As a result of simulation by synchronous and asynchronous CA, various stable patterns emerging from one nucleation cell are obtained and classified. The influence of weight matrix entries on stable patterns is studied. The theorem about the stable patterns dependence on the ratio of positive to negative entries of a weight matrix is proved. Stable patterns formed of two nucleation cells are also investigated.

The firing squad synchronization problem (FSSP) on cellular automata has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms have been proposed. In the present paper, we focus our attention to two-dimensional square synchronizers that can synchronize square arrays and construct a survey on recent developments in their designs and implementations of optimum-time synchronization algorithms for square arrays. A new generalized square synchronization algorithm with an initial general at any position is also presented.

The structural operational semantics approach to the dynamic meaning of formal models has been immensely influential as a foundation of both theoretical calculi and practical programming languages, and is a viable alternative to automata-oriented approaches. We report on an effort to apply the approach to cellular automata, in particular of the two-dimensional, regular finite grid kind that underlies many agent-based simulation models. We summarize previous, intensively category-theoretic work in more general terms, and discuss how various interesting properties are made (more) explicit by the semantical analysis of cellular automata in terms of novel mathematical structures.

This paper presents the system based on cellular automata (CA) for controlling the average opacity of any triangulated surface, in particular serving as a building envelope. The concept is based on the emergent and modular qualities of CAs and is proposed for a practical application in the field of architecture. The concept of triangular cellular automata (TCA) is explained, followed by application of totalistic (tTCA) and semi-totalistic (stTCA) TCA on an imperfect test mesh, that is a mesh with voids and nodes of various degrees. Preliminary analysis of the behavior of these TCAs at various types of initial conditions in the context of shading purposes is presented.

We explore a community-detection cellular automata algorithm inspired by human heuristics, based on information diffusion and a non-linear processing phase with a dynamics inspired by human heuris- tics. The main point of the methods is that of furnishing different “views” of the clustering levels from an individual point of view. We apply the method to networks with local connectivity and long-range rewiring.

A new cellular automaton-based approach allowing to generate sorting networks is presented. Since the traditional table-based transition function in this case involves excessive number of rules, a program-based representation of the transition function is applied. The sorting networks are encoded by the cell states and generated during the cellular automaton development. The obtained results are compared with our previous approaches utilizing cellular automata.

The network view of cellular automata focuses on the effective relationships between cells rather than the states themselves. In this article, we review a network representation presented in previous papers and present network graphs derived from all independent rules of one-dimensional elementary cellular automata and totalistic five-neighbor cellular automata. Removal of the transient effects of initial configurations improves the visibility of the dynamical characteristics of each rule. Power-law distributions of lifetimes and sizes of avalanches caused by one-cell perturbations of an attractor are exhibited by the derived network of Rule 11 (or 52) of totalistic five-neighbor cellular automata.

The faulty nodes in WSN (Wireless Sensor Network) may badly affect the network performance while trying to reach an agreement on an event. This effectively leads to deviation from the desired outcome and unproductive computational overhead. Identification of network region with faulty nodes is, therefore, a necessity to ensure agreement on an issue/event simultaneously limiting the computational overhead. This work proposes a CA (Cellular Automata) based scheme that can efficiently diagnose the region of faulty nodes in a WSN. The scheme is developed around the special class of CA called SACA. This enables fast identification of faulty region with marginal additional computation and the network bandwidth.

This paper introduces the notion of noise-induced emergent hierarchies and analyses the influence of the topology of the underlying network on these hierarchies. By developing upon a previous model of cell differentiation based on noisy random Boolean networks, we show that the adoption of a regular topology such that of cellular automata can lead to interesting effects, the most remarkable one being that,

ceteris paribus

, the resulting hierarchies have a larger number of levels and could therefore describe more “structured” complex systems.

Given a population with internal structures determining possible interactions between population members, what can be said about the spread of innovation? In genetics, this is a question of the spread of a favorable mutation within a genetically homogeneous population. In a model society, it is the question of rumors, beliefs, or innovation [1,2,3,4,5]. This paper sketches a simple iterative model of populations with structure represented in terms of edge weighted graphs. Use of such graphs has become a powerful tool in evolutionary dynamics [e.g. 6]. The model presented here employs a Markov process on a state space isomorphic to the vertex set of the N-hypercube. In analogy to genetics, spread of innovation is first modeled as a biased birth-death process in which the innovation provides a fitness r as compared to the fitness of 1 assigned to non-innovative individuals. Following on this, a probabilistic model is developed that, in the simplest cases, corresponds to an elementary probabilistic cellular automata.

Major technology progress and evolution of human living standards have led to wide development of mobile telecommunications. Nowadays, classic mobile phones tend to be replaced by more complex devices that show similar abilities to personal computers (PCs), known as smartphones. Rapid spreading of smartphone technology, as well as significant resemblance to PCs, gave rise to the appearance of mobile phone viruses, and the first attacks have already been recorded. In this work, the study of methods for the spreading of mobile phone viruses using Cellular Automata (CAs) is presented. The dependence of spreading patterns on time and on the operating system (OS) market share is examined with the use of a mathematical model designed for the prediction of such future situations. Simulation results are compared to published results based on real communication patterns, proving that the proposed model effectively captures the dynamics of mobile virus spreading.

The phenomenon of sand erosion is recently spreading in Mediterranean beaches in a worrisome way. Cellular Automata modelling such a phenomenon involves many difficulties for adopting a convenient time and space scale (minute and decimeter), that can permit temporally reasonable simulations. A very preliminary model RUSICA was developed in association with an experimental work in order to test hypotheses, to receive suggestion separately for some basic processes and to learn from past occurred cases. During this contamination phase, some experimental applications were succesfully projected in order to contrast sand erosion on the coast. This paper presents the current initial version of RUSICA for sand erosion/transport/deposition and describes the results obtained at Porto Cesareo coast in the Italian Apulia Region. Complete simulations by RUSICA will soon follow this preparatory work.

The accuracy of Cellular Automata (CA) methods for simulating wildfires is limited by the fact that spread directions are constrained to the few angles imposed by the regular lattice of cells. To mitigate such problem, this paper proposes a new CA in which a local randomization of the spread directions is explicitly introduced over the lattice. The suggested technique, inspired by a method already used for simulating lava flows, is empirically investigated under homogeneous conditions and by comparison with the vector-based simulator FARSITE. According to the presented results, the adopted randomization seems to be able to significantly improve the accuracy of CA based on a standard center-to-center ignition scheme.

Multicomponent Cellular Automata, also known as Macroscopic Cellular Automata, characterize a methodological approach for modeling complex systems, that need many components both for the states (substates) to account for different properties of the cell and for the transition function (elementary processes) in order to account for various different dynamics. Many applications were developed for modeling complex natural phenomena, particularly macroscopic ones, e.g., large scale surface flows. Minimizing the differences of a certain quantity in the cell neighborhood, by distribution from the cell to the other neighboring cells, is a basic component of many transition functions in this context. The Algorithm for the Minimization of Differences (AMD) was applied in different ways to many models. A fundamental theorem about AMD is proved in this paper; it shows that AMD properties are more extended than the previous demonstrated theorem.

The aim of this work is to present a model based on a Stochastic Cellular Automata to generate granulometric distribution of pedestrian groups in structured spaces. The main goal of this model is to set initial configurations for pedestrian simulations starting from plausible scenarios that consider the presence of groups within a crowd.

An optimal management of an irrigation network is important to ensure an efficient water supply and to predict critical situations related to natural hazards. We present a multiscale coupling methodology to simulate numerically an entire irrigation canal over a distributed High Performance Computing (HPC) resource. We decompose the network into several segments that are coupled through junctions. Our coupling strategy, based on the concept of Complex Automata (CxA) and the Multiscale Modeling Language (MML), aims at coupling simple 1D model of canal sections with 3D complex ones. Our goal is to build a numerical model that can be run over a distributed grid infrastructure, thus offering a large amount of computing resources. We illustrate our approach by coupling two canal sections in 1D through a gate.

Local interactions and influences among places in a city depend on their mutual distances in terms of accessibility to humans. That distance is hardly Euclidean, since it depends on the urban geography shaped, among others, by the network of transportation and pedestrian networks. Very little operational efforts have been undertaken in CA-based urban modelling to investigate and provide a more coherent treatment of such irregular geometries. In this paper, we propose an operational approach entirely based on cellular automata techniques for modelling of such accessibility arising from complex urban geography. We further present an example application on the city of Heraklion in Crete.

This paper presents a framework for robot path planning based on the A* search algorithm in the presence of dynamically expanding obstacles. The overall method follows Cellular Automata (CA) based rules, exploiting the discrete nature of CAs for both obstacle and robot state spaces. For the search strategy, the discrete properties of the A* algorithm were utilized, allowing a seamless merging of both CA and A* theories. The proposed algorithm guarantees both a collision free and a cost efficient path to target with optimal computational cost. More particular, it expands the map state space with respect to time using adaptive time intervals in order to predict the necessary future expansion of obstacles for assuring both a safe and a minimum cost path. The proposed method can be considered as being a general framework in the sense that it can be applied to any arbitrary shaped obstacle.

A novel visual multimedia content encryption method based on cellular automata (CA) is presented in this paper. The proposed algorithm is based on an attribute of the eXclusive-OR (XOR) logic gate, according to which, its application to a square-sized CA has the ability to reconstruct the original content of a CA after a preset number of iterations. The resulted encrypted image is a lossless representation of the original/plaintext image, i.e. there is no loss of either resolution or contrast. Experimental results indicate that the encrypted image does not contain any statistical information able to reveal the original image.

Soils, air and water have been deeply contaminated by anthropogenic activities continuously spread over time. One of the most dangerous pollutant in groundwater is represented by chlorinated organic solvents, which acts as a Dense Non Aquifer Phase Liquid (DNAPL) contaminant. Many laboratory experiments have shown that nZVI encapsulated into micelles could treat DNAPL pollution directly into the groundwater but very few in situ experimentations have been tested. Agent-Based Model (ABM) is a powerful tool to simulate and to gain better insights in complex systems. In this paper we present an ABM simulation of DNAPL contaminated groundwater remediation. The model simulates a dehalogenation process of Trichloroethylene (TCE) with the application of encapsulated nZVI, directly injected into the DNAPL contaminant source.

This paper reports the theory of a special class of Cellular Automata (CA) referred to as Restricted 5 Neighborhood CA (R5NCA). Its application deals with identification of Protein Structure. Each amino acid of a protein chain is modeled with a R5NCA rule. In the process, a protein gets modeled as a R5NCA. CA Evolution models the evolution of the protein to its minimum energy folded configuration. The physical domain parameters are next mapped to CA model parameters from the analysis of known structural data available in Protein Data Base (PDB). The process of reverse mapping is implemented to identify the structure of a protein in blind test from its model parameters. The CA model achieves close to 99% correct prediction for secondary structure prediction, while for tertiary structure prediction, the average RMSD (Root Mean Square Deviation) value has been found to 1.82.

Technology plays an important role on the regional competitiveness. In this paper, we built a regional technology diffusion model based on MABS considering agents similar to irregular Cellular Automata model. The results show that under the impact of heterogeneous traffic lines, the traditional center-hinterland diffusion mode has been no longer fit. In reality technology diffusion mode complies with a hub-net structure. Traffic condition plays an important role in regional technology improvement. A preferential tax policy can be conductive to the improvement of the local technology level.

This paper introduces a novel image resizing method for both color and grayscale images. The method could be beneficial in applications where time and quality of the processed images are crucial. The basic idea of the proposed method relies on preserving the edges by partitioning the digital images into homogenous and edge areas during the enlargement process. In addition, the basic fundamentals of Cellular Automata were adopted in order to achieve better performance both in terms of processing time as well as in image quality. By creating appropriate transition rules, the direction of the edges is considered so that every unknown pixel is processed based on its neighbors in order to preserve the quality of the edges. Results demonstrate that the proposed method improves the subjective quality of the enlarged images over conventional resizing methods while keeping the required processing time in low levels.

In the present study, acoustic wave propagation in the field including sound isolation panel is simulated using Cellular Automata (CA). CA is a discrete system which consists of finite state variables, arranged on a uniform grid. CA dynamics is described by a local interaction rule which is used for computation of new state of each cell from the present state at every time step. In this study a sound field is modeled using CA where the sound isolation panel exists and the numerical simulation results are evaluated quantitatively by the insertion loss. The results showed good correspondence with analytical solutions.

In this paper a Cellular Automata-based (CA) path estimation algorithm suitable for safe robot navigation is presented. The proposed method combines well established 3D vision techniques with CA operations and traces a collision free route from the foot of the robot to the horizon of a scene. Firstly, the depth map of the scene is obtained and, then, a polar transformation is applied. A v-disparity image calculation processing step is applied to the initial depth map separating the ground plane from the obstacles. In the next step, a CA floor field is formed representing all the distances from the robot to the traversable regions in the scene. The target point that the robot should move towards to, is tracked down and an additional CA routine is applied to the floor field revealing a traversable route that the robot should follow to reach its target location.

The enteric nervous system (ENS) in our gastrointestinal tract, nicknamed the “second brain”, is responsible for normal gut function and peristaltic contraction. Embryonic development of the ENS involves the colonization of the gut wall from one end to the other by a population of proliferating neural crest (NC) cells. Failure of these cells to invade the whole gut results in the relatively common, potentially fatal condition known as Hirschsprung disease (HSCR). Cellular automata models provide insight into the colonization process at both the individual cell-level and population-level. Our models generated experimentally testable predictions, which have subsequently been confirmed. The model results imply that HSCR is chiefly a NC cell proliferation defect and not, as previously thought, a NC cell motility defect. These results have important implications for HSCR; namely stochastic effects can determine success or failure of the colonization process for a certain range of NC cell proliferation rates.

A cellular-automaton based two-dimensional biofilm detachment module is developed. The module is an improvement of previously presented methodologies for modeling biofilm detachment under the influence of hydrodynamic forces of the moving fluid in which biofilm develops. It uses biofilm mechanical properties that are variable in time and space and are determined by the percentage of each biofilm solid substance—active biomass, extracellular polymeric substance (EPS) and residual dead biomass—and pores that are contained in each cellular automaton compartment in the biofilm column. A methodology is presented that estimates wall shear stresses applied on the biofilm by the fluid for different hydrodynamic conditions and an association with the biofilm mechanical properties is created to predict its detachment. The module is applied in samples created by the UMCCA model [Laspidou and Rittmann, Water Res 38 (2004), 3362-3372].

Agent-based models approximate the behaviour of simple natural and man-made systems. We present a simple cognitive agent capable of evaluating if a strategy has been applied successfully and capable of applying this strategy again with small changes to a similar but new situation. We describe some experimental results, present our conclusions, and outlines future work.

The mechanical behavior of the heart is guided by the propagation of an electrical wave, called action potential. Many diseases have multiple effects on both electrical and mechanical cardiac physiology. To support a better understanding of the multiscale and multiphysics processes involved in physiological and pathological cardiac conditions, a lot of work has been done in developing computational tools to simulate the electro-mechanical behavior of the heart. In this work, we propose a new user-friendly and efficient tool for the electro-mechanical simulation of the cardiac tissue that is based on cellular automata and mass-spring models. The proposed tool offers a user-friendly interface that allows one to interact with the simulation on-the-fly. In addition, the simulator is parallelized with CUDA and OpenMP to further speedup the execution time of the simulations.

We here present the preliminary release of Swii2, a web application for debris flows simulation. The core of the system is Sciddica-k0, the latest release of the Sciddica debris flow Cellular Automata family, already successfully applied to the 1997 Albano lake (Italy) debris flow. In Swii2, the Sciddica-k0 model runs server-side, while a Web 2.0 application controls the simulation. The graphical user interface is based on HTML5 and JavaScript, which permits to have a fully portable application. The client is able to control the basic Sciddica-k0 simulation functionalities thanks to asynchronous callbacks to the server. Simulation results are visualized in real time by means of a 3D interactive visualization system based on WebGL, a cross-platform application program interface used to create 3D graphics in Web browsers. Eventually, user-oriented cooperative services, which desktop applications in general do not offer, are conjectured and discussed.

This work is conducted to investigate how the initial concentration and the severity of HIV which spreads over the lymphoid tissues affect the dynamics of infection, and to what extent?. Therefore, we vary the initial concentration of HIV infected cells,

P

M

_

DC

, and the severity of HIV infected cells,

P

I

_

T

4

, of a stochastic cellular automaton for HIV infection which describes the dynamics of HIV infected cells spreading over a patch of lymphoid tissues. Our results reveal that the variations of

P

M

_

DC

and

P

I

_

T

4

do not change the feature of the dynamics of the model. They affect the dynamics of the model in the following ways: the greater the magnitude of

P

M

_

DC

and

P

I

_

T

4

, the faster the dynamics during the primary phase, and the severity parameter has greater effect on the model than does the HIV’s initial concentration.

We propose a decentralized method for traffic monitoring, fully distributed over the vehicles. An algorithm is provided, specifying which information should be tracked to reconstruct an instantaneous map of traffic flow. We test the accuracy of our method in a simple cellular automata traffic simulation model, for which the traffic condition can be controlled and analyzed theoretically.

For any project management, it is of great interest to improve the accuracy of planning since a delay in the project often causes extra cost. This paper provides a method for dynamical simulation of a project. The results provide probabilistic estimate of project time and gives project manager a chance to make preemptive action to avoid major delay.

The paper studies possibilities of creating an artificial system of image classification and recognition that simulates the functions of the human retina. Cellular automata are used to create such a system. A method for image recognition, rotated to any angle and in the modified scale, is proposed. The proposed methods and schematic technical decisions are simulated.

The objective of the paper is modeling of material softening after the deformation. The main problem of almost every model with digital material representation is consideration of recrystallization as the only mechanism of material softening. Static recovery is introduced into the model based on frontal cellular automata. An influence of static recovery on softening process is twofold. Static recovery effects on a decrease of dislocation density directly and on growing rate of recrystallized grain indirectly. Because of static recovery the recrystallization slows down and the time of recrystallization is extended. Simulation consists of two stages. During the deformation, distortion of the cells, evolution of dislocation density, nucleation and grain growth are considered, while after the deformation, the processes of softening are considered only. Comparison of simulation results with experimental data are presented as well.

In this paper a stochastic model based on a cellular automaton (CA) for describing the spatio-temporal dynamics of fat migration in chocolate confectionery, as well as the resulting fat bloom, is conceived. Several hypotheses on the underlying mechanisms for fat migration exist, but there is no consensus on the correct ones. Although many researchers are studying this industrially important phenomenon, few models describing it have been developed. Therefore, the incorporation of different mechanisms of fat migration into a stochastic CA-based model is discussed and the model parameters are investigated for a better understanding of both the model and the complex fat migration phenomenon.

Textual information in images constitutes a very rich source of high-level semantics for retrieval and indexing. In this paper, a new approach is proposed using Cellular Automata (CA) which strives towards identifying scene text on natural images. Initially, a binary edge map is calculated. Then, taking advantage of the CA flexibility, the transition rules are changing and are applied in four consecutive steps resulting in four time steps CA evolution. Finally, a post-processing technique based on edge projection analysis is employed for high density edge images concerning the elimination of possible false positives. Evaluation results indicate considerable performance gains without sacrificing text detection accuracy.

This work introduces a novel Cellular Automata (CA) model applied for freeway traffic. Besides its capacity for representing basic traffic proprieties, it is capable of representing different drivers behaviors as well as its fluctuation and variation, based on the combination of acceleration and anticipation policy. Both policies are based on normal probabilistic function which represents the nature of unpredictable human behavior. The simulations developed and described herein give rise to a phase diagram which resembles and enriches the fundamental diagram, in its theoretical as well as for real data. Therefore, novel feature proposed herein is normal probabilistic function invoked in both policy (acceleration and anticipation), which allows for a simple group of rules with a few parameters.

The paper deals with a very simple game called

Scintillae

. Like in a domino game, Scintillae provides the player with limited basic pieces that can be placed over a chessboard-like area. After the placement, the game starts in a sort of runtime mode, and the player enjoys his creation. The evolution of the system is based on few basic rules.

Despite its simplicity, Scintillae turns out to provide the player with a powerful mean able to achieve high computational power, storage capabilities and many other peculiarities based on the ability of the player to suitably dispose the pieces.

We show some of the potentials of this simple game by providing basic configurations that can be used as “sub-programs” for composing bigger systems. Moreover, the interest in Scintillae also resides in its potentials for educational purposes, as many basic concepts related to the computer science architecture can be approached with fun by means of this game.

An Analysis on the self-assembly process in DNA tile computing is presented using the cellular automata approach. It is known that a cellular automata model can simulate various complex systems by updating the states of calculation cells based on the local interaction rules. Generally DNA computing is operated through the local interaction between complimentary strands. Therefore the cellular automata approach is suitable to investigate qualitative features of such systems. Focusing on the cryptosystem using a DNA motif called a triple crossover (TX) tile, we construct a new cellular automata model. Our objective is to find a solution to improve the fragmentation problem in the self-assembly process of a calculation sheet of TX tiles, because the fragmentation prevents the system from realizing the sufficient performance. Our results suggest that such fragmentation occurs when the error correction function is lost due to the strong stability of local interaction. It is expected that these findings using cellular automata simulations provide effective information to solve the problems to develop practical applications of DNA-based computation.

The continuing development of smaller electronic devices into the nanometer regime offers great possibilities of highly parallel computing systems, as it allows to reduce power consumption and device sizes and to increase operating speed. Quantum-dot Cellular Automata (QCA) has been proposed as an alternative for nanoelectronic devices and introduces a new opportunity for the design of highly parallel algorithms and architectures. Its benefits are the fast speed, very small size, high density and low energy consumption. These advantages can be very useful for various real time image processing applications. Complex image processing algorithms include in many cases the well-known binary median filter and mathematical morphology operations such as dilation and erosion. In this paper we propose and simulate two innovative QCA circuits which implement the dilation and the erosion.

We show the construction of a rotation- and reflection-invariant local function for a two-dimensional asynchronous cellular automaton with only 3 states and radius 1 Moore neighborhood in which one can implement arbitrary delay-insensitive circuits.

This paper presents a novel scheme to construct circuits on the cell space of an asynchronous cellular automaton that has partitioned cells. The construction process in this scheme is conducted by worm configurations that contain instructions on how to operate. Circuits are constructed by multiple worms, which move around in parallel on the cell space, resulting in an efficient process, as is shown.

Studies of quantum computer implementations suggest cellular quantum computer architectures. These architectures are based on the evolution of quantum cellular automata, which can possibly simulate both quantum and classical physical systems and processes. It is however known that except for the trivial case, unitary evolution of one-dimensional homogeneous quantum cellular automata with one quantum bit (qubit) per cell is not possible because of the no-go lemma. In this paper, we define quantum cellular automata that comprise two qubits per cell and study their evolution using a quantum computer simulator. The evolution is unitary and its linearity manifests itself as a periodic structure in the probability distribution patterns.

In this paper a new procedure has been proposed to synthesize cellular automata (CA) with hybrid rulesets which are very well suited for designing cryptographic primitives. These rulesets are analyzed with respect to nonlinearity, algebraic degree, d-monomial test etc. A new graph theoretic property has also been proposed to analyze the cryptographic strength of cellular automata rules. The randomness of the sequences generated by the rulesets has been tested by NIST test-suite. The experimental results are compared with the existing related works and have shown to be out-performed.

A new Cellular Automata based stream cipher is proposed which is suitable for both hardware and software. It has a non-linear combiner where two non-linear blocks along with a linear block are linearly combined to produce the key-streams. Unlike Non-linear Feedback Shift Register (NFSR) based non-linear combiners, it combines 128-bit blocks using parallel evolution of Cellular Automata (CA) and small CA based S-boxes. The usage of CA prevents the correlation attack and two layers of re-usable small S-boxes prevent the algebraic attacks. The proposed stream cipher takes 128 bits Key and 128 bits of Initial Vector(IV). Theoretically, the cipher operates with an encryption speed of nearly 8 bits per cycle. The initialization process needs 96 cycles which is much faster than Grain and Trivium. This stream cipher is extensible in terms of Key size and provides configurable security and vendor specific implementation option. On implementation, the proposed cipher receives higher throughput than the existing standards.

In this paper we revisit the problem of using Genetic Algorithms to evolve 2-dimensional Cellular Automata (CA) as Pseudo-random Number Generators (PRNG). Our main contribution is two-fold. First, we review the problem of using CAs as PRNGs under the scope of the newer and more demanding batteries of pseudo-random generator tests that have been developed since the introduction of DIEHARD [1]. Second, we introduce a composite fitness metric, that incorporates elements from PRNG tests, to be used in the evolution of the CAs.

Side Channel Attacks (SCA) are one of the most effective means in breaking symmetric key ciphers. Generally, SCA exploits the side-channel leakages output by the implementations of ciphers or introduces defects in the system to analyze them. A number of countermeasures have been proposed to strengthen/remedy implementations of ciphers against SCA. However, none of the countermeasures, to our knowledge, are good enough towards its goal ([16], [19], [3]). In this paper, we emphasis on the necessity of randomness in designing countermeasures against SCA and propose Cellular Automata (CA) based system to thwart SCA. Our countermeasure is also analyzed against popular SCA, such as, differential power attack (DPA), scan-chain based attacks (SC-SCA) and fault attacks (FA).

Lattice-gas cellular automata are often considered as a particular case of cellular automata in which additional constraints apply, such as conservation or spatial exclusion of particles. But what about their updating? How to deal with non-perfect synchrony? Novel definitions of asynchronism are proposed that respect the specificity of lattice-gas models. These definitions are then applied to a well-known swarming rule in order to explore the robustness of the model to perturbations of its updating.

The reversibility issue of 1-dimensional asynchronous cellular automata (ACA) has been reported in [4]. The ACA rules are classified to synthesis reversible ACA. Characterization has been done to explore the update patterns of cells forming the reversible ACA. This work reports synthesis of reversible ACA for pattern generation, where specific Hamming distance between two consecutive ACA states of a cycle is maintained. A hardware realization of ACA is also reported that can effectively be utilized in VLSI circuit design, testing of asynchronous circuit, and Hamming code generation.

A new model for the study of ACA dynamical behavior has been introduced. The classical properties of injectivity, surjectivity and expansivity have been adapted to the new setting. Preliminary results show that the injectivity is almost always equal to surjectivity and that both property are almost always implied by expansivity.

In the classical approach to the mathematical model specification, for space-time complex system, the usual framework is the Partial Difference-Differential Equations system (PDEs). This approach is very hard from a mathematical point of view, and the search for the (PDEs) solutions, almost in the practical applications, often it is impossible. Our approach is based, on the contrary, on Cellular Automata methodology in the framework of Random Field models. The statistical model building methodology for the Random Fields, is based on very simple statistical and probabilistic reasoning that utilize the concept of divisible distributions and logistic non-linear model. The interaction rules for the Cellular Automata mechanism, are built thorough inferential statistics and data analysis.

This paper analyzes the possible limit set structures for the standard threshold block-sequential finite dynamical systems. As a special case of their work on Neural Networks (generalized threshold functions), Goles and Olivos (1981 [2]) showed that for the single block case (parallel update) one may only have fixed points and 2-cycles as

ω

-limit sets. Barrett et al (2006 [1]), but also Goles et al (1990 [3]) as a special case, proved that for the case with

n

blocks (sequential update) the only

ω

-limit sets are fixed points. This paper generalizes and unifies these results to standard threshold systems with block-sequential update schemes.

This work focuses on the set of 32 legal Elementary Cellular Automata. We perform an exhaustive study of the systems’ response under: (i)

α

-asynchronous dynamics, from full asynchronism to perfect synchrony; (ii)

φ

-noise scheme, a perturbation that causes a cell to miscalculate the new state when it is updated. We propose a new classification in three classes under asynchronous conditions:

α

-invariant,

α

-robust and

α

-dependent. We classify the 32 legal automata according to the degree of behavioural modification. We demonstrate that, in the

α

-dependent class, asynchrony behaves as a form of noise in timing. We identify models tolerant to both noise and asynchrony. While the majority of the

α

-invariant class is robust to noise, a subset is not able to recover its original behaviour.

We consider asynchronous one-dimensional cellular automa- ta (CA). It is shown that there is one with von Neumann neighborhood of radius 1 which can simulate each asynchronous one-dimensional cellular automaton. An analogous construction is described for

α

-asynchronous CA (where each cell independently enters a new state with probability

α

. We also point out some generalizations for other updating schemes.

The investigation of crowd dynamics is a complex field of study that involves different types of knowledge and skills, and, also from the socio-psychological perspective, the definition of crowd is still controversial. We propose to investigate analytically this phenomenon focusing on pedestrian dynamics in medium-high density situations, and, in particular, on proxemic behavior of walking groups. In this work we will present several results collected during the observation of the incoming pedestrian flows to an admission test at the University of Milano-Bicocca. In particular, we collected empirical data about: levels of density and of service, group spatial arrangement (degree of alignment and cohesion), group size and composition (gender), walking speed and lane formation. The statistical analysis of video footages of the event showed that a large majority of the incoming flow was composed of groups and that groups size significantly affects walking speed. Collected data will be used for an investigative modeling work aimed at simulating the observed crowd and pedestrian dynamics.

The rule-based CA for simulating the evacuation process of single room with one exit is presented. Analogically to the Floor-Field model, the presented model is based on the movement on rectangular lattice, driven by the potential field generated by the exit. Several ideas of decision-making allowing the agent to choose an occupied cell are implemented, to reflect the observed behaviour in high densities. The velocity of pedestrians is represented by the updating frequency of the individuals. To calibrate model parameters, an experiment “leaving the room” was organized. Based on the observed behaviour, the influence of parameters is discussed and several modifications are suggested.

In this paper a connection of a width of a bottleneck and unidirectional virtual people flow by the SIgMA.CA pedestrian movement model (stochastic Cellular Automata model) is investigated. Specific and full flow rates for different model parameters, initial densities, and bottleneck width are presented and discussed.

Walking through a pathway, a T-junction, and a stairway was modeled by Cellular Automata, introducing local neighbor and transition rules based on the Public Guideline for Evacuation. Setting two types of "personal space" for each pedestrian in one direction and 45˚ inclined direction, a person moves to the next cell at some probability in 24 directions by interpolation of these two patterns. The moving probability was evaluated just for the crowd flow through a straight pathway so that the relationship between density and flow rate might agree with that proposed by the Guideline. It is shown that these flow models can be applied to inclined 24 direction pathways. As the combination of straight pathways, the crowd flow through T-junction was simulated, which showed good agreement with the estimated results according to the Guideline. The flow in a stairway was also simulated in the present paper.

Some real applications of improved cellular automata models are considered. Considered improvement of models concerned the using real data applications from GIS and incorporating the concepts from other methodologies – especially neural networks and learning. We describe models which allow considering different processes in the case of Ukrainian capital Kyiv. Migration processes and voting processes have been considered. New ways of cellular automata development are discussed.

Evacuation simulation was conducted by Cellular Automata in which the local neighbor and state transition rules for movement of pedestrians were satisfied with the occupancy density-flow rate diagram proposed in the Public Guideline for evacuation. As case studies of the proposed algorithm, evacuation from a room with several exits, from three rooms connected to a pathway and a stairway were simulated. The simulation results were compared with the estimated evacuation time calculated by flow rate, number of people, and width of the exits. The simulation results showed good agreement with the estimated evacuation time, and furthermore, it showed precise movement of each person to evacuate from rooms caused by the flow rate change in the process.

This paper describes a model that simulates crowd movement incorporating an efficient follow-the-leader technique based on cellular automata (CA). The scope of the method is to derive principal characteristics of collective motion of biological organisms, such as flocks, swarms or herds and to apply them to the simulation of crowd movement. Thus, the study focuses on the massive form of the movement of individuals, which is lastingly detected macroscopically, during urgent circumstances with the help of some form of guidance. Nevertheless, on a lower level, this formation derives from the application of simple local rules that are applied individually to every single member of the group. Hence, the adoption of CA-based formation has allowed the development of a micro-operating model with macro-features. Furthermore, the model takes advantage of the inherent ability of CA to represent sufficiently phenomena of arbitrary complexity. The response of the model has been evaluated through different simulation scenes that have been developed both in two and three dimensions.

Pike (

Esox lucius

L.) populations have been suffering from habitat degradation and the increasing number of restoration programs had only limited success. In order to set up more effective restoration programmes in the future, it is important to gain insight into the spatio-temporal dynamics of pike. Because no efforts have been spent to develop a spatially explicit model that enables a better understanding of the observed patterns of movement, and actually as a first step towards an integrated spatially explicit model for describing pike dynamics, a model mimicking the movement of pike in the river Yser, Belgium, is proposed.

The article deals with a proxemic approach to evacuation modeling. Proxemics is interpreted as a process of acquisition of space. The authors propose a new, discrete model, based on a more detailed representation of space (taken from the Social Distances Model) and the idea of floor fields. The presented model allows for efficient, real time simulation of evacuation from large facilities using more detailed representation of spatial relations.

We investigate the behavior of evacuation process with steady inflow using the floor field model. By simulations, the metastable state induced by conflicts of pedestrians is observed. The system is controlled by parameters of the inflow and competitiveness of the pedestrians, and large inflow leads to a congested situation. The critical condition of the transition is theoretically derived.

This paper was motivated by an old car racing game played in French schools. The objective of this paper is to model such a car racing system and to find a strategy that allows to move the cars automatically. First the rules of the racing game are given. Then it is modeled as a multi-agent system by GCA-w, a CA related model. An automatic driving strategy is presented in detail. A car moves from the starting line to the arrival line from one temporary goal to the next. The car first searches for the remotest convex point at a border and fixes the next goal nearby it. Then it moves to it stepwise, first accelerating and then decelerating. It is shown that this strategy allows the cars to move automatically around the circuit without bumping against a border.

In this paper, we propose a construction process that enables the transformation of an urban traffic network using a cellular automata lattice. An abstract network hierarchy is defined which allows us to describe the important properties of an urban traffic network layer by layer. The cellular automata lattice is extended with three additional types of cells that permit the modelling of conflict points at intersections. A supporting model of vehicle behaviour based on traffic cellular automata is also extended with rules that allow vehicles to move properly within the extended cellular automata lattice.

In this paper, we propose an effective calibration method of the cellular automaton based microscopic traffic simulation model. We have shown that by utilizing a genetic algorithm it is possible to optimize various model parameters much better than a human expert. Quality of the new model has been shown in task of travel time estimation. We increased precision by more than

25 %

with regard to a manually tuned model. Moreover, we were able to calibrate some model parameters such as driver sensitivity that are extremely difficult to calibrate as relevant data can not be measured using standard monitoring technologies.

The current study investigates the way in which the saturation flow of a traffic lane is representedthrough widely used cellular automata models. In particular, following a literature search specific cellular automata models that have been developed to simulate mainly urban traffic are selected for this study. The values of the saturation flow as these are produced via model simulations with the modification of relevant model parameters including maximum desired speed and probability are defined through appropriate statistical values.

We present a new traffic CA model focused on an estimated time for a following vehicle to catch up with the one ahead (Time-to-Collision: TTC) , and investigate characteristics of the model with the simulation. We also analyze analytically the possibility of a collision between two cars in this model. The model is simulated under open boundary conditions and each car is parallel-updated. We draw some fundamental diagrams of the traffic flow with the simulation. In this figure, we find two distinct phases: a free flow and wide moving jam. And between the two phases, the region where the dots spread sparsely is seen clearly. In addition to this, by using different values of an important parameter, we can see the several patterns of the trajectory of vehicles. Based on these findings, we believe it is possible for this model to reproduce synchronized flow.

The pedal bicycle as a means of transport is gaining new popularity in a world of growing environmental and health concerns. Research relating to bicycles is generally in the area of planning and behaviour, however, flow models that include this non-motorised modality have also been defined, especially for developing-world scenarios. This paper describes a cellular-automata based model for mixed bicycle and motorised traffic on city networks where roads are shared through ‘positional discipline’, as in Dublin and other old city centres. The paper analyses the spatial properties of a particular instance of the model in some detail and presents results that demonstrate them. It also looks at a number of considerations relating to the the model’s implementation.

We demonstrate that Complex automata (CxA) - a hybrid of a Particle method (PM) and Cellular automata (CA) — can serve as a convenient modeling framework in developing advanced models of biological systems. As a proof_of_concept we use two processes of pathogenic growth: cancer proliferation and

Fusarium graminearum

wheat infection. The ability of mimicking both mechanical interactions of tumor with the rest of tissue and penetration properties of

F.graminearum,

confirms that our model can reproduce realistic 3-D dynamics of complex biological phenomena. We discuss the scope of application of CxA in the context of its implementation in CUDA GPU environment.