Spreadable cellular automata: modelling and simulations

The spreadable phenomena which describes the expansion in time of a given spatial property has been studied using models based on partial differential equations. These spreadable dynamics are generally non-linear and then difficult to simulate particularly in two dimensions. In this article, we propose cellular automata (CA) models as an alternative modelling tool that can easily simulate spreadable systems. CA are capable of describing complex systems based on simple evolution rules, which provide numerical schemes directly implemented on computers without approximation or rounding errors. We design local CA dynamics which allow us to maintain a spatial property on non-decreasing subdomains. Several numerical results are performed to illustrate spreadable phenomena. The simulation results corroborate the general shape theory that exhibits the convergence to a specific domain independently on initial conditions.     

Simulating multilane traffic flows based on cellular automata theory

A two-dimensional microscopic model of multilane traffic flows is proposed. Test calculations proved it to be adequate. The model was used to numerically analyze the traffic capacity of a crossing for different traffic lights modes, as well as to compare traffic capacities of roads depending on entries-exits and their number.     

Text compression using two-dimensional cellular automata

This paper presents an elegant mathematical model using simple matrix algebra for characterising the behaviour of two-dimensional nearest neighbourhood linear cellular automata with periodic boundary conditions. Based on this mathematical model, the VLSI architecture of a Cellular Automata Machine (CAM) has been proposed for text compression. Experimental results of comparisons with adaptive Huffman coding scheme also presented.     

Frequent itemset mining using cellular learning automata

A core issue of the association rule extracting process in the data mining field is to find the frequent patterns in the database of operational transactions. If these patterns discovered, the decision making process and determining strategies in organizations will be accomplished with greater precision. Frequent pattern is a pattern seen in a significant number of transactions. Due to the properties of these data models which are unlimited and high-speed production, these data could not be stored in memory and for this reason it is necessary to develop techniques that enable them to be processed online and find repetitive patterns. Several mining methods have been proposed in the literature which attempt to efficiently extract a complete or a closed set of different types of frequent patterns from a dataset. In this paper, a method underpinned upon Cellular Learning Automata (CLA) is presented for mining frequent itemsets. The proposed method is compared with Apriori, FP-Growth and BitTable methods and it is ultimately concluded that the frequent itemset mining could be achieved in less running time. The experiments are conducted on several experimental data sets with different amounts of minsup for all the algorithms as well as the presented method individually. Eventually the results prod to the effectiveness of the proposed method.     

Image processing using 3-state cellular automata

This paper describes the application of cellular automata (CA) to various image processing tasks such as denoising and feature detection. Whereas our previous work mainly dealt with binary images, the current work operates on intensity images. The increased number of cell states (i.e. pixel intensities) leads to a vast increase in the number of possible rules. Therefore, a reduced intensity representation is used, leading to a three state CA that is more practical. In addition, a modified sequential floating forward search mechanism is developed in order to speed up the selection of good rule sets in the CA training stage. Results are compared with our previous method based on threshold decomposition, and are found to be generally superior. The results demonstrate that the CA is capable of being trained to perform many different tasks, and that the quality of these results is in many cases comparable or better than established specialised algorithms.     

Design of materials using hybrid cellular automata

This paper presents a new approach for the topological design of materials with extreme properties. The method is based on hybrid cellular automaton (HCA), which is an implicit optimization technique that uses local rules to update design variables iteratively until meeting the described optimality conditions. By means of an energy-based homogenization approach, the effective properties of the considered material are calculated in terms of element mutual energies. By this method, no sensitivity information is required to find the optimal topology for the considered design objectives: bulk modulus, shear modulus, and negative Poisson’s ratio. The proposed method is validated by a series of numerical examples.     

Shoreline evolution: GIS,remote sensing and cellular automata modelling

The evolution and more particularly the erosion of the coasts morphology is an important environmental subject. Both the study of the actual evolution of coasts via digital tools and their modelling for the sake of prediction are necessary. A study of the evolution of a section of the Algerian coastline with a geographical information system shows that erosion is the main factor for the shoreline evolution, in the absence of structures consolidating the beaches. Therefore, a qualitative numerical model of the erosion of a coastline is proposed. It relies on a coupling between a cellular automata sedimentation model and a bi-fluid hydrodynamical model based on the Lattice Boltzmann method. The current model is two-dimensional and simulates a cross-section of a virtual coastline. The virtual coastline exhibits a gradual erosion by the water, whose speed depends on the kind of perturbation applied on the water level.     

