Home   About Us   eMedicine Search   Drug Development   Feedback   Google Scholar Search   Intranet 
Literature Database   News   Photo Gallery   Publications   Site Map   Site Search   Useful Links 

 Back to  Bioinformatics

Enhanced by Neuroinformation

Cellular Automata

(102 References)

Zhu, H., B. Yin, et al. (2003). "[Simulation application of whole-heart electophysiological model]." Sheng Wu Yi Xue Gong Cheng Xue Za Zhi 20(1): 86-90.

            We invented an efficiently approach to building whole-heart electrophysiological model with cellular automata style massive parallel computing. In this paper, we introduce the simulation facilities of a model we built and the potential application of such model. The first use is to solve the forward problem of electrocardiogram. Simulating arrhythmia ECG and accurately interpreting the significance of various irregular waveforms will be the key goal. Investigating the dynamic property of cardioelectrical activity at cellular and channel levels is the second application, aiming at revealing the mechanism of the generation and sustentation of arrhythmia. Third, the model can be used to research the impacts of artificial interventions on cardioelectrical activity. Electrical defibrillation and pace-making as well as the use of channel block agents are all cases.


Matsukidaira, J. and K. Nishinari (2003). "Euler-lagrange correspondence of cellular automaton for traffic-flow models." Phys Rev Lett 90(8): 088701.

            We propose a Euler-Lagrange transformation for cellular automata (CA) by developing new explicit transformation formulas. This transformation is done in the fully discrete level of variables, and corresponds to the well-known continuous version of it which appears in continuous mechanics such as fluid dynamics and plasma physics. Applying this method to the traffic problem, we have obtained the Lagrange representation of a traffic model, and also succeeded in clarifying the relation between different types of traffic models. It is shown that the Burgers CA, which is a corresponding CA of the continuous Burgers equation, plays a central role in considering this relation.


Manimaran, M., G. L. Snider, et al. (2003). "Scanning tunneling microscopy and spectroscopy investigations of QCA molecules." Ultramicroscopy 97(1-4): 55-63.

            Quantum-dot cellular automata (QCA), a computation paradigm based on the Coulomb interactions between neighboring cells. The key idea is to represent binary information, not by the state of a current switch (transistor), but rather by the configuration of charge in a bistable cell. In its molecular realization, the QCA cell can be a single molecule. QCA is ideally suited for molecular implementation since it exploits the molecule's ability to contain charge, and does not rely on any current flow between the molecules. We have examined using an UHV-STM some of the QCA molecules like silicon phthalocyanines and Fe-Ru complexes on Au (111) and Si (111) surfaces, which are suitable candidates for the molecular QCA approach.


Maass, A. and S. Martinez (2003). "Evolution of probability measures by cellular automata on algebraic topological Markov chains." Biol Res 36(1): 113-8.

            In this paper we review some recent results on the evolution of probability measures under cellular automata acting on a fullshift. In particular we discuss the crucial role of the attractiveness of maximal measures. We enlarge the context of the results of a previous study of topological Markov chains that are Abelian groups; the shift map is an automorphism of this group. This is carried out by studying the dynamics of Markov measures by a particular additive cellular automata. Many of these topics were within the focus of Francisco Varela's mathematical interests.


Lent, C. S., B. Isaksen, et al. (2003). "Molecular quantum-dot cellular automata." J Am Chem Soc 125(4): 1056-63.

            Molecular electronics is commonly conceived as reproducing diode or transistor action at the molecular level. The quantum-dot cellular automata (QCA) approach offers an attractive alternative in which binary information is encoded in the configuration of charge among redox-active molecular sites. The Coulomb interaction between neighboring molecules provides device-device coupling. No current flow between molecules is required. We present an ab initio analysis of a simple molecular system which acts as a molecular QCA cell. The intrinsic bistability of the charge configuration results in dipole or quadrupole fields which couple strongly to the state of neighboring molecules. We show how logic gates can be implemented. We examine the role of the relaxation of nuclear coordinates in the molecular charge reconfiguration.


Kondoh, M. (2003). "High reproductive rates result in high predation risks: a mechanism promoting the coexistence of competing prey in spatially structured populations." Am Nat 161(2): 299-309.

            I tested the hypothesis that spatial structure provides a trade-off between reproduction and predation risk and thereby facilitates predator-mediated coexistence of competing prey species. I compared a cellular automata model to a mean-field model of two prey species and their common predator. In the mean-field model, the prey species with the higher reproductive rate (the superior competitor) always outcompeted the other species (the inferior competitor), both in the presence of and the absence of the predator. In the cellular automata model, both prey species, which differed only in their reproductive rates, coexisted for a long time in the presence of their common predator at intermediate levels of predation. At low predation rates, the superior competitor dominated, while high predation rates favored the inferior competitor. This discrepancy in the results of the different models was due to a trade-off that spontaneously emerged in spatially structured populations; that is, the more clustered distribution of the superior competitor made it more susceptible to predation. In addition, coexistence of competing prey species declined with increasing dispersal ranges of either prey or predator, which suggests that the trade-off that results from spatial structure becomes less important as either prey or predator disperse over a broader range.


Kier, L. B., C. K. Cheng, et al. (2003). "Studies of ligand diffusion pathways over a protein surface." J Chem Inf Comput Sci 43(1): 255-8.

            Studies were conducted on the behavior of simulated molecules diffusing within organized water, postulated to form from the hydropathic states of protein surface amino acid side chains. This organization is postulated to facilitate the diffusion of ligands across the protein surface to their effector. These studies reveal that the organized water can be disrupted in their diffusion facilitating function by the presence of some other solute in high concentration. It was also found from cellular automata simulations that chiral isomers behaved in a slightly different manner when in an asymmetric enclosure simulating a fragment of the organized water pathway. These findings have relevance to observations about the mechanism of action of nonspecific anesthetic agents.


Jiao, J., G. J. Long, et al. (2003). "Building Blocks for the Molecular Expression of Quantum Cellular Automata. Isolation and Characterization of a Covalently Bonded Square Array of Two Ferrocenium and Two Ferrocene Complexes." J Am Chem Soc 125(25): 7522-7523.

            The suitability of [{(eta(5)-C(5)H(5))Fe(eta(5)-C(5)H(4))}(4)(eta(4)-C(4))Co(eta(5)-C(5)H(5)) ][PF(6)](2), [1][PF(6)](2), for use as a molecular quantum cellular automata (QCA) cell is demonstrated. To this end the structure of 1 in the solid state and the conversion of 1 to mono- and dicationic mixed-valence complexes have been accomplished. The latter compounds have been isolated as pure materials and characterized by IR, EPR, and Mossbauer spectroscopies and single-crystal XRD (monocation only) and magnetic susceptibility measurements. Near-IR spectra demonstrate the mixed valence character of the cations (valence trapped on the IR, EPR and Mossbauer time scales), and the energies of the intervalence charge-transfer bands provide a measure of the hole hopping frequency.


Hunt, S. M., M. A. Hamilton, et al. (2003). "A computer investigation of chemically mediated detachment in bacterial biofilms." Microbiology 149(Pt 5): 1155-63.

            A three-dimensional computer model was used to evaluate the effect of chemically mediated detachment on biofilm development in a negligible-shear environment. The model, BacLAB, combines conventional diffusion-reaction equations for chemicals with a cellular automata algorithm to simulate bacterial growth, movement and detachment. BacLAB simulates the life cycle of a bacterial biofilm from its initial colonization of a surface to the development of a mature biofilm with cell areal densities comparable to those in the laboratory. A base model founded on well established transport equations that are easily adaptable to investigate conjectures at the biological level has been created. In this study, the conjecture of a detachment mechanism involving a bacterially produced chemical detachment factor in which high local concentrations of this detachment factor cause the bacteria to detach from the biofilm was examined. The results show that the often observed 'mushroom'-shaped structure can occur if detachment events create voids so that the remaining attached cells look like mushrooms.


Huang, D. W. and W. N. Huang (2003). "Traffic signal synchronization." Phys Rev E Stat Nonlin Soft Matter Phys 67(5-2): 056124.

            The benefits of traffic signal synchronization are examined within the cellular automata approach. The microsimulations of traffic flow are obtained with different settings of signal period T and time delay delta. Both numerical results and analytical approximations are presented. For undersaturated traffic, the green-light wave solutions can be realized. For saturated traffic, the correlation among the traffic signals has no effect on the throughput. For oversaturated traffic, the benefits of synchronization are manifest only when stochastic noise is suppressed.


Hu, R. and X. Ruan (2003). "[A logistic cellular automaton for simulating tumor growth]." Sheng Wu Yi Xue Gong Cheng Xue Za Zhi 20(1): 79-82.

            This paper focuses on a differential equation logistic model simulating tumor growth. We design a kind of tumor dynamic growth model with one-dimensional cellular automata. A discrete logistic model is developed from the continuous logistic model. Based on others' work, we design discrete mathematical growth dynamic model with cellular automaton. In terms of discrete model, we design stochastic evolving rules of cellular automaton. And this paper simulates the tumor growth dynamic model with cellular automata. The theoretic analysis and results of cellular automaton model are in agreement with data from the ideal differential equation logistic growth of cancer.


Hammer, P. E., D. H. Brooks, et al. (2003). "Estimation of entrainment response using electrograms from remote sites: validation in animal and computer models of reentrant tachycardia." J Cardiovasc Electrophysiol 14(1): 52-61.

            INTRODUCTION: Studies suggest that entrainment response (ER) of reentrant tachycardia to overdrive pacing can be estimated using signals from sites other than the paced site. METHODS AND RESULTS: A formula for estimation of ER using remote sites against the difference between the postpacing interval (PPI) and tachycardia cycle length (TCL) determined solely from the paced site signal was validated in experimental data and using a simple two-dimensional cellular automata model of reentry. The model also was used to study the behavior and features of entrained surfaces, including the resetting of tachycardia phase by single premature paced stimuli. Experimental results from 1,484 remote sites in 115 pacing sequences showed the average of the median ER estimate error at each pacing site was -2 +/- 5 msec, and the median ER estimate was within 10 msec of PPI-TCL for 94% of pacing sites. From simulation results, ER at the paced site was accurately estimated from >99.8% of 20,764 remote sites during pacing at 24 sites and three paced cycle lengths. Intervals measured from remote electrograms revealed whether the site was activated orthodromically or nonorthodromically during pacing, and results of simulations illustrated that the portion of the surface activated nonorthodromically during pacing increased with distance from the pacing site to the circuit. The phenomenon of nonorthodromic activation of reentrant circuits predicted by modeling was discernible in measurements taken from the animal model of reentrant tachycardia. Results also showed that, for single premature stimuli that penetrated the tachycardia circuit, phase reset of the tachycardia was linearly related to distance between the central obstacle and the paced site. CONCLUSION: The ER is a complex but predictable perturbation of the global activation sequence of reentrant tachycardias. This predictability allows calculations of the response from anywhere on the perturbed surface. These findings suggest new techniques for measurement of the ER, which may lend themselves to computer-based methods for accurate and rapid mapping of reentrant circuits.


