Critical properties of Rule 22 elementary cellular automata

The one-dimensional elementary cellular automaton Rule 22 is studied by means of Monte Carlo simulation on the dedicated K2 high-speed computer. If one considers random initialization with probability p for one-initialization per site, it is shown that the system behaves like a normal one-dimensional statistical ensemble with critical points atp=0 andp=1. Critical slowing down is exhibited, with a dynamical exponent of 1.0. The standard initialization ofp=0.5 is too far away from the critical point to allow similar observations.     

Determination of fixed points and shift cycles for nearest neighbor cellular automata

One-dimensional nearest neighbor cellular automata defined over Z₂ are characterized in terms of a set of eight nonadditive basis operators which act on the automaton state space. Every evolution rule for such automata can be expressed as an operator which is a direct sum of the basis operators. This approach allows decomposition of automata rules into additive and nonadditive parts. As a result, it is simple to determine fixed points (those states for which the rule reduces to the identity), and shift cycles (sets of states on which the rule reduces to a shift). Sets of states on which any given nearest neighbor automaton reduces to an identity or a shift are characterized. This allows us to obtain some results on the entropic properties of nonadditive automata, although these are not nearly so complete as results obtained for additive automata.     

An evacuation model using cellular automata

In order to simulate evacuation from a room with multiple exits, a two-dimensional basic cellular automata (CA) model is proposed based on human behavior. In this model, two factors are taken into account, viz. spatial distance and occupant density. To make the simulation more reasonable, human behavior including inertial effect, group effect and unadventurous effect are considered in an extended model. Numerical results show that the proposed CA model is realistic and robust. A parametric study reveals the potential application of CA model in the assessment of fire safety.     

Quantum walks and reversible cellular automata

We obtain a conserved quantity for a reversible cellular automaton derived from a discrete-time quantum walk in one dimension. As a corollary, we give detailed information regarding the evolution of the quantum walk.     

A dilute bootstrap percolation: Lattice model for unresponsiveness in T-cell immunology

The biased majority rule of cellular automata takes a spin up if and only if at least two of its four nearest neighbors on the square lattice are up. We generalize this type of bootstrap percolation by introducing quenched site dilution as well as a random birth and decay process. Our Monte Carlo simulations then give first-order transitions qualitatively similar to our results from meanfield reaction equations describing the induction of T-cell unresponsiveness in the immune system.     

Emergence of self-replicating structures in a cellular automata space

Past cellular automata models of self-replication have always been initialized with an original copy of the structure that will replicate, and have been based on a transition function that only works for a single, specific structure. This article demonstrates for the first time that it is possible to create cellular automata models in which a self-replicating structure emerges from an initial state having a random density and distribution of individual components. These emergent self-replicating structures employ a fairly general rule set that can support the replication of structures of different sizes and their growth from smaller to larger ones. This rule set also allows “random” interactions of self-replicating structures with each other and with other structures within the cellular automata space. Systematic simulations show that emergence and growth of replicants occurs often and is essentially independent of the cellular space size, initial random pattern of components, and initial density of components, over a broad range of these parameters. The number of replicants and the total number of components they incorporate generally approach quasi-stable values with time.     

Probabilistic bootstrap percolation

In bootstrap percolation, sites are occupied with probabilityp, but those with less thanm occupied first neighbors are removed. This culling process is repeated until a stable configuration (all occupied sites have at leastm occupied first neighbors or the whole lattice is empty) is achieved. Formm ₁ the transition is first order, while form<m ₁ it is second order, withm-dependent exponents. In probabilistic bootstrap percolation, sites have probabilityr or (1–r) of beingm- orm-sites, respectively (m-sites are those which need at leastm occupied first neighbors to remain occupied). We have studied the model on Bethe lattices, where an exact solution is available. Form=2 andm=3, the transition changes from second to first order atr ₁=1/2, and the exponent is different forr<1/2,r=1/2, andr>1/2. The same qualitative behavior is found form=1 andm=3. On the other hand, form=1 andm=2 the transition is always second order, with the same exponents ofm=1, for any value ofr>0. We found, form=z–1 andm=z, wherez is the coordination number of the lattice, thatp _c=1 for a value ofr which depends onz, but is always above zero. Finally, we argue that, for bootstrap percolation on real lattices, the exponents and form=2 andm=1 are equal, for dimensions below 6.On leave from Universidade Federal de Santa Catarina, Depto. de Fisica, 88049, Florianópolis, SC, Brazil     

Exact results for deterministic cellular automata with additive rules

Deterministic cellular automata (CA) with additive rules are studied by exploiting the properties of circulant matrices on finite fields. Complete state transition diagrams for higher-order and multidimensional CA on finite lattices are analyzed. Conditions on the rules which make them reversible are obtained. It is shown that all state transition diagrams of the CA have identical trees rooted on cycles. General formulae for cycle lengths and multiplicities are given.     

A stochastic cellular automata model of tautomer equilibria

ABSTRACT