Sand automata as cellular automata

In this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. This relation induces a compact topology for sand automata, and a new context in which sand automata are homeomorphic to cellular automata acting on a specific subshift. We show that the existing topological results for sand automata, including the Hedlund-like representation theorem, still hold. In this context, we give a characterization of cellular automata which are sand automata, and study some dynamical behaviors such as equicontinuity. Furthermore, we deal with simple sand automata. We show that the classical definition of nilpotency is not meaningful for sand automata. Then, we introduce the suitable new notion of flattening sand automata. Finally, we prove that this simple dynamical behavior is undecidable.     

Adaptive behaviorin cellular automata using rough set theory

The paper uses ideas from machine learning and artificial intelligence to provide the model of cellular automata based on rough set theory and the response to it in simulated cars. Recently, the examination and modeling of vehicular traffic has become an important subject of research. We propose in this paper, a road-traffic system based on two-dimensional cellular automata combined with rough set theory, to model the flow and jamming that is common in an urban environment. The modeled development process in this paper involves simulated processes of evolution, learning, and self-organization. The main value of the model is that it provides an illustration of how simple learning processes may lead to the formation of the state machine behavior, which can give emergence to the model.     

Elliptic curve based hardware architecture using cellular automata

This study presents an efficient division architecture using restricted irreducible polynomial on elliptic curve cryptosystem (ECC), based on cellular automata. The most expensive arithmetic operation in ECC is division, which is performed by multiplying the inverse of a multiplicand. The proposed architecture is highly regular, expandable, and has reduced latency and hardware complexity. The proposed architecture can be efficiently used in the hardware design of crypto-coprocessors.     

Simulation of forest fire fronts using cellular automata

In this work a new model for fire front spreading based on two-dimensional cellular automata is proposed. It is a more realistic modification of the model introduced by Karafyllidis and Thanailakis (see [Karafyllidis I, Thanailakis A. A model for predicting forest fire spreading using cellular automata. Ecol Model 1997;99:87–97]), which is based on the transfer of fractional burned area. Specifically, the model proposed in this work introduces a more accurate factor of propagation from a diagonal neighbor cell and includes, in a detailed form, the rate of fire spread. Moreover, the model is useful for both homogeneous and inhomogeneous environments. Some tests have been passed in order to determine the goodness of the method.     

Retina simulation using cellular automata and GPU programming

This article shows how the architectural modelization of biological retina allows real-time performances, on standard widespread computing systems. First, we describe the biological retina with regard to its pipeline architecture, detailing its layer behaviours and properties. Then we propose a corresponding pipelined model of artificial retina based on cellular automata. In this work, the main innovation is the computing method based on the programming of a personal computer graphical card using OpenGL shading language. The last section demonstrates the efficiency of our model through numerical and graphical results. We lay particular emphasis on the fact that our direct implementation of the Graphical Processor Unit (GPU) provides computation power about 20 times as fast as conventional programming.     

Image security system using recursive cellular automata substitution

This paper presents a novel image security system based on the replacement of the pixel values using recursive cellular automata (CA) substitution. This proposed image encryption method exhibits the properties of confusion and diffusion because of the characteristics of CA substitution are flexible. The salient features of the proposed image encryption method are its losslessness, symmetric private key encryption, very large number of secret keys, and key-dependent pixel value replacement. Simulation results obtained using some color and gray-level images clearly demonstrate the strong performance of the proposed image security system.     

Assessing complexity in cellular automata using information theory

ABSTRACT

We discuss two ways in which information theory can be used to assess complexity in a system of interacting agents. In the first part, we adopt a global viewpoint and propose a characterization of complexity based on successive maximum entropy estimations of the probability density describing the system, thereby quantifying the respective role played by low and high orders of interaction. In the second part we reconsider the question from a local perspective, focussing on the statistical dependencies between neighbouring agents. These tools are tried on simple cellular automata in order to put them in perspective with other notions of complexity usually employed for such systems. We show that these approaches are hardly comparable, despite some overlap in simple cases. However this allows to interpret complexity in terms of interactions at work in a system (instead of making reference to any particular realization of this dynamics), and to shed some light on the role of initial conditions in complex systems.