Cannas, S. A., D. E. Marco, et al. (2003). "Modelling biological invasions: species traits, species interactions, and habitat heterogeneity." Math Biosci 183(1): 93-110.

            In this paper we explore the integration of different factors to understand, predict and control ecological invasions, through a general cellular automaton model especially developed. The model includes life history traits of several species in a modular structure interacting multiple cellular automata. We performed simulations using field values corresponding to the exotic Gleditsia triacanthos and native co-dominant trees in a montane area. Presence of G. triacanthos juvenile bank was a determinant condition for invasion success. Main parameters influencing invasion velocity were mean seed dispersal distance and minimum reproductive age. Seed production had a small influence on the invasion velocity. Velocities predicted by the model agreed well with estimations from field data. Values of population density predicted matched field values closely. The modular structure of the model, the explicit interaction between the invader and the native species, and the simplicity of parameters and transition rules are novel features of the model.


Blue, M. and B. W. Bush (2003). "Information content in the Nagel-Schreckenberg cellular automaton traffic model." Phys Rev E Stat Nonlin Soft Matter Phys 67(4 Pt 2): 047103.

            We estimate the set dimension and find bounds for the set entropy of a cellular automaton model for single lane traffic. Set dimension and set entropy, which are measures of the information content per cell, are related to the fractal nature of the automaton [S. Wolfram, Physica D 10, 1 (1989); Theory and Application of Cellular Automata, edited by S. Wolfram (World Scientific, Philadelphia, 1986)] and have practical implications for data compression. For models with maximum speed v(max), the set dimension is approximately log((v(max)+2))2.5, which is close to one bit per cell regardless of the maximum speed. For a typical maximum speed of five cells per time step, the dimension is approximately 0.47.


Van Wijland, F. (2002). "Universality class of nonequilibrium phase transitions with infinitely many absorbing states." Phys Rev Lett 89(19): 190602.

            We consider systems whose steady states exhibit a nonequilibrium phase transition from an active state to one-among an infinite number-absorbing state, as some control parameter is varied across a threshold value. The pair contact process, stochastic fixed-energy sandpiles, activated random walks, and many other cellular automata or reaction-diffusion processes are covered by our analysis. We argue that the upper-critical dimension below which anomalous fluctuation driven scaling appears is d(c)=6, in contrast to a widespread belief. We provide the exponents governing the critical behavior close to or at the transition point to first order in an varepsilon =6-d expansion.


Turcotte, D. L., B. D. Malamud, et al. (2002). "Self-organization, the cascade model, and natural hazards." Proc Natl Acad Sci U S A 99 Suppl 1: 2530-7.

            We consider the frequency-size statistics of two natural hazards, forest fires and landslides. Both appear to satisfy power-law (fractal) distributions to a good approximation under a wide variety of conditions. Two simple cellular-automata models have been proposed as analogs for this observed behavior, the forest fire model for forest fires and the sand pile model for landslides. The behavior of these models can be understood in terms of a self-similar inverse cascade. For the forest fire model the cascade consists of the coalescence of clusters of trees; for the sand pile model the cascade consists of the coalescence of metastable regions.


Testa, B., L. B. Kier, et al. (2002). "A cellular automata model of water structuring by a chiral solute." J Chem Inf Comput Sci 42(3): 712-6.

            The organization of water around a solute molecule with surface features of varying hydropathic states is studied. A stationary solute molecule and mobile water solvent molecules are modeled using cellular automata dynamics. It is shown that varying hydropathic states of solute molecule surface features influence the relative affinities of water for these features. In the case of a simulated chiral solute, a chiral pattern of associated water molecules binding to the surface is produced. This finding is in agreement with published simulations and circular dichroism measurements. A pattern of water molecules at locations beyond the surface of the solute molecules is detected, evidence of an emergent property in this solvent-solute system.


Strain, M. C. and H. Levine (2002). "Comment on "dynamics of HIV infection: a cellular automata approach"." Phys Rev Lett 89(21): 219805.


Skiadas, I. V. and B. K. Ahring (2002). "A new model for anaerobic processes of up-flow anaerobic sludge blanket reactors based on cellular automata." Water Sci Technol 45(10): 87-92.

            The advantageous performance of the UASB reactors is due to the immobilisation of the active biomass, since bacteria coagulate forming aggregates usually called granules. Changes in organic loading rate, hydraulic loading rate or influent substrate composition usually result in changes in granule characteristics and lead to different reactor behaviour. A dynamic mathematical model has been developed for the anaerobic digestion of a glucose based synthetic wastewater in UASB reactors. Cellular automata (CA) theory has been applied to simulate the granule development process. The model takes into consideration that granule diameter and granule microbial composition are functions of the reactor operational parameters and is capable of predicting the UASB performance and the layer structure of the granules.


Sedivy, R., S. Thurner, et al. (2002). "Short-term rhythmic proliferation of human breast cancer cell lines: surface effects and fractal growth patterns." J Pathol 197(2): 163-9.

            Kinetic studies of cell proliferation rates shed light on the growth dynamics of cancer. Most such studies are based on measurements of cell numbers that were evaluated in time intervals of about 12 h. Studies of the initial tumour growth with short measuring intervals are rare. This study was therefore designed with 1 h measuring intervals over a 24 h period. Human breast cancer cell lines (ZR-75-1, SK-BR-3, MCF-7) and a benign cell line (HBL-100) were used to study the hourly thymidine uptake as a measure of cells in synthesis. In parallel experiments, the same cell lines were also exposed to tumour necrosis factor alpha (TNF-alpha) to explore the effect of an apoptosis-inducing substance on initial tumour growth kinetics. In time-evolution plots, there was an oscillation of the labelling index of thymidine uptake for all investigated cell lines, with and without TNF-alpha. Based on the results obtained, a mathematical model was developed mimicking the real experiment. To describe the system dynamically a cellular automaton model was studied. The growth kinetics revealed by the simulation were in accordance with our experimental data. Two- and three-dimensional growth simulations of this computer model yielded objects morphologically similar to real images of human breast cancer. Almost identical fractal dimensions of the virtual and real tumours further supported this visual similarity. The cellular automata models could, therefore, be seen as a bridge towards realistic in vivo scenarios. From a clinical point of view, the results obtained may be applicable not only to primary tumours, but even to tumour cell microfoci and small metastases, which are a major concern in early metastasizing tumours such as breast cancer.


Sachse, F. B., L. G. Blumcke, et al. (2002). "Comparison of macroscopic models of excitation and force propagation in the heart." Biomed Tech (Berl) 47 Suppl 1 Pt 1: 217-20.

            Computer aided simulations of the heart provide knowledge of phenomena, which are commonly neither visible nor measurable with current techniques. This knowledge can be applied e.g. in cardiologic diagnosis and therapy. A variety of models was created to reconstruct cardiac processes, e.g. electrical propagation and force development. In this work different macroscopic models were compared, i.e. models based on excitation-diffusion equations and cellular automata. The comparison was carried out concerning reconstruct-ability of cardiac phenomena, mathematical and biophysical foundation as well as computational expense. Particularly, the reconstruct-ability of electromechanic feedback mechanisms was examined. Perspectives for further developments and improvements of models were given.


Moore, J. H. and L. W. Hahn (2002). "A cellular automata approach to detecting interactions among single-nucleotide polymorphisms in complex multifactorial diseases." Pac Symp Biocomput: 53-64.

            The identification and characterization of susceptibility genes for common complex multifactorial human diseases remains a statistical and computational challenge. Parametric statistical methods such as logistic regression are limited in their ability to identify genes whose effects are dependent solely or partially on interactions with other genes and environmental exposures. We introduce cellular automata (CA) as a novel computational approach for identifying combinations of single-nucleotide polymorphisms (SNPs) associated with clinical endpoints. This alternative approach is nonparametric (i.e. no hypothesis about the value of a statistical parameter is made), is model-free (i.e. assumes no particular inheritance model), and is directly applicable to case-control and discordant sib-pair study designs. We demonstrate using simulated data that the approach has good power for identifying high-order nonlinear interactions (i.e. epistasis) among four SNPs in the absence of independent main effects.


Maree, A. F. and P. Hogeweg (2002). "Modelling Dictyostelium discoideum morphogenesis: the culmination." Bull Math Biol 64(2): 327-53.

            The culmination of the morphogenesis of the cellular slime mould Dictyostelium discoideum involves complex cell movements which transform a mound of cells into a globule of spores on a slender stalk. We show that cyclic AMP signalling and differential adhesion, combined with cell differentiation and slime production, are sufficient to produce the morphogenetic cell movements which lead to culmination. We have simulated the process of culmination using a hybrid cellular automata/partial differential equation model. With our model we have been able to reproduce the main features that occur during culmination, namely the straight downward elongation of the stalk, its anchoring to the substratum and the formation of the long thin stalk topped by the spore head. We conclude that the cyclic AMP signalling system is responsible for the elongation and anchoring of the stalk, but in a roundabout way: pressure waves that are induced by the chemotaxis towards cyclic AMP squeeze the stalk through the cell mass. This mechanism forces the stalk to elongate precisely in the direction opposite to that of the chemotactically moving cells. The process turns out to be 'guided' by inactive 'pathfinder' cells, which form the tip of the stalk. We show that the entire development is enacted by means of the aforementioned building blocks. This means that no global gradients or different modes of chemotaxis are needed to complete the culmination.


Mao, L., H. H. Harris, et al. (2002). "Simple lattice simulation of chiral discrimination in monolayers." J Chem Inf Comput Sci 42(5): 1179-84.

            A simulation method based on cellular automata on a hexagonal lattice is applied to model the behavior of chiral molecules on a surface, such as those in a monolayer of amphiphiles each having a single chiral center. The simulation method includes movement and orientation rules, with the objects ("molecules") on the lattice vertices possessing three different groups with one group pointing along each edge. Periodic boundary conditions are employed in the simulations. Interaction strengths are calculated between pairs of groups occupying the edges between vertices and summed for the entire system. The model successfully reproduces the formation of domains as a consequence of the movement rule. The movement rule can be adjusted to simulate homochiral discrimination or heterochiral discrimination for the case of racemic mixtures. The orientation rule results in a preference for orientations of the molecules that minimize the total interaction strength.


