Reversibility of 1D Cellular Automata with Periodic Boundary over Finite Fields $\pmb{ {\mathbb{Z}}}_{p}$

The reversibility problem for linear cellular automata with null boundary defined by a rule matrix in the form of a pentadiagonal matrix was studied recently over the binary field ℤ₂ (del Rey and Rodriguez Sánchez in Appl. Math. Comput., 2011, doi:). In this paper, we study one-dimensional linear cellular automata with periodic boundary conditions over any finite field ℤ _p . For any given p≥2, we show that the reversibility problem can be reduced to solving a recurrence relation depending on the number of cells and the coefficients of the local rules defining the one-dimensional linear cellular automata. More specifically, for any given values (from any fixed field ℤ _p ) of the coefficients of the local rules, we outline a computer algorithm determining the recurrence relation which can be solved by testing reversibility of the cellular automaton for some finite number of cells. As an example, we give the full criteria for the reversibility of the one-dimensional linear cellular automata over the fields ℤ₂ and ℤ₃.     

From quantum cellular automata to quantum lattice gases

A natural architecture for nanoscale quantum computation is that of a quantum cellular automaton. Motivated by this observation, we begin an investigation of exactly unitary cellular automata. After proving that there can be no nontrivial, homogeneous, local, unitary, scalar cellular automaton in one dimension, we weaken the homogeneity condition and show that there are nontrivial, exactly unitary, partitioning cellular automata. We find a one-parameter family of evolution rules which are best interpreted as those for a one-particle quantum automaton. This model is naturally reformulated as a two component cellular automaton which we demonstrate to limit to the Dirac equation. We describe two generalizations of this automaton, the second, of which, to multiple interacting particles, is the correct definition of a quantum lattice gas.     

Synchronization of cellular automaton pairs

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.     

Linear cellular automata and recurring sequences in finite fields

A one-dimensional linear cellular automaton with periodic boundary conditions consists of a lattice of sites on a cylinder evolving according to a linear local interaction rule. Limit cycles for such a system are studied as sets of strings on which the rule acts as a shift of sizes/h; i.e., each string in the limit cycle cyclically shifts bys sites inh iterations of the rule. For any given rule, the size of the shift varies with the cylinder sizen. The analysis of shifts establishes an equivalence between the strings of values appearing in limit cycles for these automata, and linear recurring sequences in finite fields. Specifically, it is shown that a string appears in a limit cycle for a linear automaton rule on a cylinder sizen iff its values satisfy a linear recurrence relation defined by the shift value for thatn. The rich body of results on recurring sequences and finite fields can then be used to obtain detailed information on periodic behavior for these systems. Topics considered here include the inverse problem of identifying the set of linear automata rules for which a given string appears in a limit cycle, and the structure under operations (such as addition and complementation) of sets of limit cycle strings.     

Path-integral solution of the one-dimensional Dirac quantum cellular automaton

Quantum cellular automata, which describe the discrete and exactly causal unitary evolution of a lattice of quantum systems, have been recently considered as a fundamental approach to quantum field theory and a linear automaton for the Dirac equation in one dimension has been derived. In the linear case a quantum cellular automaton is isomorphic to a quantum walk and its evolution is conveniently formulated in terms of transition matrices. The semigroup structure of the matrices leads to a new kind of discrete path-integral, different from the well known Feynman checkerboard one, that is solved analytically in terms of Jacobi polynomials of the arbitrary mass parameter.     

A geometrical interpretation of the chaotic state of inhomogeneous deterministic cellular automata

We propose a geometrical interpretation of the chaotic state of inhomogeneous cellular automata. From the rules of the cellular automaton we construct a network. The percolating phase of this network coincides with the chaotic phase of the cellular automaton. We also report numerical tests of these ideas on several cellular automata.     

Universally programmable quantum cellular automaton

