The one-dimensional cyclic cellular automaton: A system with deterministic dynamics that emulates an interacting particle system with stochastic dynamics

Consider a cellular automaton defined on where each lattice site may take on one ofN values, referred to as colors. TheN colors are arranged in a cyclic hierarchy, meaning that colork follows colork–1 modN (k=0,...,N–1). Any two colors that are not adjacent in this hierarchy form an inert pair. In this scheme, there is symmetry in theN colors. Initialized the cellular automaton with product measure, and let time pass in discrete units. To get the configuration at timet+1 from the one at timet, each lattice site looks at the colors of its two nearest neighbors, and if it sees the color that follows its own color, then that site changes color to the color that follows; otherwise, that site does not change color. All such updates occur synchronously at timet+1. For each value ofN2, the fundamental question is whether each site in the cellular automaton changes color infinitely often (fluctuation) or only finitely often (fixation). We prove here that ifN4, then fluctuation occurs, and ifN5, then fixation occurs.     

Stability of Cellular Automata Trajectories Revisited: Branching Walks and Lyapunov Profiles

We study non-equilibrium defect accumulation dynamics on a cellular automaton trajectory: a branching walk process in which a defect creates a successor on any neighborhood site whose update it affects. On an infinite lattice, defects accumulate at different exponential rates in different directions, giving rise to the Lyapunov profile. This profile quantifies instability of a cellular automaton evolution and is connected to the theory of large deviations. We rigorously and empirically study Lyapunov profiles generated from random initial states. We also introduce explicit and computationally feasible variational methods to compute the Lyapunov profiles for periodic configurations, thus developing an analog of Floquet theory for cellular automata.     

Self-injective rings and linear (weak) inverses of linear finite automata over rings

LetR be a finite commutative ring with identity and τ be a nonnegative integer. In studying linear finite automata, one of the basic problems is how to characterize the class of rings which have the property that every (weakly) invertible linear finite automaton ℳ with delay τ over R has a linear finite automaton ℳ′ over R which is a (weak) inverse with delay τ of ℳ. The rings and linear finite automata are studied by means of modules and it is proved that *-rings are equivalent to self-injective rings, and the unsolved problem (for τ=0) is solved. Moreover, a further problem of how to characterize the class of rings which have the property that every invertible with delay τ linear finite automaton ℳ overR has a linear finite automaton ℳ′ over R which is an inverse with delay τ′ for some τ′⩾τ is studied and solved. Project supported by the National Natural Science Foundation of China(Grant No. 69773015).     

Dynamics groups of asynchronous cellular automata

We say that a finite asynchronous cellular automaton (or more generally, any sequential dynamical system) is π-independent if its set of periodic points are independent of the order that the local functions are applied. In this case, the local functions permute the periodic points, and these permutations generate the dynamics group. We have previously shown that exactly 104 of the possible 2²³=2562^{2^{3}}=256 cellular automaton rules are π-independent. In the article, we classify the periodic states of these systems and describe their dynamics groups, which are quotients of Coxeter groups. The dynamics groups provide information about permissible dynamics as a function of update sequence and, as such, connect discrete dynamical systems, group theory, and algebraic combinatorics in a new and interesting way. We conclude with a discussion of numerous open problems and directions for future research.     

Sharp metastability threshold for two-dimensional bootstrap percolation

 In the bootstrap percolation model, sites in an L by L square are initially independently declared active with probability p. At each time step, an inactive site becomes active if at least two of its four neighbours are active. We study the behaviour as p→0 and L→∞ simultaneously of the probability I(L,p) that the entire square is eventually active. We prove that I(L,p)→1 if , and I(L,p)→0 if , where λ=π²/18. We prove the same behaviour, with the same threshold λ, for the probability J(L,p) that a site is active by time L in the process on the infinite lattice. The same results hold for the so-called modified bootstrap percolation model, but with threshold λ^′=π²/6. The existence of the thresholds λ,λ^′ settles a conjecture of Aizenman and Lebowitz [3], while the determination of their values corrects numerical predictions of Adler, Stauffer and Aharony [2]. Received: 12 May 2002 / Revised version: 12 August 2002 / Published online: 14 November 2002 Research funded in part by NSF Grant DMS-0072398 Mathematics Subject Classification (2000): Primary 60K35; Secondary 82B43 Key words or phrases: Bootstrap percolation – Cellular automaton – Metastability – Finite-size scaling     

The asymmetric random cluster model and comparison of Ising and Potts models