Lenton, T. M. and M. van Oijen (2002). "Gaia as a complex adaptive system." Philos Trans R Soc Lond B Biol Sci 357(1421): 683-95.

            We define the Gaia system of life and its environment on Earth, review the status of the Gaia theory, introduce potentially relevant concepts from complexity theory, then try to apply them to Gaia. We consider whether Gaia is a complex adaptive system (CAS) in terms of its behaviour and suggest that the system is self-organizing but does not reside in a critical state. Gaia has supported abundant life for most of the last 3.8 Gyr. Large perturbations have occasionally suppressed life but the system has always recovered without losing the capacity for large-scale free energy capture and recycling of essential elements. To illustrate how complexity theory can help us understand the emergence of planetary-scale order, we present a simple cellular automata (CA) model of the imaginary planet Daisyworld. This exhibits emergent self-regulation as a consequence of feedback coupling between life and its environment. Local spatial interaction, which was absent from the original model, can destabilize the system by generating bifurcation regimes. Variation and natural selection tend to remove this instability. With mutation in the model system, it exhibits self-organizing adaptive behaviour in its response to forcing. We close by suggesting how artificial life ('Alife') techniques may enable more comprehensive feasibility tests of Gaia.


Kujala, J. V. and T. J. Lukka (2002). "Solutions for certain number-conserving deterministic cellular automata." Phys Rev E Stat Nonlin Soft Matter Phys 65(2 Pt 2): 026115.

            We explain the unexpected behavior of the generalizations of cellular automation traffic models introduced in [H. Fuks and N. Boccara, Int. J. Mod. Phys. C 9, 1 (1998)]. We analyze the steady-state flow in R(m,k) as a function of the initial density; we show that these rules correspond to a system with an infinite number of different kinds of virtual particles interacting according to complex annihilation rules. From simple considerations, we are able to predict the unexpected cutoff of the average flow at unity observed by Fuks and Boccara. We present an efficient algorithm for determining the exact final flow from a given finite initial state. An analysis of this algorithm in the infinite limit using generating functions yields an exact polynomial equation between the flow and density for R(m,k), of maximally 2(m+k)th degree in both.


Knospe, W., L. Santen, et al. (2002). "Human behavior as origin of traffic phases." Phys Rev E Stat Nonlin Soft Matter Phys 65(1 Pt 2): 015101.

            It is shown that the desire for smooth and comfortable driving is directly responsible for the occurrence of synchronized traffic in highway traffic. This desire goes beyond the avoidance of accidents, which so far has been the main focus of microscopic modeling and that is mainly responsible for the other two phases observed empirically, free flow and wide moving jams. These features have been incorporated into a microscopic model based on stochastic cellular automata by means of event-driven anticipation. The results of computer simulations are compared with empirical data. It turns out that anticipation effects are responsible for the stabilization of the traffic phases and even reproduce the empirically observed coexistence of wide moving jams with both free flow and synchronized traffic.


Kier, L. B., C. K. Cheng, et al. (2002). "A cellular automata model of ligand passage over a protein hydrodynamic landscape." J Theor Biol 215(4): 415-26.

            The subject of ligand passage to an active site on a protein is addressed. Current views on the mechanism and the possible role of surface water are discussed. A theory is presented in which the pattern of hydropathic states of protein surface amino acid side chains is invoked as the influence on the relative hydrophobic effects of nearby water. The theory describes a ligand passage through the hydrodynamic near-surface water which exhibits temporary organized cavities resembling the chreodes introduced by Waddington. The passage of the ligand to the active site is facilitated by this dynamic mechanism. Cellular automata models of preferential directional diffusion through these chreodes support the theory. The theory may be invoked to explain a number of ligand-active site observations and serves as an idea for further studies.


Jiang, R., Q. S. Wu, et al. (2002). "Cellular automata model simulating traffic interactions between on-ramp and main road." Phys Rev E Stat Nonlin Soft Matter Phys 66(3 Pt 2A): 036104.

            In this paper, we study the on-ramp system using the cellular automata traffic flow model. Different from previous works, we consider not only the influence of the on-ramp flow on the main road but also the opposite influence. The update rules are given in detail and the concept of priority is introduced. The numerical simulations are carried out and the phase diagram is presented. Two different types of phase diagram are distinguished and the currents of the on-ramp system are discussed.


Imai, K., T. Hori, et al. (2002). "Self-reproduction in three-dimensional reversible cellular space." Artif Life 8(2): 155-74.

            Due to inevitable power dissipation, it is said that nano-scaled computing devices should perform their computing processes in a reversible manner. This will be a large problem in constructing three-dimensional nano-scaled functional objects. Reversible cellular automata (RCA) are used for modeling physical phenomena such as power dissipation, by studying the dissipation of garbage signals. We construct a three-dimensional self-inspective self-reproducing reversible cellular automaton by extending the two-dimensional version SR(8). It can self-reproduce various patterns in three-dimensional reversible cellular space without dissipating garbage signals.


Hutt, M. T., R. Neff, et al. (2002). "Method for detecting the signature of noise-induced structures in spatiotemporal data sets." Phys Rev E Stat Nonlin Soft Matter Phys 66(2 Pt 2): 026117.

            Spatiotemporal stochastic resonance (STSR) is a phenomenon, where the stability of spatial patterns in an extended dynamical system displays a resonance-type dependence on the noise amplitude with the patterns being optimal at intermediate noise level. This dynamical behavior has been found in theoretical systems as well as in biochemical processes, where the noise level has been controlled externally. However, it is an open question how to identify the signature of a spatiotemporal stochastic resonance in a natural system, e.g., in ecology, when the noise amplitude is not known. This question is addressed in the present paper. We provide analysis tools, which allow to reconstruct the noise intensity in a spatiotemporal data set from the data alone. These tools are based on nearest-neighbor considerations inspired by cellular automata and are an appropriate method for detecting STSR, when combined with some measure of spatial order. As a test of our analysis tools, we apply them to sample data generated by four theoretical model systems. We show explicitly that without knowledge of the theoretical value of the noise amplitude for those systems displaying STSR the corresponding resonance curve can be reconstructed from the data alone. In addition, the other (nonresonant) cases are properly identified by our method with no resonance curve being found.


Fuks, H. (2002). "Nondeterministic density classification with diffusive probabilistic cellular automata." Phys Rev E Stat Nonlin Soft Matter Phys 66(6 Pt 2): 066106.

            We present a probabilistic cellular automaton (CA) with two absorbing states which performs classification of binary strings in a nondeterministic sense. In a system evolving under this CA rule, empty sites become occupied with a probability proportional to the number of occupied sites in the neighborhood, while occupied sites become empty with a probability proportional to the number of empty sites in the neighborhood. The probability that all sites become eventually occupied is equal to the density of occupied sites in the initial string.


Faraudo, J. and J. Bafaluy (2002). "Computer simulation study of irreversible adsorption: coverage fluctuations." Phys Rev E Stat Nonlin Soft Matter Phys 65(3 Pt 2B): 037101.

            In this paper, we develop a cellular automata model to study the coverage fluctuations in monolayers of irreversible adsorbed particles. The effect of bulk diffusion and excluded volume interactions between adsorbed and incoming particles on coverage fluctuations is analyzed by simulations and analytically. We also show that the macroscopic boundary and initial conditions imposed at the system (open or closed cell) determine the effect of these factors on coverage fluctuations. In fact, under certain conditions, the excluded volume interactions only influence fluctuations near the jamming limit.


Dedecker, A. P., P. L. Goethals, et al. (2002). "Comparison of Artificial Neural Network (ANN) Model Development Methods for Prediction of Macroinvertebrate Communities in the Zwalm River Basin in Flanders, Belgium." ScientificWorldJournal 2(1): 96-104.

            Modelling has become an interesting tool to support decision making in water management. River ecosystem modelling methods have improved substantially during recent years. New concepts, such as artificial neural networks, fuzzy logic, evolutionary algorithms, chaos and fractals, cellular automata, etc., are being more commonly used to analyse ecosystem databases and to make predictions for river management purposes. In this context, artificial neural networks were applied to predict macroinvertebrate communities in the Zwalm River basin (Flanders, Belgium). Structural characteristics (meandering, substrate type, flow velocity) and physical and chemical variables (dissolved oxygen, pH) were used as predictive variables to predict the presence or absence of macroinvertebrate taxa in the headwaters and brooks of the Zwalm River basin. Special interest was paid to the frequency of occurrence of the taxa as well as the selection of the predictors and variables to be predicted on the prediction reliability of the developed models. Sensitivity analyses allowed us to study the impact of the predictive variables on the prediction of presence or absence of macroinvertebrate taxa and to define which variables are the most influential in determining the neural network outputs.


Bub, G. and A. Shrier (2002). "Propagation through heterogeneous substrates in simple excitable media models." Chaos 12(3): 747-753.

            The interaction of waves and obstacles is simulated by adding heterogeneities to a FitzHugh-Nagumo model and a cellular automata model. The cellular automata model is formulated to account for heterogeneities by modelling the interaction between current sources and current sinks. In both models, wave fronts propagate if the size of the heterogeneities is small, and block if the size of the heterogeneities is large. For intermediate values, wave fronts break up into numerous spiral waves. The theoretical models give insights concerning spiral wave formation in heterogeneous excitable media. (c) 2002 American Institute of Physics.


Bernaschi, M. and F. Castiglione (2002). "Selection of escape mutants from immune recognition during HIV infection." Immunol Cell Biol 80(3): 307-13.

            We present computer simulations of the HIV infection based ona sophisticated cellular automata model of the immune response.The infection progresses following the well-known three-phase dynamics observed in patients, that is, acute, silent and acquired immunodeficiency.Antigenic shift and selection of escape viral mutants with low transcription rate explain the long term course of the asymptomatic phase, while the immunodeficiency status appears to be the consequence of a drastic reduction in T helper cell repertoire.


Amar, P., P. Ballet, et al. (2002). "Hyperstructures, genome analysis and I-cells." Acta Biotheor 50(4): 357-73.

            New concepts may prove necessary to profit from the avalanche of sequence data on the genome, transcriptome, proteome and interactome and to relate this information to cell physiology. Here, we focus on the concept of large activity-based structures, or hyperstructures, in which a variety of types of molecules are brought together to perform a function. We review the evidence for the existence of hyperstructures responsible for the initiation of DNA replication, the sequestration of newly replicated origins of replication, cell division and for metabolism. The processes responsible for hyperstructure formation include changes in enzyme affinities due to metabolite-induction, lipid-protein affinities, elevated local concentrations of proteins and their binding sites on DNA and RNA, and transertion. Experimental techniques exist that can be used to study hyperstructures and we review some of the ones less familiar to biologists. Finally, we speculate on how a variety of in silico approaches involving cellular automata and multi-agent systems could be combined to develop new concepts in the form of an Integrated cell (I-cell) which would undergo selection for growth and survival in a world of artificial microbiology.