We discuss the role of classical control in the context of reversible quantum cellular automata. Employing the structure theorem for quantum cellular automata, we give a general construction scheme to turn an arbitrary cellular automaton with external classical control into an autonomous one, thereby proving the computational equivalence of these two models. We use this technique to construct a universally programmable cellular automaton on a one-dimensional lattice with single cell dimension 12.     

Deterministic one-dimensional cellular automata

A formal treatment of some of the properties of deterministic, rule 150, elementary one-dimensional cellular automata (CA) with null boundary conditions is presented. The general form of the characteristic polynomial of the CA global rule transition matrix is obtained. Mathematical relationships between the CA register lengths and the order of the corresponding group or semigroup structures are derived.     

Computation by Asynchronously Updating Cellular Automata

A known method to compute on an asynchronously updating cellular automaton is the simulation of a synchronous computing model on it. Such a scheme requires not only an increased number of cell states, but also the simulation of a global synchronization mechanism. Asynchronous systems tend to use synchronization only on a local scale—if they use it at all. Research on cellular automata that are truly asynchronous has been limited mostly to trivial phenomena, leaving issues such as computation unexplored. This paper presents an asynchronously updating cellular automaton that conducts computation without relying on a simulated global synchronization mechanism. The two-dimensional cellular automaton employs a Moore neighborhood and 85 totalistic transition rules describing the asynchronous interactions between the cells. Despite the probabilistic nature of asynchronous updating, the outcome of the dynamics is deterministic. This is achieved by simulating delay-insensitive circuits on it, a type of asynchronous circuit that is known for its robustness to variations in the timing of signals. We implement three primitive operators on the cellular automaton from which any arbitrary delay-insensitive circuit can be constructed and show how to connect the operators such that collisions of crossing signals are avoided.     

Zeno''s paradox in quantum cellular automata

The effect of Zeno's paradox in quantum theory is demonstrated with the aid of quantum mechanical cellular automata. It is shown that the degree of non-unitarity of the cellular automaton evolution and the frequency of consecutive measurements of cellular automaton states are operationally indistinguishable.     

Computational universality of fungal sandpile automata

Hyphae within the mycelia of the ascomycetous fungi are compartmentalised by septa. Each septum has a pore that allows for inter-compartmental and inter-hyphal streaming of cytosol and even organelles. The compartments, however, have special organelles, Woronin bodies, that can plug the pores. When the pores are blocked, no flow of cytoplasm takes place. Inspired by the controllable compartmentalisation within the mycelium of the ascomycetous fungi we designed two-dimensional fungal automata. A fungal automaton is a cellular automaton where communication between neighbouring cells can be blocked on demand. We demonstrate computational universality of the fungal automata by implementing sandpile cellular automata circuits there. We reduce the Monotone Circuit Value Problem to the Fungal Automaton Prediction Problem. We construct families of wires, cross-overs and gates to prove that the fungal automata are P-complete.     

开放边界条件下二维可转向主干道交通流模型的研究

在开放性边界条件下，利用改进的Nagel-Schreckenberg交通流模型，引入过路口车辆的可 转向机理，建立二维n速主干道元胞自动机交通流模型，研究了转向概率和边界条件对 干道交通状况的影响而导致的不同相变特性以及这两个因素对实现改善干道交通的组织作用 . 关键词： 元胞自动机 交通流 转向概率 相变     

Cylindrical cellular automata

A one-dimensional cellular automaton with periodic boundary conditions may be viewed as a lattice of sites on a cylinder evolving according to a local interaction rule. A technique is described for finding analytically the set of attractors for such an automaton. Given any one-dimensional automaton rule, a matrixA is defined such that the number of fixed points on an arbitrary cylinder size is given by the trace ofA ⁿ , where the powern depends linearly on the cylinder size. More generally, the number of strings of arbitrary length that appear in limit cycles of any fixed period is found as the solution of a linear recurrence relation derived from the characteristic equation of an associated matrix. The technique thus makes it possible, for any rule, to compute the number of limit cycles of any period on any cylinder size. To illustrate the technique, closed-form expressions are provided for the complete attractor structure of all two-neighbor rules. The analysis of attractors also identifies shifts as a basic mechanism underlying periodic behavior. Every limit cycle can be equivalently defined as a set of strings on which the action of the rule is a shift of sizes/h; i.e., each string cyclically shifts bys sites inh iterations of the rule. The study of shifts provides detailed information on the structure and number of limit cycles for one-dimensional automata.     