We introduce the asymmetric random cluster (or ARC) model, which is a graphical representation of the Potts lattice gas, and establish its basic properties. The ARC model allows a rich variety of comparisons (in the FKG sense) between models with different parameter values; we give, for example, values (β, h) for which the 0‘s configuration in the Potts lattice gas is dominated by the “+” configuration of the (β, h) Ising model. The Potts model, with possibly an external field applied to one of the spins, is a special case of the Potts lattice gas, which allows our comparisons to yield rigorous bounds on the critical temperatures of Potts models. For example, we obtain 0.571 ≤ 1 − exp(−β _c ) ≤ 0.600 for the 9-state Potts model on the hexagonal lattice. Another comparison bounds the movement of the critical line when a small Potts interaction is added to a lattice gas which otherwise has only interparticle attraction. ARC models can also be compared to related models such as the partial FK model, obtained by deleting a fraction of the nonsingleton clusters from a realization of the Fortuin-Kasteleyn random cluster model. This comparison leads to bounds on the effects of small annealed site dilution on the critical temperature of the Potts model. Received: 27 August 2000 / Revised version: 31 August 2000 / Published online: 8 May 2001     

Cutting Sequences for Geodesic Flow on the Modular Surface and Continued Fractions

 This paper describes the cutting sequences of geodesic flow on the modular surface with respect to the standard fundamental domain of . The cutting sequence for a vertical geodesic is related to a one-dimensional continued fraction expansion for θ, called the one-dimensional Minkowski geodesic continued fraction (MGCF) expansion, which is associated to a parametrized family of reduced bases of a family of 2-dimensional lattices. The set of cutting sequences for all geodesics forms a two-sided shift in a symbol space which has the same set of forbidden blocks as for vertical geodesics. We show that this shift is not a sofic shift, and that it characterizes the fundamental domain ℱ up to an isometry of the hyperbolic plane . We give conversion methods between the cutting sequence for the vertical geodesic , the MGCF expansion of θ and the additive ordinary continued fraction (ACF) expansion of θ. We show that the cutting sequence and MGCF expansions can each be computed from the other by a finite automaton, and the ACF expansion of θ can be computed from the cutting sequence for the vertical geodesic θ + it by a finite automaton. However, the cutting sequence for a vertical geodesic cannot be computed from the ACF expansion by any finite automaton, but there is an algorithm to compute its first symbols when given as input the first symbols of the ACF expansion, which takes time and space . (Received 11 August 2000; in revised form 18 April 2001)     

Cutting Sequences for Geodesic Flow on the Modular Surface and Continued Fractions

 This paper describes the cutting sequences of geodesic flow on the modular surface with respect to the standard fundamental domain of . The cutting sequence for a vertical geodesic is related to a one-dimensional continued fraction expansion for θ, called the one-dimensional Minkowski geodesic continued fraction (MGCF) expansion, which is associated to a parametrized family of reduced bases of a family of 2-dimensional lattices. The set of cutting sequences for all geodesics forms a two-sided shift in a symbol space which has the same set of forbidden blocks as for vertical geodesics. We show that this shift is not a sofic shift, and that it characterizes the fundamental domain ℱ up to an isometry of the hyperbolic plane . We give conversion methods between the cutting sequence for the vertical geodesic , the MGCF expansion of θ and the additive ordinary continued fraction (ACF) expansion of θ. We show that the cutting sequence and MGCF expansions can each be computed from the other by a finite automaton, and the ACF expansion of θ can be computed from the cutting sequence for the vertical geodesic θ + it by a finite automaton. However, the cutting sequence for a vertical geodesic cannot be computed from the ACF expansion by any finite automaton, but there is an algorithm to compute its first symbols when given as input the first symbols of the ACF expansion, which takes time and space .     

On the classification of bases in <Emphasis Type="Italic">P</Emphasis><Subscript>k</Subscript> according to the decidability of the completeness problem for automata

The completeness problem for bases of the form Φ ∪ ν, where Φ ⊆ P _k and ν is a finite system of automaton functions, is considered. Previously, the problem for k = 2 was solved by the author; it was also shown that there is an algorithm for determining the completeness of the system Φ∪ν when [Φ] = Pk. The paper is concerned with the case where [Φ] is the maximal (precomplete) class in P _k . The problem of completeness for systems Φ ∪ ν is shown to be undecidable if Φ is embedded in a Slupecki class and algorithmically decidable if Φ contains the class preserving all constants. Thus, the bases in P _k , k ≥ 3, can be classified according to their ability to guarantee the decidability of the completeness problem for automaton functions.     

22号初等元胞自动机的演化复杂性

Cellular automata are the discrete dynamical systems of simple construction but with complex and varied behaviors. In this paper, the elementary cellular automaton of rule 22 is studied by the tools of formal language theory and symbolic dynamics. Its temporal evolution orbits are coarse-grained into evolution sequences and the evolution languages are defined. It is proved that for every n≥2 its width n evolution language is not regular.