Afraimovich, V., F. C. Ordaz, et al. (2002). "A class of cellular automata modeling winnerless competition." Chaos 12(2): 279-288.

            Neural units introduced by Rabinovich et al. ("Sensory coding with dynamically competitive networks," UCSD and CIT, February 1999) motivate a class of cellular automata (CA) where spatio-temporal encoding is feasible. The spatio-temporal information capacity of a CA is estimated by the information capacity of the attractor set, which happens to be finitely specified. Two-dimensional CA are studied in detail. An example is given for which the attractor is not a subshift. (c) 2002 American Institute of Physics.


Zorzenon dos Santos, R. M. and S. Coutinho (2001). "Dynamics of HIV infection: a cellular automata approach." Phys Rev Lett 87(16): 168102.

            We use a cellular automata model to study the evolution of human immunodeficiency virus (HIV) infection and the onset of acquired immunodeficiency syndrome (AIDS). The model takes into account the global features of the immune response to any pathogen, the fast mutation rate of the HIV, and a fair amount of spatial localization, which may occur in the lymph nodes. Our results reproduce the three-phase pattern observed in T cell and virus counts of infected patients, namely, the primary response, the clinical latency period, and the onset of AIDS. The dynamics of real experimental data is related to the transient behavior of our model and not to its steady state. We have also found that the infected cells organize themselves into spatial structures, which are responsible for the decrease on the concentration of uninfected cells, leading to AIDS.


Zhu, H., B. Yin, et al. (2001). "[Computing ECG based on action potential of single cardiac cell]." Sheng Wu Yi Xue Gong Cheng Xue Za Zhi 18(4): 511-4, 519.

            This paper introduces an ECG computing algorithm that computes ECG based on the action potential of single cardiac cell. Taking solid angle analysis as tool, this algorithm analyzes the field potential of a cardiac cell that connects and communicates with neighboring cells. This algorithm has been implemented in our electrophysiological model CardioAuto, which was built with extended Cellular 3.0-a cellular automata system. Algorithm and simulation results reveal that it is the transmembrane potential slope among cell group that contributes to ECG waveform generation and determines the waveform deflection. To a specific lead location, whenever cell group has a transmembrane potential slope that proximal end is higher than distal end, a downward ECG deflection is generated. Whenever cell group has a reverse transmembrane potential slope, an upward ECG deflection is generated. Whenever there is no transmembrane potential slope, ECG keeps on baseline. According to our algorithm, the significance of normal and many abnormal ECG waveforms can be analyzed and interpreted at cellular level.


Wootton, J. T. (2001). "Local interactions predict large-scale pattern in empirically derived cellular automata." Nature 413(6858): 841-4.

            An important unanswered question in ecology is whether processes such as species interactions that occur at a local scale can generate large-scale patterns seen in nature. Because of the complexity of natural ecosystems, developing an adequate theoretical framework to scale up local processes has been challenging. Models of complex systems can produce a wide array of outcomes; therefore, model parameter values must be constrained by empirical information to usefully narrow the range of predicted behaviour. Under some conditions, spatially explicit models of locally interacting objects (for example, cells, sand grains, car drivers, or organisms), variously termed cellular automata or interacting particle models, can self-organize to develop complex spatial and temporal patterning at larger scales in the absence of any externally imposed pattern. When these models are based on transition probabilities of moving between ecological states at a local level, relatively complex versions of these models can be linked readily to empirical information on ecosystem dynamics. Here, I show that an empirically derived cellular automaton model of a rocky intertidal mussel bed based on local interactions correctly predicts large-scale spatial patterns observed in nature.


Tyson, J. J. and M. C. Mackey (2001). "Molecular, metabolic, and genetic control: An introduction." Chaos 11(1): 81-83.

            The living cell is a miniature, self-reproducing, biochemical machine. Like all machines, it has a power supply, a set of working components that carry out its necessary tasks, and control systems that ensure the proper coordination of these tasks. In this Special Issue, we focus on the molecular regulatory systems that control cell metabolism, gene expression, environmental responses, development, and reproduction. As for the control systems in human-engineered machines, these regulatory networks can be described by nonlinear dynamical equations, for example, ordinary differential equations, reaction-diffusion equations, stochastic differential equations, or cellular automata. The articles collected here illustrate (i) a range of theoretical problems presented by modern concepts of cellular regulation, (ii) some strategies for converting molecular mechanisms into dynamical systems, (iii) some useful mathematical tools for analyzing and simulating these systems, and (iv) the sort of results that derive from serious interplay between theory and experiment. (c) 2001 American Institute of Physics.


Sun, X., D. Wang, et al. (2001). "Fractal and chaotic behavior of circular cellular automata." Phys Rev E Stat Nonlin Soft Matter Phys 64(3-2): 036105.

            A new type of circular cellular automata (CCA) has been introduced. The evolutions of the CCA obtained by the clockwise, anticlockwise, and scanning line-by-line site sequence in the successively growing rings divided from a square lattice are studied. The evolution seems to form a twisty fishnet when the CCA are grown by the first two sequences. Sierpinski triangle gasket or the modulated ones are formed in the fourth quadrant of the CCA grown by the line scanning sequence. Fractal analysis is used to characterize the relationships between the pattern formed and the initial position of the growing ring and it is found that the pattern is very sensitive to the initial growth condition, showing the chaotic behavior.


Oliveira, G. M., P. P. de Oliveira, et al. (2001). "Definition and application of a five-parameter characterization of one-dimensional cellular automata rule space." Artif Life 7(3): 277-301.

            Cellular automata (CA) are important as prototypical, spatially extended, discrete dynamical systems. Because the problem of forecasting dynamic behavior of CA is undecidable, various parameter-based approximations have been developed to address the problem. Out of the analysis of the most important parameters available to this end we proposed some guidelines that should be followed when defining a parameter of that kind. Based upon the guidelines, new parameters were proposed and a set of five parameters was selected; two of them were drawn from the literature and three are new ones, defined here. This article presents all of them and makes their qualities evident. Then, two results are described, related to the use of the parameter set in the Elementary Rule Space: a phase transition diagram, and some general heuristics for forecasting the dynamics of one-dimensional CA. Finally, as an example of the application of the selected parameters in high cardinality spaces, results are presented from experiments involving the evolution of radius-3 CA in the Density Classification Task, and radius-2 CA in the Synchronization Task.


Molofsky, J., J. D. Bever, et al. (2001). "Coexistence under positive frequency dependence." Proc R Soc Lond B Biol Sci 268(1464): 273-7.

            Negative frequency dependence resulting from interspecific interactions is considered a driving force in allowing the coexistence of competitors. While interactions between species and genotypes can also result in positive frequency dependence, positive frequency dependence has usually been credited with hastening the extinction of rare types and is not thought to contribute to coexistence. In the present paper, we develop a stochastic cellular automata model that allows us to vary the scale of frequency dependence and the scale of dispersal. The results of this model indicate that positive frequency dependence will allow the coexistence of two species at a greater rate than would be expected from chance. This coexistence arises from the generation of banding patterns that will be stable over long time-periods. As a result, we found that positive frequency-dependent interactions over local spatial scales promote coexistence over neutral interactions. This result was robust to variation in boundary conditions within the simulation and to variation in levels of disturbance. Under all conditions, coexistence is enhanced as the strength of positive frequency-dependent interactions is increased.


Mitchell, M. (2001). "Life and evolution in computers." Hist Philos Life Sci 23(3-4): 361-83.

            This paper argues for the possibility of 'artificial life' and computational evolution, first by discussing (via a highly simplified version) John von Neumann's self-reproducing automation and then by presenting some recent work focusing on computational evolution, in which 'cellular automata', a form of parallel and decentralized computing system, are evolved via 'genetic algorithms'. It is argued that such in silico experiments can help to make sense of the question of whether we can eventually build computers that are intelligent and alive.


Li, X., Q. Wu, et al. (2001). "Cellular automaton model considering the velocity effect of a car on the successive car." Phys Rev E Stat Nonlin Soft Matter Phys 64(6 Pt 2): 066128.

            In this paper we present a cellular automata model for one-lane traffic flow. The update rules of velocity of a car depend not only on the positions of this car and the car ahead of it, but also on the velocities of the two cars. Using computer simulations we obtain some basic qualitative results and the fundamental diagram of the proposed model. In comparison with those of the existing models in the literature, we find that the fundamental diagram of the proposed model is more consistent with the results measured in the real traffic, and the model is able to reproduce some relevant macroscopic states that are found in the real traffic flow but cannot be predicted by the existing models.


Lee, K. M., H. Xu, et al. (2001). "Parity problem with a cellular automaton solution." Phys Rev E Stat Nonlin Soft Matter Phys 64(2 Pt 2): 026702.

            The parity of a bit string of length N is a global quantity that can be efficiently computed using a global counter in O(N) time. But is it possible to find the parity using cellular automata with a set of local rule tables without using any global counter? Here, we report a way to solve this problem using a number of r=1 binary, uniform, parallel, and deterministic cellular automata applied in succession for a total of O(N2) time.


Kreft, J. U., C. Picioreanu, et al. (2001). "Individual-based modelling of biofilms." Microbiology 147(Pt 11): 2897-912.

            Understanding the emergence of the complex organization of biofilms from the interactions of its parts, individual cells and their environment, is the aim of the individual-based modelling (IbM) approach. This IbM is version 2 of BacSim, a model of Escherichia coli colony growth, which was developed into a two-dimensional multi-substrate, multi-species model of nitrifying biofilms. It was compared with the established biomass-based model (BbM) of Picioreanu and others. Both models assume that biofilm growth is due to the processes of diffusion, reaction and growth (including biomass growth, division and spreading). In the IbM, each bacterium was a spherical cell in continuous space and had variable growth parameters. Spreading of biomass occurred by shoving of cells to minimize overlap between cells. In the BbM, biomass was distributed in a discrete grid and each species had uniform growth parameters. Spreading of biomass occurred by cellular automata rules. In the IbM, the effect of random variation of growth parameters of individual bacteria was negligible in contrast to the E. coli colony model, because the heterogeneity of substrate concentrations in the biofilm was more important. The growth of a single cell into a clone, and therefore also the growth of the less abundant species, depended on the randomly chosen site of attachment, owing to the heterogeneity of substrate concentrations in the biofilm. The IbM agreed with the BbM regarding the overall growth of the biofilm, due to the same diffusion-reaction processes. However, the biofilm shape was different due to the different biomass spreading mechanisms. The IbM biofilm was more confluent and rounded due to the steady, deterministic and directionally unconstrained spreading of the bacteria. Since the biofilm shape is influenced by the spreading mechanism, it is partially independent of growth, which is driven by diffusion-reaction. Chance in initial attachment events modifies the biofilm shape and the growth of single cells because of the high heterogeneity of substrate concentrations in the biofilm, which again results from the interaction of diffusion-reaction with spreading. This stresses the primary importance of spreading and chance in addition to diffusion-reaction in the emergence of the complexity of the biofilm community.