Many chemical substances, including drugs and biomolecules, exist in solution not as a single species, but as a collection of tautomers and related species. Importantly, each of these species is an independent compoundwith its own specific biochemical and physicochemical properties. The species interconvert in a dynamic and often complicated manner, making modelling the overall species composition difficult. Agent-based cellular automata models are uniquely suited to meet this challenge, allowing the equilibria to be simulated using simple rulesand at the same time capturing the inherent stochasticity of the natural phenomenon. In the present example a stochastic cellular automata model is employed to simulate the tautomer equilibria of 9-anthrone and 9-anthrol in the presence of their common anion. The observed K_E of the 9-anthrone ? 9-anthrol tautomerisation along with the measured tautomer pK_a values were used to model the equilibria at pH values 4, 7 and 10. At pH 4 and 7, the anthrone comprises >99% of the total species population, while at pH 10the anthrone and the anion each represent just under half of the total population. The advantages of the cellular automata approach over the customary coupled differential equation approach are discussed.     

Kink movements and percolation in the binary additive cellular automaton

We show that under the Bernoulli initial condition two kinks in the cellular automaton (CA) 18/256 will annihilate each other with probability one. It turns out that there is an equivalent statement in terms of percolation in the simple binary additive CA. Namely, under the Bernoulli initial condition, l's do not percolate in the binary additive CA.     

Fractal dimension at the phase transition of inhomogeneous cellular automata

For random binary mixtures of cellular automata in the square lattice, calculations are made of the fractal dimensions associated with the damage spreading and the propagation time of damage at the transition to chaos. Two rules are mixed and universalities of these quantities are sought with respect to change of the rules.     

Transient and cyclic behavior of cellular automata with null boundary conditions

One-dimensional cellular automata (CA) over finite fields are studied in which each interior cell is updated to contain the sum of the previous values of its two nearest neighbors. Boundary cells are updated according to null boundary conditions. For a given initial configuration, the CA evolves through transient configurations to an attracting cycle. The dependence of the maximal transient length and maximal cycle length on the number of cells is investigated. Both can be determined from the minimal polynomial of the update matrix, which in this case satisfies a useful recurrence relation. With cell values from a field of characteristic two, the explicit dependence of the maximal transient length on the number of cells is determined. Extensions and directions for future work are presented.Deceased.     

Annealed and quenched inhomogeneous cellular automata (INCA)

A probabilistic one-dimensional cellular automaton model by Domany and Kinzel is mapped into an inhomogeneous cellular automaton with the Boolean functions XOR and AND as transition rules. Wolfram's classification is recovered by varying the frequency of these two simple rules and by quenching or annealing the inhomogeneity. In particular, class 4 is related to critical behavior in directed percolation. Also, the critical slowing down of second-order phase transitions is related to a stochastic version of the classical halting problem of computation theory.     

Metastability with probabilistic cellular automata in an HIV infection

Assuming a small failure probability for the interleukin production, a discrete model of HIV infection leads to transitions between fixed points. Eventually all initial configurations for the cellular automata lead to the destruction of the immune system, i.e., to AIDS.     

Algorithms for computing preimages of cellular automata configurations

This paper investigates pre-images (ancestors or past configurations) of specified configurations of one-dimensional cellular automata. Both counting and listing of pre-images are discussed. The main graphical tools used are the de Bruijn diagram, and its extension the pre-image network, which is created by concatenating de Bruijn diagrams. The counting of pre-images is performed as the multiplication of topological matrices of de Bruijn diagrams. Listing of pre-images is described using two algorithms. The first algorithm traces paths in the pre-image network and focuses on local knowledge of the network. The second performs a complete analysis of the network before proceeding with listing.     

Cluster growth in particle-conserving cellular automata

A class of simple two-dimensional cellular automata with particle conservation is proposed for easy simulations of interacting particle systems. The automata are defined by the exchange of states of neighboring cells, depending on the configurations around the cells. By attributing an energy to a configuration of cells, we can select significant rules from the huge number of possible rules and classify them into several groups, based on the analogy with a binary alloy. By numerical calculations, cluster growth is found in two kinds of phases which reveal gas-solid coexistence and liquid droplets. Normalized scaling functions are obtained, and dynamical scaling is examined.     

A note on inherent replication properties of local cellular automata transition functions

Local transition functions of elementary cellular automata show different tendencies to replicate parts of a configuration in a later generation. This is seen as regularities in the time-space diagram. This replication depends on both the configuration and the local transition function. A possibility to isolate the influence of the local transition function is shown.     

Invariant strings and pattern-recognizing properties of one-dimensional cellular automata

A cellular automaton is a discrete dynamical system whose evolution is governed by a deterministic rule involving local interactions. It is shown that given an arbitrary string of values and an arbitrary neighborhood size (representing the range of interaction), a simple procedure can be used to find the rules of that neighborhood size under which the string is invariant. The set of nearestneighbor rules for which invariant strings exist is completely specified, as is the set of strings invariant under each such rule. For any automaton rule, an associated filtering rule is defined for which the only attractors are spatial sequences consisting of concatenations of invariant strings. A result is provided defining the rule of minimum neighborhood size for which an arbitrarily chosen string is the unique invariant string. The applications of filtering rules to pattern recognition problems are discussed.