Modelling forest fire spread using hexagonal cellular automata

In this paper a new mathematical model for predicting the spread of a fire front in homogeneous and inhomogeneous environments is presented. It is based on a bidimensional cellular automata model, whose cells stand for regular hexagonal areas of the forest. The results obtained are in agreement with the fire spreading in real forests.     

Modelling nonlinear sequence generators in terms of linear cellular automata

In this work, a wide family of LFSR-based sequence generators, the so-called clock-controlled shrinking generators (CCSGs), has been analyzed and identified with a subset of linear cellular automata (CA). In fact, a pair of linear models describing the behavior of the CCSGs can be derived. The algorithm that converts a given CCSG into a CA-based linear model is very simple and can be applied to CCSGs in a range of practical interest. The linearity of these cellular models can be advantageously used in two different ways: (a) for the analysis and/or cryptanalysis of the CCSGs and (b) for the reconstruction of the output sequence obtained from this kind of generators.     

The development of a cellular automaton-finite volume model for dendritic growth

A cellular automaton to track the solid–liquid interface movement is linked to finite volume computations of solute diffusion to simulate the behavior of dendritic structures in binary alloys during solidification. A significant problem encountered in the CA formulation has been the presence of artificial anisotropy in growth kinetics introduced by a Cartesian CA grid. A new technique to track the interface movement is proposed to model dendritic growth in different crystallographic orientations while reducing the anisotropy due to grid orientation. The model stability with respect to the numerical parameters (cell size and time step) for various operating conditions is examined. A method for generating an operating window in Δt and Δx has been identified, in which the model gives a grid-independent set of results for calculated dendrite tip radius and tip undercooling. Finally, the model is compared to published experimental and analytical results for both directional and equiaxed growth conditions.     

A single-copy minimal-time simulation of a torus of automata by a ring of automata

We consider cellular automata on Cayley graphs and we simulate the behavior of a torus of n×m automata (nodes) by a ring of n·m automata (cells). Our simulation technique requires the neighborhood of the nodes to be preserved. We achieve this constraint by copying the contents of nodes on the cells. We consider the problem of minimizing the number of the copies. We prove that it is possible to simulate the behavior of a torus on a ring with a single copy on each cell if and only if n and m satisfy a given condition. In that case we propose a time-optimal algorithm. We thus improve a previous work done by Martin where two copies were requested. When the condition on n and m is not fulfilled one can use the previous algorithm.     

On irreversibility of von Neumann additive cellular automata on grids

The von Neumann cellular automaton appears in many different settings in Operations Research varying from applications in Formal Languages to Biology. One of the major questions related to it is to find a general condition for irreversibility of a class of two-dimensional cellular automata on square grids (σ⁺-automata). This question is partially answered here with the proposal of a sufficient condition for the irreversibility of σ⁺-automata.     

CELLULAR AUTOMATA FOR THE NETWORK RESEARCHER

Cellular automata (CA) can be used in simulations of network processes and network evolution by identifying adjacent vertices in a network with neighboring cells in a CA. However, there are restrictions on networks that can be represented by two dimensional CAs. For example, the degree of a vertex, the maximum number of unconnected neighbors, and the maximum size of a clique, are limited. Moreover, a high degree of transitivity is built into the two dimensional CA. Increasing the number of dimensions beyond two relaxes all the constraints. Moreover, the reduced transitivity of higher dimensional CAs allows us to vary in a systematic way the “localness” of the connections. Thus, we can examine the differences between strong (local and transitive) versus weak (non-transitive) ties, a difference that Granovetter and others have shown to be important. The paper offers equations describing how maximum degree, maximum clique size, maximum number of unconnected neighbors, and transitivity vary with the dimensions of the CA.     

Tensional computation: further musings on the computational cosmography

Universe operates in pure principle only, wherefrom we can choose to view Universe as an emergent computation. The proposed method for this most basic of computations is the computational cosmography, wherein a system of interacting deformable polyhedra utilizing the geometric primitives of Fuller's synergetic geometry coordinate and evolve within an isotropic vector matrix. A gedanken experiment involving gravity on a two-dimensional lattice is also discussed, as are some consequences associated with this computational cosmographical viewpoint.     

Density of periodic points, invariant measures and almost equicontinuous points of cellular automata

Revisiting the notion of μ-almost equicontinuous cellular automata introduced by R. Gilman, we show that the sequence of image measures of a shift ergodic measure μ by iterations of such automata converges in Cesàro mean to an invariant measure μ_c. Moreover the dynamical system (cellular automaton F, invariant measure μ_c) has still the μ_c-almost equicontinuity property and the set of periodic points is dense in the topological support of the measure μ_c. We also show that the density of periodic points in the topological support of a measure μ occurs for each μ-almost equicontinuous cellular automaton when μ is an invariant and shift ergodic measure. Finally using most of these results we give a non-trivial example of a couple (μ-equicontinuous cellular automaton F, shift and F-invariant measure μ) such that the restriction of F to the topological support of μ has no equicontinuous points.     

Dynamic range in a neuron network with electrical and chemical synapses