Kier, L. B. and L. H. Hall (2001). "Molecular connectivity: intermolecular accessibility and encounter simulation." J Mol Graph Model 20(1): 76-83.

            The simple molecular connectivity indices are interpreted as summations of bond accessibilities to bimolecular encounters with another, identical molecule. To transcend this model, a molecule is treated as disjecta membra with each bond modeled as a discrete cell in a dynamic simulation of many molecules. Each bond accessibility is transformed into a cellular automata rule. The dynamics are run for each of 38 alkanes, recording the average number of cell encounters, beta. The beta values show a high correlation with the boiling points. The significance of the bond accessibilities and the concept of intermolecular encounters explaining the molecular connectivity indices is supported by these findings.


Ichinose, S. I. (2001). "Transient structures of wave patterns arising in the wave regeneration of subalpine coniferous forests." Phys Rev E Stat Nonlin Soft Matter Phys 64(6 Pt 1): 061903.

            In wave-regeneration phenomena observed in the subalpine coniferous forests, mainly consisting of Abies species, the blighted forests present various shapes in the course of development, spots at the initial stage turning into arches and finally into long whitish stripes. Because the wave-regeneration could not be followed in the field without long term studies, a simple model has been elaborated to simulate the various different dieback structures observed in the real forests. This model, based on cellular automata, is employed to analyze the power spectral density of canopy tree height fluctuations in the wave-regenerated forests. The results demonstrate that almost all the dieback structures observed in the field can be generated by this simple model, by varying the wind direction and its strength by some stochasticity. The power spectrum density presents various shapes in the course of development, white noise type at the initial stage turning into Lorentz type and finally into 1/f type power spectrum (spatial Fourier frequency).


Hermanowicz, S. W. (2001). "A simple 2D biofilm model yields a variety of morphological features." Math Biosci 169(1): 1-14.

            A two-dimensional biofilm model was developed based on the concept of cellular automata. Three simple, generic processes were included in the model: cell growth, internal and external mass transport and cell detachment (erosion). The model generated a diverse range of biofilm morphologies (from dense layers to open, mushroom-like forms) similar to those observed in real biofilm systems. Bulk nutrient concentration and external mass transfer resistance had a large influence on the biofilm structure.


Hauert, C. (2001). "Fundamental clusters in spatial 2x2 games." Proc R Soc Lond B Biol Sci 268(1468): 761-9.

            The notion of fundamental clusters is introduced, serving as a rule of thumb to characterize the statistical properties of the complex behaviour of cellular automata such as spatial 2 x 2 games. They represent the smallest cluster size determining the fate of the entire system. Checking simple growth criteria allows us to decide whether the cluster-individuals, e.g. some mutant family, are capable of surviving and invading a resident population. In biology, spatial 2 x 2 games have a broad spectrum of applications ranging from the evolution of cooperation and intraspecies competition to disease spread. This methodological study allows simple classifications and long-term predictions in various biological and social models to be made. For minimal neighbourhood types, we show that the intuitive candidate, a 3 x 3 cluster, turns out to be fundamental with certain weak limitations for the Moore neighbourhood but not for the Von Neumann neighbourhood. However, in the latter case, 2 x 2 clusters generally serve as reliable indicators to whether a strategy survives. Stochasticity is added to investigate the effects of varying fractions of one strategy present at initialization time and to discuss the rich dynamic properties in greater detail. Finally, we derive Liapunov exponents for the system and show that chaos reigns in a small region where the two strategies coexist in dynamical equilibrium.


Haire, T. J., P. S. Ganney, et al. (2001). "An investigation into the feasibility of implementing fractal paradigms to simulate cancellous bone structure." Comput Methods Biomech Biomed Engin 4(4): 341-54.

            Cancellous bone consists of a framework of solid trabeculae interspersed with bone marrow. The structure of the bone tissue framework is highly convoluted and complex, being fractal and statistically self-similar over a limited range of magnifications. To date, the structure of natural cancellous bone tissue has been defined using 2D and 3D imaging, with no facility to modify and control the structure. The potential of four computer-generated paradigms has been reviewed based upon knowledge of other fractal structures and chaotic systems, namely Diffusion Limited Aggregation (DLA), Percolation and Epidemics, Cellular Automata, and a regular Grid with randomly relocated nodes. The resulting structures were compared for their ability to create realistic structures of cancellous bone rather than reflecting growth and form processes. Although the creation of realistic computer-generated cancellous bone structures is difficult, it should not be impossible. Future work considering the combination of fractal and chaotic paradigms is underway.


Gisiger, T. (2001). "Scale invariance in biology: coincidence or footprint of a universal mechanism?" Biol Rev Camb Philos Soc 76(2): 161-209.

            In this article, we present a self-contained review of recent work on complex biological systems which exhibit no characteristic scale. This property can manifest itself with fractals (spatial scale invariance), flicker noise or 1/f-noise where f denotes the frequency of a signal (temporal scale invariance) and power laws (scale invariance in the size and duration of events in the dynamics of the system). A hypothesis recently put forward to explain these scale-free phenomomena is criticality, a notion introduced by physicists while studying phase transitions in materials, where systems spontaneously arrange themselves in an unstable manner similar, for instance, to a row of dominoes. Here, we review in a critical manner work which investigates to what extent this idea can be generalized to biology. More precisely, we start with a brief introduction to the concepts of absence of characteristic scale (power-law distributions, fractals and 1/f-noise) and of critical phenomena. We then review typical mathematical models exhibiting such properties: edge of chaos, cellular automata and self-organized critical models. These notions are then brought together to see to what extent they can account for the scale invariance observed in ecology, evolution of species, type III epidemics and some aspects of the central nervous system. This article also discusses how the notion of scale invariance can give important insights into the workings of biological systems.


Galam, S. and J. P. Radomski (2001). "Cancerous tumor: The high frequency of a rare event." Phys Rev E Stat Nonlin Soft Matter Phys 63(5 Pt 1): 051907.

            A simple model for cancer growth is presented using cellular automata. Cells diffuse randomly on a two-dimensional square lattice. Individual cells can turn cancerous at a very low rate. During each diffusive step, local fights may occur between healthy and cancerous cells. Associated outcomes depend on some biased local rules, which are independent of the overall cancerous cell density. The models unique ingredients are the frequency of local fights and the bias amplitude. While each isolated cancerous cell is eventually destroyed, an initial two-cell tumor cluster is found to have a nonzero probabilty to spread over the whole system. The associated phase diagram for survival or death is obtained as a function of both the rate of fight and the bias distribution. Within the model, although the occurrence of a killing cluster is a very rare event, it turns out to happen almost systematically over long periods of time, e.g., on the order of an adults life span. Thus, after some age, survival from tumorous cancer becomes random.


Fuk, sacute, et al. (2001). "Convergence to equilibrium in a class of interacting particle systems evolving in discrete time." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 64(1-2): 016117.

            We conjecture that for a wide class of interacting particle systems evolving in discrete time, namely, conservative cellular automata with piecewise linear flow diagrams, relaxation to the limit set follows the same power law at critical points. We further describe the structure of the limit sets of such systems as unions of shifts of finite type. Relaxation to the equilibrium resembles ballistic annihilation, with "defects" propagating in opposite directions annihilating upon collision.


Di Paolo, E. A. (2001). "Rhythmic and non-rhythmic attractors in asynchronous random Boolean networks." Biosystems 59(3): 185-95.

            In multi-component, discrete systems, such as Boolean networks and cellular automata, the scheme of updating of the individual elements plays a crucial role in determining their dynamic properties and their suitability as models of complex phenomena. Many interesting properties of these systems rely heavily on the use of synchronous updating of the individual elements. Considerations of parsimony have motivated the claim that, if the natural systems being modelled lack any clear evidence of synchronously driven elements, then random asynchronous updating should be used by default. The introduction of a random element precludes the possibility of strictly cyclic behaviour. In principle, this poses the question of whether asynchronously driven Boolean networks, cellular automata, etc., are inherently bad choices at the time of modelling rhythmic phenomena. This paper focuses on this subsidiary issue for the case of Asynchronous Random Boolean Networks (ARBNs). It defines measures of pseudo-periodicity between states and sufficiently relaxed statistical constraints. These measures are used to guide a genetic algorithm to find appropriate examples. Success in this search for a number of cases, and the subsequent statistical analysis lead to the conclusion that ARBNs can indeed be used as models of co-ordinated rhythmic phenomena, which may be stronger precisely because of their in-built asynchrony. The same technique is used to find non-stationary attractors that show no rhythm. Evidence suggests that the latter are more abundant than rhythmic attractor. The methodology is flexible, and allows for more demanding statistical conditions for defining pseudo-periodicity, and constraining the evolutionary search.


Capcarrere, M. S. and M. Sipper (2001). "Necessary conditions for density classification by cellular automata." Phys Rev E Stat Nonlin Soft Matter Phys 64(3-2): 036113.

            Classifying the initial configuration of a binary-state cellular automaton (CA) as to whether it contains a majority of 0s or 1s-the so-called density-classification problem-has been studied over the past decade by researchers wishing to glean an understanding of how locally interacting systems compute global properties. In this paper we prove two necessary conditions that a CA must satisfy in order to classify density: (1) the density of the initial configuration must be conserved over time, and (2) the rule table must exhibit a density of 0.5.


Camara, G. and A. M. Monteiro (2001). "Geocomputation techniques for spatial analysis: are they relevant to health data?" Cad Saude Publica 17(5): 1059-71, discussion 1072-81.

            Geocomputation is an emerging field of research that advocates the use of computationally intensive techniques such as neural networks, heuristic search, and cellular automata for spatial data analysis. Since increasing amounts of health-related data are collected within a geographical frame of reference, geocomputational methods show increasing potential for health data analysis. This paper presents a brief survey of the geocomputational field, including some typical applications and references for further reading.


Bernaschi, M. and F. Castiglione (2001). "Design and implementation of an immune system simulator." Comput Biol Med 31(5): 303-31.

            Cellular automata based models have proven capable of providing several new insights into the dynamics of the immune system (IS) response.A qualitative picture of the IS behavior can be obtained with small-scale simulations. However, for a more detailed analysis and to further validate the models, large-scale simulations are required.To this purpose we present here a simulator (PARIMM) of the IS response which has been carefully designed and coded to allow such simulations (millions of cells with a very high degree of complexity). The code does not just resort to parallel processing to run faster. Data structures and I/O have been optimized as well to limit the (huge) memory and disk space requirements.The recent addition of the description of the T killer cellular mediated response allows the code to simulate both humoral and cellular immune reactions.All these features put PARIMM among the most complete simulators of the immune system developed up today.


