Invariant Measures and Decay of Correlations for a Class of Ergodic Probabilistic Cellular Automata

We give new sufficient ergodicity conditions for two-state probabilistic cellular automata (PCA) of any dimension and any radius. The proof of this result is based on an extended version of the duality concept. Under these assumptions, in the one dimensional case, we study some properties of the unique invariant measure and show that it is shift-mixing. Also, the decay of correlation is studied in detail. In this sense, the extended concept of duality gives exponential decay of correlation and allows to compute explicitly all the constants involved.     

Phase Transition and Correlation Decay in Coupled Map Lattices

For a Coupled Map Lattice with a specific strong coupling emulating Stavskaya’s probabilistic cellular automata, we prove the existence of a phase transition using a Peierls argument, and exponential convergence to the invariant measures for a wide class of initial states using a technique of decoupling originally developed for weak coupling. This implies the exponential decay, in space and in time, of the correlation functions of the invariant measures.     

Cellular automata and nonlinear dynamical models

A point of view is pursued in which cellular automata (CA) are viewed as a laboratory to investigate nonlinear dynamics. We introduce an irreversible cellular automaton (ICA) with minimal coupling which exhibit class 4 behavior. Periodic structures (phases) are studied along with their stability properties. We observe topological conserved quantities and introduce a classification of structures via a topological number. Time reversal invariant cellular automata (TRCA) are also investigated; we discuss stability of phases and use a concept of local entropy to measure the growth of chaos in slightly perturbed phases. A classification of approach to chaos into 3 classes is proposed for TRCA.     

On ergodic one-dimensional cellular automata

We show that all onto cellular automata defined on the binary sequence space are invariant with respect to the Haar measure, and that an extensive class of such maps (including many nonlinear ones) are strongly mixing with respect to the Haar measure.This work was supported in part by grants from NSERC of Canada     

Ergodicity of quantum cellular automata

We define a class of dynamical maps on the quasi-local algebra of a quantum spin system, which are quantum analoges of probabilistic cellular automata. We develop criteria for such a system to be ergodic, i.e., to posses a unique invariant state. Intuitively, ergodicity obtains if the local transition operators exhibit sufficiently large disorder. The ergodicity criteria also imply bounds for the exponential decay of correlations in the unique invariant state. The main technical tool is a quantum version of oscillation norms, defined in the classical case as the sum over all sites of the variations of an observable with respect to local spin flips.     

Law of Large Numbers for Non-Local Functions on Probabilistic Cellular Automata

We prove a multi-dimensional version of the law of large numbers for invariant measures of a large class of probabilistic cellular automata, whose transition probabilities satisfy some inequalities, which are known to assure their ergodicity. In some non-ergodic cases analogous results have been obtained for local functions. We deal with a larger class of functions, which includes some non-local ones.     

Self-organisation in Cellular Automata with Coalescent Particles: Qualitative and Quantitative Approaches

This article introduces new tools to study self-organisation in a family of simple cellular automata which contain some particle-like objects with good collision properties (coalescence) in their time evolution. We draw an initial configuration at random according to some initial shift-ergodic measure, and use the limit measure to describe the asymptotic behaviour of the automata. We first take a qualitative approach, i.e. we obtain information on the limit measure(s). We prove that only particles moving in one particular direction can persist asymptotically. This provides some previously unknown information on the limit measures of various deterministic and probabilistic cellular automata: 3 and 4-cyclic cellular automata [introduced by Fisch (J Theor Probab 3(2):311–338, 1990; Phys D 45(1–3):19–25, 1990)], one-sided captive cellular automata [introduced by Theyssier (Captive Cellular Automata, 2004)], the majority-traffic cellular automaton, a self stabilisation process towards a discrete line [introduced by Regnault and Rémila (in: Mathematical Foundations of Computer Science 2015—40th International Symposium, MFCS 2015, Milan, Italy, Proceedings, Part I, 2015)]. In a second time we restrict our study to a subclass, the gliders cellular automata. For this class we show quantitative results, consisting in the asymptotic law of some parameters: the entry times [generalising K ?rka et al. (in: Proceedings of AUTOMATA, 2011)], the density of particles and the rate of convergence to the limit measure.     

Traveling patterns in cellular automata

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:相似文献   

A new cellular automata model of traffic flow with negative exponential weighted look-ahead potential

With the development of traffic systems, some issues such as traffic jams become more and more serious. Efficient traffic flow theory is needed to guide the overall controlling, organizing and management of traffic systems. On the basis of the cellular automata model and the traffic flow model with look-ahead potential, a new cellular automata traffic flow model with negative exponential weighted look-ahead potential is presented in this paper. By introducing the negative exponential weighting coefficient into the look-ahead potential and endowing the potential of vehicles closer to the driver with a greater coefficient, the modeling process is more suitable for the driver's random decision-making process which is based on the traffic environment that the driver is facing. The fundamental diagrams for different weighting parameters are obtained by using numerical simulations which show that the negative exponential weighting coefficient has an obvious effect on high density traffic flux. The complex high density non-linear traffic behavior is also reproduced by numerical simulations.     

Cellular automata for nanometer-scale computation