Cellular automaton model for traffic flow based on safe driving policies and human reactions

This paper proposes a new single-lane cellular automaton model for traffic flow. The model takes into account normal drivers’ spacing policies and transportation engineering practices to guarantee that microscopic vehicle behavior is more in line with vehicular movement in the real world. As a result, drivers’ reactions are based on a safety analysis that determines the most appropriate action for a vehicle to take. Hence, the model introduces a new set of simple rules to change the speed of vehicles that incorporates three important thresholds required by the follower vehicle to accelerate, slow down or maintain its speed. Thus, the space gap, relative speed and limited acceleration/deceleration capabilities are introduced into simulations. Simulation results obtained from a system with periodic conditions show that the model can smooth the speed drop when vehicles approach the upstream front of the traffic jam. Therefore, the model avoids unrealistic deceleration behavior found in most previous cellular automata models. Besides, the model is also capable of reproducing most empirical findings including the three states of traffic flow, the backward speed of the downstream front of the traffic jam, and different congested traffic patterns induced by a system with open boundary conditions with an on-ramp. Moreover, the new model preserves the computational simplicity of the cellular automata models.     

Quantum ω-Automata over Infinite Words and Their Relationships

Inspired by the results of finite automata working on infinite words, we studied the quantum ω-automata with Büchi, Muller, Rabin and Streett acceptance condition. Quantum finite automata play a pivotal part in quantum information and computational theory. Investigation of the power of quantum finite automata over infinite words is a natural goal. We have investigated the classes of quantum ω-automata from two aspects: the language recognition and their closure properties. It has been shown that quantum Muller automaton is more dominant than quantum Büchi automaton. Furthermore, we have demonstrated the languages recognized by one-way quantum finite automata with different quantum acceptance conditions. Finally, we have proved the closure properties of quantum ω-automata.

     

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.     

Analytical investigation of the boundary-triggered phase transition dynamics in a cellular automata model with a slow-to-start rule

Previous studies suggest that there are three different jam phases in the cellular automata automaton model with a slow-to-start rule under open boundaries.In the present paper,the dynamics of each free-flow-jam phase transition is studied.By analysing the microscopic behaviour of the traffic flow,we obtain analytical results on the phase transition dynamics.Our results can describe the detailed time evolution of the system during phase transition,while they provide good approximation for the numerical simulation data.These findings can perfectly explain the microscopic mechanism and details of the boundary-triggered phase transition dynamics.     

Effects of boundary conditions on spatially periodic states

We investigate analytically and numerically the influence of linear homogeneous boundary conditions on the stationary solutions of a simple model for cellular pattern formation in one dimension. For all boundary conditions there exists in a reduced wavenumber band at least one static solution where the amplitude falls below its bulk value near the boundary (“Type-I” solution). A linear stability analysis of the uniform state at threshold reveals that Type-I solutions are often unstable. Then there exists in the full Eckhaus-stable band, a static solution where the amplitude rises above its bulk value near the boundary (“Type-II” solution), or a limit-cycle solution where the amplitude near the boundary oscillates. These solutions bifurcate from the homogeneous state below the bulk threshold and therefore remain finite at threshold.     

Rotators,periodicity, and absence of diffusion in cyclic cellular automata

Cyclic cellular automata are two-dimensional cellular automata which generalize lattice versions of the Lorentz gas and certain biochemistry models of artificial life. We show that rotators and time reversibility play a special role in the creation of closed orbits in cyclic cellular automata. We also prove that almost every orbit is closed (periodic) and the absence of diffusion for the flipping rotator model (also known as the ant).