Albat, R. (2001). "Scaling theory and spreading dynamics in systems with one absorbing state derived from an equilibrium statistical model." Phys Rev E Stat Nonlin Soft Matter Phys 64(2 Pt 2): 026113.

            We show that for systems with one absorbing state, the widely assumed scaling properties of the survival probability and of the probability density of the size of activity avalanches cannot be true in the asymptotic limit. Trying to answer the question, what is the true asymptotic limit of these quantities, we study Domany-Kinzel probabilistic cellular automata using an equilibrium statistical mechanic model (ESM). We are able to express important quantities of the avalanche dynamics by correlation functions of the ESM. The application of scaling theory to the ESM allows for the derivation of the scaling properties of quantities of the avalanche dynamics in the form of infinite series. From these results we can obtain possible solutions for the apparent scaling problem, but cannot decide definitely which one is true. The most appealing solution, for which some evidence is given, states that there is a narrow range around the critical point in which, for example, the survival probability has the same power-law behavior as on the critical point. Outside this narrow range, the usually assumed scaling should be approximately valid.


Wurthner, J. U., A. K. Mukhopadhyay, et al. (2000). "A cellular automaton model of cellular signal transduction." Comput Biol Med 30(1): 1-21.

            On the basis of cellular automata models, a software specifically tailored to model biochemical reactions involved in cellular signal transduction was implemented on a personal computer. Recent data regarding desensitization processes in mouse Leydig cells are used to simulate the underlying reactions of signal transduction. Pretreatment of real Leydig cells with different molecules results in a modification of the signal transduction cascade leading to a diminished response of the cells during subsequent stimulations. The model is capable of simulating the complex behavior of this intracellular second messenger production in a qualitative and semi-quantitative way. The results indicate that quantitative simulations on a molecular level will be possible once appropriate computer hardware is available. The simulations and results of the cellular automaton presented are easily described and comprehended, which make it a useful tool that will facilitate research in cellular signal transduction and other fields covering complex reaction networks.


Tolle, C. R., J. L. Budzien, et al. (2000). "Do dynamical systems follow Benford's law?" Chaos 10(2): 331-336.

            Data compiled from a variety of sources follow Benford's law, which gives a monotonically decreasing distribution of the first digit (1 through 9). We examine the frequency of the first digit of the coordinates of the trajectories generated by some common dynamical systems. One-dimensional cellular automata fulfill the expectation that the frequency of the first digit is uniform. The molecular dynamics of fluids, on the other hand, provides trajectories that follow Benford's law. Finally, three chaotic systems are considered: Lorenz, Henon, and Rossler. The Lorenz system generates trajectories that follow Benford's law. The Henon system generates trajectories that resemble neither the uniform distribution nor Benford's law. Finally, the Rossler system generates trajectories that follow the uniform distribution for some parameters choices, and Benford's law for others. (c) 2000 American Institute of Physics.