Clustering of the 88 non-equivalent Elementary Cellular Automata according to their position in the space of information processing features. Rules are coloured according to their Wolfram class. ECA in class I are shown in black, class II in red, chaotic automata (class III) in green and automata displaying complex behaviour (class IV) in blue. In spite of some important important differences, information features and Wolfram class are seen to overlap to a certain extent.     

Effective RCA design using quantum dot cellular automata

Quantum dot Cellular Automata (QCA) is a transistor less technology alternative to CMOS for developing low-power, high speed digital circuits. Adder circuits are broadly employed in all digital computation systems. In this paper, a novel coplanar QCA full adder circuit is proposed which is designed with minimum number of QCA cells. The proposed full adder requires only 13 QCA cells, an area of 0.008 μm² and delay of about 2 clock cycles to implement its function. Then an efficient 4-bit Ripple Carry Adder (RCA) is designed based on the proposed full adder that performs higher end addition in an effective way. Simulations results are obtained precisely using QCA designer tool version 2.0.3. Also the simulation results shows that the proposed 4-bit Ripple Carry Adder (RCA) requires only 70 QCA cells, an area of 0.18 μm² and delay of about 5 clock cycles to implement its function with enhanced performance in terms of latency, area and QCA Cost. From the comparisons, it is found that our work achieves over 55% improvement in QCA cell count.     

Acceleration of cellular automata algorithms using genetic algorithms

The following problem is solved: Given a Cellular Automaton with continuous state space which simulates a physical system or process, use a Genetic Algorithm in order to find a Cellular Automaton with discrete state space, having the smallest possible lattice size and the smallest possible number of discrete states, the results of which are as close as possible to the results of the Cellular Automaton with continuous state space. The Cellular Automaton with discrete state space evolves much faster than the Cellular Automaton with continuous state space. The state spaces of two Cellular Automata have been discretized using a Genetic Algorithm. The first Cellular Automaton simulates the two-dimensional photoresist etching process in integrated circuit fabrication and the second is used to predict forest fire spreading. A general method for the discretization of the state space of Cellular Automata using a Genetic Algorithm is also presented. The aim of this work is to provide a method for accelerating the execution of algorithms based on Cellular Automata (Cellular Automata algorithms) and to build a bridge between Cellular Automata as models for physical systems and processes and Cellular Automata as a VLSI architecture.     

Data compression and encryption using cellular automata transforms

A family of basis functions, generated from the evolving states of Cellular Automata (CA), is used to compress and encrypt data. The operations required in encoding and decoding the data are described under the umbrella Cellular Automata Transforms (CAT). There is a huge number of these transform bases. CAT can be used in the way other mathematical transforms (e.g., Fourier, Discrete Cosine, Laplace, Wavelet, etc.) are utilized. In data-compression applications, the rules and pertinent keys used to generate the CA are selected to favor those that yield basis functions with the best information-packing characteristics. On the other hand, for encryption the selection is biased towards those with the tendency to yield an avalanche effect. In the latter case the transform process must be error-free.     

Linear cellular automata and Fischer automata

We study the sizes of minimal finite state machines associated with linear cellular automata. In particular, we construct a class of binary linear cellular automata whose corresponding minimal automata exhibit full exponential blow-up. These cellular automata have Hamming distance 1 to a permutation automaton. Moreover, the corresponding minimal Fischer automata as well as the minimal DFAs have maximal complexity. By contrast, the complexity of higher iterates of a cellular automaton always stays below the theoretical upper bound.     

Symmetric cellular automata

A class of cellular automata with permutation-invariant local rules acting on symmetric lattices is considered. In the case of two states, we show that these local rules are nothing else than a generalization of the rules of the game of Life. In view of the symmetry relative to the state renaming, we can further reduce the number of possible automata. For automata with symmetric rules acting on highly symmetric lattices, we can develop efficient algorithms to study their dynamics. Relevant examples are presented.