The dynamic range is the logarithmic difference between maximum and minimum levels of sensation produced by known stimuli. In the human sensory systems the dynamic ranges are typically larger than for single neurons, this amplification being essentially a collective effect of the neural network. We investigated the dynamic range exhibited by a cellular automaton network with electrical and chemical synapses, when the stimuli are modelled by a Poisson process of suprathreshold events of stereotyped unit amplitude and the neuron response is its average firing rate.     

Some rigorous results for the Greenberg-Hastings Model

In this paper, we obtain some rigorous results for a cellular automaton known as the Greenberg-Hastings Model. The state space is {0, 1, 2}^{Z d} . The dynamics are deterministic and discrete time. A site which is 1 changes to 2, a site which is 2 changes to 0, and a site which is 0 changes to a 1 if one of its 2d neighbors is a 1. In one dimension, we compute the exact asymptotic rate at which the system dies out when started at random and compute the topological entropy. In two or more dimensions we show that starting from a nontrivial product measure, the limit exists as 3m and is Bernoulli shift. Finally, we investigate the behavior of the system on a large finite box.     

Lattice games without rational strategies

We show that the lattice games of Guo and Miller support universal computation, disproving their conjecture that all lattice games have rational strategies. We also state an explicit counterexample to that conjecture: a three dimensional lattice game whose set of winning positions does not have a rational generating function.     

A cellular automaton model for collective neural dynamics

A stochastic epidemic model for the collective behaviour of a large set of Boolean automata placed upon the sites of a complete graph is revisited. In this paper we study the generalisation of the model to take into account inhibitory neurons. The resulting stochastic cellular automata are completely defined by five parameters: the number of excitatory neurons, N, the number of inhibitory neurons, M, the probabilities of excitation, α, and inhibition, γ, among neurons and the spontaneous transition rate from the firing to the quiescent state, β.We propose that the background of the electroencephalographic signals could be mimicked by the fluctuations in the total number of firing neurons in the excitatory subnetwork. These fluctuations are Gaussian and the mean-square displacement from an initial state displays a strongly subdiffusive behaviour approximately given by , where NA=β/(β+Mγ), τ=2(Nα−β). Comparison with real EEG records exhibits good agreement with these predictions.     

Synthesis of cryptographic interleaved sequences by means of linear cellular automata

This work shows that a class of pseudorandom binary sequences, the so-called interleaved sequences, can be generated by means of linear multiplicative polynomial cellular automata. In fact, these linear automata generate all the solutions of a type of linear difference equations with binary coefficients. Interleaved sequences are just particular solutions of such equations. In this way, popular nonlinear sequence generators with cryptographic application can be linearized in terms of simple cellular automata.     

A CA-based epidemic model for HIV/AIDS transmission with heterogeneity

The complex dynamics of HIV transmission and subsequent progression to AIDS make the mathematical analysis untraceable and problematic. In this paper, we develop an extended CA simulation model to study the dynamical behaviors of HIV/AIDS transmission. The model incorporates heterogeneity into agents’ behaviors. Agents have various attributes such as infectivity and susceptibility, varying degrees of influence on their neighbors and different mobilities. Additional, we divide the post-infection process of AIDS disease into several sub-stages in order to facilitate the study of the dynamics in different development stages of epidemics. These features make the dynamics more complicated. We find that the epidemic in our model can generally end up in one of the two states: extinction and persistence, which is consistent with other researchers’ work. Higher population density, higher mobility, higher number of infection source, and greater neighborhood are more likely to result in high levels of infections and in persistence. Finally, we show in four-class agent scenario, variation in susceptibility (or infectivity) and various fractions of four classes also complicates the dynamics, and some of the results are contradictory and needed for further research.     

Computational methods for Conway's Game of Life cellular automaton

The cellular automaton model of computation has drawn the interest of researchers from different disciplines including computer science, biology, mathematics, economy, biochemistry and philosophy. Although a cellular automaton is based on a set of simple rules, over time complex patterns may evolve. We present computational methods for implementing and optimizing a well known two-state cellular automaton, Conway's Game of Life, on a 16-core Intel Xeon. The evaluation is based on three multicore algorithms. The first algorithm is coherent and utilizes shared memory and barrier synchronization. The remaining two algorithms are distributed and utilize private memories and explicit core-to-core message passing. We provide a link to our open source simulation software.     

Modeling framework for optimal evacuation of large-scale crowded pedestrian facilities

The paper presents a simulation–optimization modeling framework for the evacuation of large-scale pedestrian facilities with multiple exit gates. The framework integrates a genetic algorithm (GA) and a microscopic pedestrian simulation–assignment model. The GA searches for the optimal evacuation plan, while the simulation model guides the search through evaluating the quality of the generated evacuation plans. Evacuees are assumed to receive evacuation instructions in terms of the optimal exit gates and evacuation start times. The framework is applied to develop an optimal evacuation plan for a hypothetical crowded exhibition hall. The obtained results show that the model converges to a superior optimal evacuation plan within an acceptable number of iterations. In addition, the obtained evacuation plan outperforms conventional plans that implement nearest-gate immediate evacuation strategies.