Stark, W. R. and W. H. Hughes (2000). "Asynchronous, irregular automata nets: the path not taken." Biosystems 55(1-3): 107-17.

            This is a prelude to, and an extension of the original paper Artificial tissue models (Stark, R., 1994. The topology and analysis of asynchronous processes. http://www.math.usf.edu/ approximately stark/documents). However, this exposition is designed for a broader audience - anyone working in biological information processing. A primary objective is to demonstrate that irregular asynchronous automata nets, as opposed to cellular automata, are a realistic approach to modeling biological information processing. Also, new material is presented. Sections 1 and 2 review the early history of von Neumann's attempt explore biological information processing and finally the emergence of cellular automata. The history is guided by the question of why John von Neumann knowingly (we believe) compromised his investigation of biological information processing by falling back to the model we now know as cellular automata. Section 3 defines and explores examples of cellular automata and artificial tissue. Sections 4 and 5 contain philosophical observations which unify our paper, and propose an answer to the original question. A new model for Turing's leopards' spot problem is presented. The asynchronous models are defined by a cell program and a local commumications protocol only. Computational freedom comes from asynchronous activity, while global organization emerges from the entropy reducing nature of the cell programs.


Rocha, L. M. (2000). "Syntactic autonomy. Why there is no autonomy without symbols and how self-organizing systems might evolve them." Ann N Y Acad Sci 901: 207-23.

            Two different types of agency are discussed that are based on dynamically coherent and incoherent couplings with an environment, respectively. I propose that until a private syntax (syntactic autonomy) is discovered by dynamically coherent agents, there are no significant or interesting types of closure or autonomy. When syntactic autonomy is established, then, because of a process of description-based selected self-organization, open-ended evolution is enabled. At this stage, in addition to dynamics, agents depend on localized, symbolic memory, thus adding a level of dynamic incoherence to their interaction with the environment. Furthermore, it is the appearance of syntactic autonomy that enables much more interesting types of closures among agents sharing the same syntax. To investigate how we can study the emergence of syntax from dynamic systems, experiments with cellular automata leading to emergent computation that solves nontrivial tasks are discussed. RNA editing is also mentioned as a process that may have been used to obtain a primordial biological code necessary for open-ended evolution.


Nowak, A., R. R. Vallacher, et al. (2000). "Society of self: the emergence of collective properties in self-structure." Psychol Rev 107(1): 39-61.

            Using cellular automata, the authors show how mutual influences among elements of self-relevant information give rise to dynamism, differentiation, and global evaluation in self-concept. The model assumes a press for integration that promotes internally generated dynamics and enables the self-structure to operate as a self-organizing dynamical system. When this press is set at high values, the self can resist inconsistent information and reestablish equilibrium after being perturbed by such information. A weak press for integration, on the other hand, impairs self-organization tendencies, making the system vulnerable to external information. Paradoxically, external information of a random nature may enhance the emergence of a stable self-structure in an initially disordered system. The simulation results suggest that important global properties of the self reflect the operation of integration processes that are generic in complex systems.


Nagai, Y. and Y. Aizawa (2000). "Rule-dynamical generalization of McCulloch-Pitts neuron networks." Biosystems 58(1-3): 177-85.

            A new aspect for neuronal networks is presented. The aspect is based on the concept of ruledynamics which was originally proposed by one of the authors, Aizawa. The concept of ruledynamics were modeled on the two states cellular automata of neighborhood-three (CA(2/3)). A brief review of ruledynamics is also presented, because most publications of the authors so far have been in Japanese. Our concise assertion in the present paper is that a neuronal network realizes a kind of ruledynamics. This assertion is a speculation on the comparison of McCulloch-Pitts neuron networks with ruledynamics on CA(2/3). A trial is originally shown to demonstrate that a McCulloch-Pitts neuron network can be imitated by an extended version of ruledynamics on CA(2/3).


Martins, M. L., G. Ceotto, et al. (2000). "Cellular automata model for citrus variegated chlorosis." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 62(5 Pt B): 7024-30.

            A cellular automata model is proposed to analyze the progress of citrus variegated chlorosis epidemics in Sao Paulo orange plantations. In this model epidemiological and environmental features, such as motility of sharpshooter vectors that perform Levy flights, level of plant hydric and nutritional stress, and seasonal climatic effects, are included. The observed epidemic data were quantitatively reproduced by the proposed model on varying the parameters controlling vector motility, plant stress, and initial population of diseased plants.


Lobry, C. and H. Elmoznino (2000). "Combinatorial properties of some cellular automata related to the mosaic cycle concept." Acta Biotheor 48(3-4): 219-42.

            A cellular automaton that is related to the "mosaic cycle concept" is considered. We explain why such automata sustain very often, but not always, n-periodic trajectories (n being the number of states of the automaton). Our work is a first step in the direction of a theory of these type of automata which might be useful in modeling mosaic successions.


Lewis, T. J. and J. Rinzel (2000). "Self-organized synchronous oscillations in a network of excitable cells coupled by gap junctions." Network 11(4): 299-320.

            Recent evidence suggests that electrical coupling plays a role in generating oscillatory behaviour in networks of neurons; however, the underlying mechanisms have not been identified. Using a cellular automata model proposed by Traub et al (Traub R D, Schmitz D, Jefferys J G and Draguhn A 1999 High-frequency population oscillations are predicted to occur in hippocampal pyramidal neural networks interconnected by axo-axonal gap junctions Neuroscience 92 407-26), we describe a novel mechanism for self-organized oscillations in networks that have strong, sparse random electrical coupling via gap junctions. The network activity is generated by random spontaneous activity that is moulded into regular population oscillations by the propagation of activity through the network. We explain how this activity gives rise to particular dependences of mean oscillation frequency on network connectivity parameters and on the rate of spontaneous activity, and we derive analytical expressions to approximate the mean frequency and variance of the oscillations. In doing so, we provide insight into possible mechanisms for frequency control and modulation in networks of neurons.


Kier, L. B., C. K. Cheng, et al. (2000). "Cellular automata models of chemical systems." SAR QSAR Environ Res 11(2): 79-102.

            This paper describes the use of kinematic, asynchronous, stochastic cellular automata to model liquid properties, solution phenomena and kinetic phenomena encountered in complex biological systems. Cellular automata models of dynamic phenomena represent in silico experiments designed to assess the effects of competing factors on the physical and chemical properties of solutions and other complex systems. Specific applications include solution behavior, separation of immiscible liquids, micelle formation, diffusion, membrane passage, first- and second-order chemical kinetics, enzyme activity and acid dissociation. Cellular automata is thus considered as providing an exploratory method for the analysis of dynamic phenomena and the discovery and understanding of new, unexpected phenomena.


Kier, L. B. and C. K. Cheng (2000). "A cellular automata model of an anticipatory system." J Mol Graph Model 18(1): 29-32, 61.

            An anticipatory system has been modeled using the dynamic characteristics of cellular automata. Rules governing the steps in an enzymatic conversion of substrates to products are operative in the system. A concentration of an intermediate product influences the creation of a supplemental enzyme that enhances the competence of an enzyme down stream. This anticipation of the future event creates a condition in which the concentration of a later substrate is suppressed, a property characteristic of the system. The model presents a useful opportunity to study a variety of aspects of this fascinating phenomena.


Kier, L. B. (2000). "A cellular automata model of bond interactions among molecules." J Chem Inf Comput Sci 40(5): 1285-8.

            The ten types of alkane bonds have been modeled as isolated fragments using cellular automata dynamics. The rules governing the states and the trajectories of the cells simulating the bonds are derived from the bimolecular interaction accessibilites recently described. The sum of cell encounters at unit iteration (time) becomes a parameter associated with the relationship of a molecule with its neighbors. This value is found to correlate very closely with the boiling points of alkanes, pentanes through octanes. The results reinforce the concept that the molecular connectivity indices are describing the interaction possibilities among alkanes. The study introduces a new way of simulating intermolecular bond encounter dynamics among many molecules.


Kier, L. B., C. K. Cheng, et al. (2000). "A cellular automata model of chromatography." Biomed Chromatogr 14(8): 530-4.

            Dynamic models of the behavior of solvent and solute molecules can be made using cellular automata. A chromatographic column was represented by use of a cellular automata grid of 43 x 200 spaces. Solvent (mobile phase), solute and stationary phase cells were designated to simulate the chromatographic situation. The movements of solute and solvent cells down the grid were monitored for different numbers of iterations, different flow rates and different affinities of the solutes for the stationary phase and the solvent for itself. The cellular automata dynamics were successfully able to model expected chromatographic behavior except in a few cases where the number of cells was not large enough to provide an average value reflective of the molecular situation.


Garcia-Olivares, A., M. Villarroel, et al. (2000). "Enzymes as molecular automata: a stochastic model of self-oscillatory glycolytic cycles in cellular metabolism." Biosystems 56(2-3): 121-9.

            A stochastic model based on the molecular automata approach was developed to simulate the cyclic dynamics of glycolysis-gluconeogenesis in cell energy metabolism. The stochastic algorithm, based on Gillespie's method, simulates the master equation associated with any network of enzymatically controlled reactions. This model of the glycolytic-gluconeogenetic cycle was developed by assembling the stochastic kinetic reactions controlled by two enzymes: phosphofructokinase (PFKase) and fructose-1, 6-biphosphatase (FBPase). In order to obtain the hysteresis behaviour predicted by classical Sel'kov analysis, a minimum complexity is required in the allosteric regulations. This implies that the FBPase cannot have a single binding site for its transition to the inactive state (a minimum of two or three binding sites is necessary). Given the multimeric structure of this enzyme, this kinetic hypothesis is tenable. Other possible applications of the stochastic automata approach for different cases of channels, receptors and enzymatic control are suggested.


Freudenberg, J., T. Schiemann, et al. (2000). "Simulation of cardiac excitation patterns in a three-dimensional anatomical heart atlas." Comput Biol Med 30(4): 191-205.

            Computerized anatomical atlas systems enable interactive investigation of digital body models. Here we present a three-dimensional atlas of the human heart, based on image data provided in the Visible Human Project. This heart atlas consists of multiple kinds of cardiac tissues and offers unlimited possibilities for its visual exploration. A temporal dimension is added to the underlying heart model by simulation of cardiac excitation spreading. For this purpose a second generation cellular automata algorithm is adapted to the excitation kinetics of cardiac tissue. The presented system is shown as a successful method for the visualization-based investigation of cardiac excitation.


Cowburn, R. P. and M. E. Welland (2000). "Room temperature magnetic quantum cellular automata." Science 287(5457): 1466-8.

            All computers process information electronically. A processing method based on magnetism is reported here, in which networks of interacting submicrometer magnetic dots are used to perform logic operations and propagate information at room temperature. The logic states are signaled by the magnetization direction of the single-domain magnetic dots; the dots couple to their nearest neighbors through magnetostatic interactions. Magnetic solitons carry information through the networks, and an applied oscillating magnetic field feeds energy into the system and serves as a clock. These networks offer a several thousandfold increase in integration density and a hundredfold reduction in power dissipation over current microelectronic technology.


Chowdhury, D., J. Kertesz, et al. (2000). "Comment on "Critical behavior of a traffic flow model"." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 61(3): 3270-1.

            We show that the dynamical structure factor investigated by Roters et al. [Phys. Rev. E 59, 2672 (1999)] does not allow the determination of the precise nature of the transition in the Nagel-Schreckenberg cellular automata model for traffic flow. We provide evidence for the existence of a crossover instead of a critical point.


Bernaschi, M., S. Succi, et al. (2000). "Large-scale cellular automata simulations of the immune system response." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 61(2): 1851-4.

            The sequential nature of the process allowing the immune system to learn how to withstand pathogen agents is explored by means of large-scale computer simulation of the Celada-Seiden immunological automaton. In accord with our previous results, it is found that the learning process proceeds via a sequential cascade in affinity space.


Tsimring, L. S., R. Ramaswamy, et al. (1999). "Dynamics of a shallow fluidized bed." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 60(6 Pt B): 7126-30.

            The results of the experimental study of the dynamics of a shallow fluidized bed are reported. The behavior of granular material is controlled by the interplay of two factors--levitation due to the upward airflow, and sliding back due to gravity. Near the threshold of instability, the system shows critical behavior with remarkably long transient dynamics. The experimental observations are compared with a simple cellular automata model.


Sotolongo-Costa, O., A. Vazquez, et al. (1999). "Bethe lattice representation for sandpiles." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 59(6): 6956-61.

            Avalanches in sandpiles are represented by a process of percolation in a Bethe lattice with a feedback mechanism. The results indicate that the frequency spectrum and probability distribution of avalanches provide a better resemblance to the experimental results than other models using cellular automata simulations. Apparent discrepancies between experiments performed by different authors are reconciled. Critical behavior is expressed here by the critical properties of percolation phenomena.


Sayama, H. (1999). "A new structurally dissolvable self-reproducing loop evolving in a simple cellular automata space." Artif Life 5(4): 343-65.

            We constructed a simple evolutionary system, "evoloop," on a deterministic nine-state five-neighbor cellular automata (CA) space by improving the structurally dissolvable self-reproducing loop we had previously contrived [14] after Langton's self-reproducing loop [7]. The principal role of this improvement is to enhance the adaptability (a degree of the variety of situations in which structures in the CA space can operate regularly) of the self-reproductive mechanism of loops. The experiment with evoloop met with the intriguing result that, though no mechanism was explicitly provided to promote evolution, the loops varied through direct interaction of their phenotypes, smaller individuals were naturally selected thanks to their quicker self-reproductive ability, and the whole population gradually evolved toward the smallest ones. This result gives a unique example of evolution of self-replicators where genotypical variation is caused by precedent phenotypical variation. Such interrelation of genotype and phenotype would be one of the important factors driving the evolutionary process of primitive life forms that might have actually occurred in ancient times.


Makowiec, D. (1999). "Stationary states of Toom cellular automata in simulations." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 60(4 Pt A): 3787-96.

            Stationary states of Toom probabilistic cellular automata are tested in computer experiments. The aim of the tests is to identify the features characterizing the equilibrium states understood as in statistical mechanics. Namely, we investigate the following: scaling laws that involve critical parameters beta, gamma, and nu, locality of the interactions, and density of the relative entropy between stationary states. The arguments showing that stationary Toom states are not the equilibrium ones are provided.


Lejeune, A., J. Perdang, et al. (1999). "Application of cellular automata to N-body systems." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 60(3): 2601-11.

            A two-dimensional cellular automaton model is introduced to deal with the dynamics of a finite system of particles whose interactions are simulated by two-body step potentials. The method is illustrated for a potential approximating the standard Lennard-Jones potential, representative for the problem of heavy ion collisions in nuclear physics. From the cellular automaton dynamics thermodynamic equilibrium state variables are introduced in the usual way. The numerical experiments indicate the occurrence of a phase transition. Macroscopically the transition is marked by a singularity in the equation of state; microscopically it manifests itself by the formation of clusters of particles of all sizes, obeying a mass distribution in the form of a power law of exponent 1.35.


Kwon, S., W. Hwang, et al. (1999). "Dynamic behavior of driven interfaces in models with two absorbing states." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 59(5 Pt A): 4949-52.

            We study the dynamics of an interface (active domain) between different absorbing regions in models with two absorbing states in one dimension: probabilistic cellular automata models and interacting monomer-dimer models. These models exhibit a continuous transition from an active phase into an absorbing phase, which belongs to the directed Ising (DI) universality class. In the active phase, the interface spreads ballistically into the absorbing regions and the interface width diverges linearly in time. Approaching the critical point, the spreading velocity of the interface vanishes algebraically with a DI critical exponent. Introducing a symmetry-breaking field h that prefers one absorbing state over the other drives the interface to move asymmetrically toward the unpreferred absorbing region. In Monte Carlo simulations, we find that the spreading velocity of this driven interface shows a discontinuous jump at criticality. We explain that this unusual behavior is due to a finite relaxation time in the absorbing phase. The crossover behavior from the symmetric case (DI class) to the asymmetric case (directed percolation class) is also studied. We find the scaling dimension of the symmetry-breaking field y(h)=1.21(5).


Jimenez-Morales, F. (1999). "Evolving three-dimensional cellular automata to perform a quasiperiod-3 collective behavior task." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 60(4 Pt B): 4934-40.

            We present results from experiments in which a genetic algorithm (GA) is used to develop three-dimensional cellular automata (CA) to perform a nontrivial collective behavior task. Under a fitness function that is defined as an averaged area in the iterative map, the GA detects a CA rule with quasiperiod-3 (QP3) collective behavior and another with period-3. For rules with QP3 the time autocorrelation function decays as a power law with an exponent of -1/2, according to the predictions of the Kardar-Parisi-Zhang equation, and a space-time diagram reveals the existence of propagating structures inside the system.


Hopcraft, K. I., E. Jakeman, et al. (1999). "Levy random walks with fluctuating step number and multiscale behavior." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 60(5 Pt A): 5327-43.

            Random walks with step number fluctuations are examined in n dimensions for when step lengths comprising the walk are governed by stable distributions, or by random variables having power-law tails. When the number of steps taken in the walk is large and uncorrelated, the conditions of the Levy-Gnedenko generalization of the central limit theorem obtain. When the number of steps is correlated, infinitely divisible limiting distributions result that can have Levy-like behavior in their tails but can exhibit a different power law at small scales. For the special case of individual steps in the walk being Gaussian distributed, the infinitely divisible class of K distributions result. The convergence to limiting distributions is investigated and shown to be ultraslow. Random walks formed from a finite number of steps modify the behavior and naturally produce an inner scale. The single class of distributions derived have as special cases, K distributions, stable distributions, distributions with power-law tails, and those characteristic of high and low frequency cascades. The results are compared with cellular automata simulations that are claimed to be paradigmatic of self-organized critical systems.


Goldschmidt, Y. Y., H. Hinrichsen, et al. (1999). "Nonequilibrium critical behavior in unidirectionally coupled stochastic processes." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 59(6): 6381-408.

            Phase transitions from an active into an absorbing, inactive state are generically described by the critical exponents of directed percolation (DP), with upper critical dimension d(c)=4. In the framework of single-species reaction-diffusion systems, this universality class is realized by the combined processes A-->A+A, A+A-->A, and A-->0. We study a hierarchy of such DP processes for particle species A,B,..., unidirectionally coupled via the reactions A-->B, ...(with rates mu(AB),...). When the DP critical points at all levels coincide, multicritical behavior emerges, with density exponents beta(i) which are markedly reduced at each hierarchy level i> or =2. This scenario can be understood on the basis of the mean-field rate equations, which yield beta(i)=1/2(i-1) at the multicritical point. Using field-theoretic renormalization-group techniques in d=4-epsilon dimensions, we identify a new crossover exponent phi, and compute phi=1+O(epsilon(2)) in the multicritical regime (for small mu(AB)) of the second hierarchy level. In the active phase, we calculate the fluctuation correction to the density exponent on the second hierarchy level, beta(2)=1/2-epsilon/8+O(epsilon(2)). Outside the multicritical region, we discuss the crossover to ordinary DP behavior, with the density exponent beta(1)=1-epsilon/6+O(epsilon(2)). Monte Carlo simulations are then employed to confirm the crossover scenario, and to determine the values for the new scaling exponents in dimensions d< or =3, including the critical initial slip exponent. Our theory is connected to specific classes of growth processes and to certain cellular automata, and the above ideas are also applied to unidirectionally coupled pair annihilation processes. We also discuss some technical as well as conceptual problems of the loop expansion, and suggest some possible interpretations of these difficulties.


Gerwinski, M. and J. Krug (1999). "Analytic approach to the critical density in cellular automata for traffic flow." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 60(1): 188-96.

            The jamming transition in the stochastic traffic cellular automaton of Nagel and Schreckenberg [J. Phys. I 2, 2221 (1992)] is examined. We argue that most features of the transition found in the deterministic limit do not persist in the presence of noise, and suggest instead to define the transition to take place at that critical density rho(c) at which a large initial jam just fails to dissolve. We show that rho(c)=v(J)/(v(J)+v(F)), where v(F) is the velocity of noninteracting vehicles and v(J) is the speed of the dissolution wave moving into the jam. An approximate analytic calculation of v(J) in the framework of a simple renormalization scheme is presented, which explicitly displays the effect of the interaction between vehicles during the acceleration stage of the Nagel-Schreckenberg rules with maximum velocity v(max)>1. The analytic prediction is compared to numerical simulations. We find a remarkable correspondence between the analytic expression for v(J) and a phase diagram obtained numerically by Lubeck et al.


Fuks, H. (1999). "Exact results for deterministic cellular automata traffic models." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 60(1): 197-202.

            We present a rigorous derivation of the flow at arbitrary time in a deterministic cellular automaton model of traffic flow. The derivation employs regularities in preimages of blocks of zeros, reducing the problem of preimage enumeration to a well-known lattice path counting problem. Assuming infinite lattice size and random initial configuration, the flow can be expressed in terms of generalized hypergeometric function. We show that the steady-state limit agrees with previously published results.


Courbage, M., D. Mercier, et al. (1999). "Traveling waves and chaotic properties in cellular automata." Chaos 9(4): 893-901.

            Traveling wave solutions of cellular automata (CA) with two states and nearest neighbors interaction on one-dimensional (1-D) infinite lattice are computed. Space and time periods and the number of distinct waves have been computed for all representative rules, and each velocity ranging from 2 to 22. This computation shows a difference between spatially extended systems, generating only temporal chaos and those producing as well spatial complexity. In the first case wavelengths are simply related to the velocity of propagation and the dispersivity is an affine function, while in the second case (which coincides with Wolfram class 3), the dispersivity is multiform and its dependence on the velocities is highly random and discontinuous. This property is typical of space-time chaos in CA. (c) 1999 American Institute of Physics.


Urias, J., G. Salazar, et al. (1998). "Synchronization of cellular automaton pairs." Chaos 8(4): 814-818.

            The phenomenon of synchronization in pairs of cellular automata coupled in a driver-replica mode is studied. Necessary and sufficient conditions for synchronization in linear cellular automaton pairs are given. The couplings that make a pair synchronize are determined for all linear elementary cellular automata. (c) 1998 American Institute of Physics.


Urias, J., E. Ugalde, et al. (1998). "A cryptosystem based on cellular automata." Chaos 8(4): 819-822.

            Cryptosystems for binary information are based on two primitives: an indexed family of permutations of binary words and a generator of pseudorandom sequences of indices. A very efficient implementation of the primitives is constructed using the phenomenon of synchronization in cellular automata. (c) 1998 American Institute of Physics.


Salazar, G. and J. Urias (1998). "Internal symmetries of cellular automata via their polynomial representation." Chaos 8(3): 711-716.

            A polynomial representation of elementary cellular automata (ECA) is used to give a complete characterization of the local internal symmetries of all ECA. It is also shown that the polynomial representation is a natural choice for the study of local internal transformations of all cellular automata with two symbols. This is achieved by proving that local internal transformations are simply expressed in this representation as sums of polynomials. (c) 1998 American Institute of Physics.


Urias, J. and A. Enciso (1997). "Internal symmetries of cellular automata." Chaos 7(3): 447-454.

            (Internal) transformations on the space Sigma of automaton configurations are defined as bi-infinite sequences of permutations of the cell symbols. A pair of transformations (gamma,theta) is said to be an internal symmetry of a cellular automaton f:Sigma-->Sigma if f=theta(-1)fgamma. It is shown that the full group of internal symmetries of an automaton f can be encoded as a group homomorphism F such that theta=F(gamma). The domain and image of the homomorphism F have, in general, infinite order and F is presented by a local automaton-like rule. Algorithms to compute the symmetry homomorphism F and to classify automata by their symmetries are presented. Examples on the types of dynamical implications of internal symmetries are discussed in detail. (c) 1997 American Institute of Physics.


Urias, J., R. Rechtman, et al. (1997). "Sensitive dependence on initial conditions for cellular automata." Chaos 7(4): 688-693.

            The property of sensitive dependence on intial conditions is the basis of a rigorous mathematical construction of local maximum Lyapunov exponents for cellular automata. The maximum Lyapunov exponent is given by the fastest average velocity of either the left or right propagating damage fronts. Deviations from the long term behavior of the finite time Lyapunov exponents due to generation of information are quantified and could be used for the characterization of the space time complexity of cellular automata. (c) 1997 American Institute of Physics.


Conrad, M. and J. C. Chen (1997). "Pattern Categorization and Generalization with a Virtual Neuromolecular Architecture." Neural Netw 10(1): 111-123.

            A multilevel neuromolecular computing architecture has been developed that provides a rich platform for evolutionary learning. The architecture comprises a network of neuron-like modules with internal dynamics modeled by cellular automata. The dynamics are motivated by the hypothesis that molecular processes operative in real neurons (in particular processes connected with second messenger signals and cytoskeleton-membrane interactions) subserve a signal integrating function. The objective is to create a repertoire of special purpose dynamic pattern processors through an evolutionary search algorithm and then to use memory manipulation algorithms to select combinations of processors from the repertoire that are capable of performing coherent pattern recognition/neurocontrol tasks. The system consists of two layers of cytoskeletally controlled (enzymatic) neurons and two layers of memory access neurons (called reference neurons) divided into a collection of functionally comparable subnets. Evolutionary learning can occur at the intraneuronal level through variations in the cytoskeletal structures responsible for the integration of signals in space and time, through variations in the location of elements that represent readin or readout proteins, and through variations in the connectivity of the neurons. The memory manipulation algorithms that orchestrate the repertoire of neuronal processors also use evolutionary search procedures. The network is capable of performing complicated pattern categorization tasks and of doing so in a manner that balances specificity and generalization. Copyright 1996 Elsevier Science Ltd.


Chernyak, Y. B., A. B. Feldman, et al. (1997). "Correspondence between discrete and continuous models of excitable media: trigger waves." Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics 55(3 Pt B): 3215-33.

            We present a theoretical framework for relating continuous partial differential equation (PDE) models of excitable media to discrete cellular automata (CA) models on a randomized lattice. These relations establish a quantitative link between the CA model and the specific physical system under study. We derive expressions for the CA model's plane wave speed, critical curvature, and effective diffusion constant in terms of the model's internal parameters (the interaction radius, excitation threshold, and time step). We then equate these expressions to the corresponding quantities obtained from solution of the PDEs (for a fixed excitability). This yields a set of coupled equations with a unique solution for the required CA parameter values. Here we restrict our analysis to "trigger" wave solutions obtained in the limiting case of a two-dimensional excitable medium with no recovery processes. We tested the correspondence between our CA model and two PDE models (the FitzHugh-Nagumo medium and a medium with a "sawtooth" nonlinear reaction source) and found good agreement with the numerical solutions of the PDEs. Our results suggest that the behavior of trigger waves is actually controlled by a small number of parameters.


Urias, J., G. Salazar-Anaya, et al. (1996). "Traveling patterns in cellular automata." Chaos 6(3): 493-503.

            A method to identify the invariant subsets of bi-infinite configurations of cellular automata that propagate rigidly with a constant velocity nu is described. Causal traveling configurations, propagating at speeds not greater than the automaton range, mid R:numid R:</=r, are considered. The sets of traveling configurations are presented by finite automata and its topological entropy is calculated. When the invariant subset of traveling configurations has nonzero topological entropy, the dynamics is dominated by the interaction of domains, composed of traveling patterns of finite size. The sets of traveling patterns and domains are presented by finite automata. End-resolving CA are shown to always have sets of traveling configurations that are spatially periodic with zero entropy, except possibly for traveling configurations at top speed. The elementary CA are examined exhaustively along these lines. (c) 1996 American Institute of Physics.


Turcotte, D. L. (1995). "Scaling in geology: landforms and earthquakes." Proc Natl Acad Sci U S A 92(15): 6697-704.

            Landforms and earthquakes appear to be extremely complex; yet, there is order in the complexity. Both satisfy fractal statistics in a variety of ways. A basic question is whether the fractal behavior is due to scale invariance or is the signature of a broadly applicable class of physical processes. Both landscape evolution and regional seismicity appear to be examples of self-organized critical phenomena. A variety of statistical models have been proposed to model landforms, including diffusion-limited aggregation, self-avoiding percolation, and cellular automata. Many authors have studied the behavior of multiple slider-block models, both in terms of the rupture of a fault to generate an earthquake and in terms of the interactions between faults associated with regional seismicity. The slider-block models exhibit a remarkably rich spectrum of behavior; two slider blocks can exhibit low-order chaotic behavior. Large numbers of slider blocks clearly exhibit self-organized critical behavior.


Cronhjort, M. B. (1995). "Hypercycles versus parasites in the origin of life: model dependence in spatial hypercycle systems." Orig Life Evol Biosph 25(1-3): 227-33.

            Spatial hypercycle systems can be modelled by means of cellular automata or partial differential equations. In either model, two dimensional spirals or clusters can be formed. Different models give rise to slightly different spatial structures, but the response to parasites is fundamentally different: In cellular automata the hypercycle is resistant to parasites that are fatal in a partial differential equations model. In three dimensions scroll rings correspond to the two dimensional spirals. Numerical simulations on a partial differential equations model indicate that the scroll rings are unstable: The contract by a power law and disappear. Therefore, in three dimensions clusters seem to be the best candidate for the hypercycle resistant to parasites.


Back to Top