Cellular automata have recently been proposed as an architecture for dense, locally-interacting arrays of submicron devices. However, because conventional von Neumann cellular automata do not correctly reflect the long-range behavior of typical inter-device interactions, they do not provide a suitable theoretical model for the proposed device arrays. In this paper we define replica cellular automata, a class of cellular automata that can be generated from lattice-gas cellular automata. We show that for inter-device interactions that have a well-defined screening length D, replica cellular automata provide a suitable formal model. As an example of their applicability, we exhibit a computation-universal cellular automata architecture in which the cells consist of charge-transfer quantum dot devices.     

复合元胞自动机系统反向迭代加密技术研究

提出了元胞自动机的交叉复合在序列R下随机复合的思想,分析了复合元胞自动机系统的密码学特性,利用元胞自动机反向迭代加密技术,构造了两个基于复合元胞自动机的密码系统.新的复合元胞自动机密码系统很好地解决了单一元胞自动机密码系统中存在的误差单向扩散的问题,并且能够以较小的规则半径获得大密钥空间.计算机仿真结果表明,复合元胞自动机密码系统具有良好的扰乱和扩散性能,能够有效地抵抗蛮力攻击和差分分析. 关键词： 离散动力系统 复合元胞自动机 反向迭代 分组密码     

Renormalization of Cellular Automata and Self-Similarity

We study self-similarity in one-dimensional probabilistic cellular automata (PCA) using the renormalization technique. We introduce a general framework for algebraic construction of renormalization groups (RG) on cellular automata and apply it to exhaustively search the rule space for automata displaying dynamic criticality.     

Ergodicity of the 2D Navier--Stokes Equations¶with Random Forcing

We consider the Navier–Stokes equation on a two dimensional torus with a random force, acting at discrete times and analytic in space, for arbitrarily small viscosity coefficient. We prove the existence and uniqueness of the invariant measure for this system as well as exponential mixing in time. Received: 18 May 2000 / Accepted: 8 December 2000     

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).     

Evolution of the Probability Measure for the Majda Model: New Invariant Measures and Breathing PDFs

In 1993, Majda proposed a simple, random shear model from which scalar intermittency was rigorously predicted for the invariant probability measure of passive tracers. In this work, we present an integral formulation for the tracer measure, which leads to a new, comprehensive study on its temporal evolution based on Monte Carlo simulation and direct numerical integration. An interesting, non-monotonic “breathing” phenomenon is discovered from these results and carefully defined, with a solid example for special initial data to predict such phenomenon. The signature of this phenomenon may persist at long time, characterized by the approach of the PDF core to its infinite time, invariant value. We find that this approach may be strongly dependent on the non-dimensional Péclet number, of which the invariant measure itself is independent. Further, the “breathing” PDF is recovered as a new invariant measure in a distinguished time scale in the diffusionless limit. Rigorous asymptotic analysis is also performed to identify the Gaussian core of the invariant measures, and the critical rate at which the heavy, stretched exponential regime propagates towards the tail as a function of time is calculated.     

The dynamics of defect ensembles in one-dimensional cellular automata

We investigate the dynamics of ensembles of diffusive defects in one-dimensional deterministic cellular automata. The work builds on earlier results on individual random walks in cellular automata. Here we give a natural condition guaranteeing diffusive behavior also in the presence of other defects. Simple branching and birth mechanisms are introduced and prototype classes of cellular automata exhibiting weakly interacting walks capable of annihilation and coalescence are studied. Their equilibrium behavior is also characterized. The design principles of cellular automata with desired diffusive interaction properties become transparent from this analysis.     

Statistical mechanics of probabilistic cellular automata

We investigate the behavior of discrete-time probabilistic cellular automata (PCA), which are Markov processes on spin configurations on ad-dimensional lattice, from a rigorous statistical mechanics point of view. In particular, we exploit, whenever possible, the correspondence between stationary measures on the space-time histories of PCAs on ^d and translation-invariant Gibbs states for a related Hamiltonian on ( ^d+1). This leads to a simple large-deviation formula for the space-time histories of the PCA and a proof that in a high-temperature regime the stationary states of the PCA are Gibbsian. We also obtain results about entropy, fluctuations, and correlation inequalities, and demonstrate uniqueness of the invariant state and exponential decay of correlations in a high-noise regime. We discuss phase transitions in the low-noise (or low-temperature) regime and review Toom's proof of nonergodicity of a certain class of PCAs.     

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.     

Ergodicity of the Finite Dimensional Approximation of the 3D Navier–Stokes Equations Forced by a Degenerate Noise

We prove ergodicity of the finite dimensional approximations of the three dimensional Navier–Stokes equations, driven by a random force. The forcing noise acts only on a few modes and some algebraic conditions on the forced modes are found that imply the ergodicity. The convergence rate to the unique invariant measure is shown to be exponential.     

Quantum entropy production as a measure of irreversibility

We consider conservative quantum evolutions possibly interrupted by macroscopic measurements. When started in a nonequilibrium state, the resulting path-space measure is not time-reversal invariant and the weight of time-reversal breaking equals the exponential of the entropy production. The mean entropy production can then be expressed via a relative entropy on the level of histories. This gives a partial extension of the result for classical systems, that the entropy production is given by the source term of time-reversal breaking in the path-space measure.