Search

The basic κ -color box-ball (BBS) system is an integrable cellular automaton on one dimensional lattice whose local states take { 0 , 1 , ... , κ } with 0 regarded as an empty box. The time evolution is defined by a combinatorial rule of quantum group theoretical origin, and the complete set of conserved quantities is given by a κ -tuple of Young diagrams. In the randomized BBS, a probability distribution on { 0 , 1 , ... , κ } to independently fill the consecutive n sites in the initial state induces a highly nontrivial probability measure on the κ -tuple of those invariant Young diagrams. In a recent work Kuniba et al. (Nucl Phys B 937:240–271, 2018), their large n 'equilibrium shape' has been determined in terms of Schur polynomials by a Markov chain method and also by a very different approach of thermodynamic Bethe ansatz (TBA). In this paper, we establish a large deviations principle for the row lengths of the invariant Young diagrams. As a corollary, they are shown to converge almost surely to the equilibrium shape at an exponential rate. We also refine the TBA analysis and obtain the exact scaling form of the vacancy, the row length and the column multiplicity, which exhibit nontrivial factorization in a one-parameter specialization. [ABSTRACT FROM AUTHOR]

On the space of Ising configurations on the 2-d square lattice, we consider a family of non Gibbsian measures introduced by using a pair Hamiltonian, depending on an additional inertial parameter q. These measures are related to the usual Gibbs measure on Z 2 and turn out to be the marginal of the Gibbs measure of a suitable Ising model on the hexagonal lattice. The inertial parameter q tunes the geometry of the system. The critical behaviour and the decay of correlation functions of these measures are studied thanks to relation with the Random Cluster model. This measure turns out to be interesting also because it is the stationary measure of a class of Probabilistic Cellular Automata (PCA). Such PCA can be used to obtain a fast sample of the Ising measures on 2-d lattices. [ABSTRACT FROM AUTHOR]

We consider an agent-based model with exponentially distributed waiting times in which two types of agents interact locally over a graph, and based on this interaction and on the value of a common intolerance threshold τ, decide whether to change their types. This is equivalent to a zero-temperature ising model with Glauber dynamics, an asynchronous cellular automaton with extended Moore neighborhoods, or a Schelling model of self-organized segregation in an open system, and has applications in the analysis of social and biological networks, and spin glasses systems. Some rigorous results were recently obtained in the theoretical computer science literature, and this work provides several extensions. We enlarge the intolerance interval leading to the expected formation of large segregated regions of agents of a single type from the known size ϵ>0 to size ≈0.134. Namely, we show that for 0.433<τ<1/2 (and by symmetry 1/2<τ<0.567), the expected size of the largest segregated region containing an arbitrary agent is exponential in the size of the neighborhood. We further extend the interval leading to expected large segregated regions to size ≈0.312 considering “almost segregated” regions, namely regions where the ratio of the number of agents of one type and the number of agents of the other type vanishes quickly as the size of the neighborhood grows. In this case, we show that for 0.344<τ≤0.433 (and by symmetry for 0.567≤τ<0.656) the expected size of the largest almost segregated region containing an arbitrary agent is exponential in the size of the neighborhood. This behavior is reminiscent of supercritical percolation, where small clusters of empty sites can be observed within any sufficiently large region of the occupied percolation cluster. The exponential bounds that we provide also imply that complete segregation, where agents of a single type cover the whole grid, does not occur with high probability for p=1/2 and the range of intolerance considered. [ABSTRACT FROM AUTHOR]

In dynamical systems, some of the most important questions are related to phase transitions and convergence time. We consider a one-dimensional probabilistic cellular automaton where their components assume two possible states, zero and one, and interact with their two nearest neighbors at each time step. Under the local interaction, if the component is in the same state as its two neighbors, it does not change its state. In the other cases, a component in state zero turns into a one with probability $$\alpha ,$$ and a component in state one turns into a zero with probability $$1-\beta $$ . For certain values of $$\alpha $$ and $$\beta $$ , we show that the process will always converge weakly to $$\delta _{0},$$ the measure concentrated on the configuration where all the components are zeros. Moreover, the mean time of this convergence is finite, and we describe an upper bound in this case, which is a linear function of the initial distribution. We also demonstrate an application of our results to the percolation PCA. Finally, we use mean-field approximation and Monte Carlo simulations to show coexistence of three distinct behaviours for some values of parameters $$\alpha $$ and $$\beta $$ . [ABSTRACT FROM AUTHOR]

While the reversibility of multidimensional cellular automata is undecidable and there exists a criterion for determining if a multidimensional linear cellular automaton is reversible, there are only a few results about the reversibility problem of multidimensional linear cellular automata under boundary conditions. This work proposes a criterion for testing the reversibility of a multidimensional linear cellular automaton under null boundary condition and an algorithm for the computation of its reverse, if it exists. The investigation of the dynamical behavior of a multidimensional linear cellular automaton under null boundary condition is equivalent to elucidating the properties of the block Toeplitz matrix. The proposed criterion significantly reduces the computational cost whenever the number of cells or the dimension is large; the discussion can also apply to cellular automata under periodic boundary conditions with a minor modification. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Metastability is a physical phenomenon ubiquitous in first order phase transitions. A fruitful mathematical way to approach this phenomenon is the study of rare transitions Markov chains. For Metropolis chains associated with statistical mechanics systems, this phenomenon has been described in an elegant way in terms of the energy landscape associated to the Hamiltonian of the system. In this paper, we provide a similar description in the general rare transitions setup. Beside their theoretical content, we believe that our results are a useful tool to approach metastability for non-Metropolis systems such as Probabilistic Cellular Automata. [ABSTRACT FROM AUTHOR]

Reversible cellular automata are seen as microscopic physical models, and their states of macroscopic equilibrium are described using invariant probability measures. We establish a connection between the invariance of Gibbs measures and the conservation of additive quantities in surjective cellular automata. Namely, we show that the simplex of shift-invariant Gibbs measures associated to a Hamiltonian is invariant under a surjective cellular automaton if and only if the cellular automaton conserves the Hamiltonian. A special case is the (well-known) invariance of the uniform Bernoulli measure under surjective cellular automata, which corresponds to the conservation of the trivial Hamiltonian. As an application, we obtain results indicating the lack of (non-trivial) Gibbs or Markov invariant measures for 'sufficiently chaotic' cellular automata. We discuss the relevance of the randomization property of algebraic cellular automata to the problem of approach to macroscopic equilibrium, and pose several open questions. As an aside, a shift-invariant pre-image of a Gibbs measure under a pre-injective factor map between shifts of finite type turns out to be always a Gibbs measure. We provide a sufficient condition under which the image of a Gibbs measure under a pre-injective factor map is not a Gibbs measure. We point out a potential application of pre-injective factor maps as a tool in the study of phase transitions in statistical mechanical models. [ABSTRACT FROM AUTHOR]

Imagine a huge (in theory, infinite) space, whose elements are called components. We say that we have a configuration, if for every component we have specified its state. All components have one and the same finite set $$M$$ of possible states and one of the elements of $$M$$ is called zero. If all the components of a configuration are zeros, we call it 'all zeros'. We are especially interested in those configurations, in which only a bounded set of components are in a state different from zero; such a configuration is called an island. Our time is discrete and we may imagine that, due to the forces of nature, at every time step the whole configuration (landscape) is subject to a deterministic uniform local rule $$D$$ such that non-zero components may appear only in the vicinity of already existing non-zero components (like in percolation or contact processes). We say that an operator $$D$$ erodes an island $$x$$ if there is a natural $$t$$ such that $$x D^t =$$ 'all zeros', that is $$t$$ iterative applications of $$D$$ turn $$x$$ into 'all zeros'. We call $$D$$ an eroder if it erodes all islands. We look for an algorithm which decides for any $$D$$ whether it is an eroder or not and does it make islands grow or not. In general this problem is algorithmically unsolvable, so we need to restrict our scope; in addition to the afore-mentioned conditions we assume that $$D$$ is monotonic. Studying such processes one has to decide whether time and space are discrete or continuous and in this study we choose discrete time and continuous space just because this case is underrepresented in the literature. But especially important is the set of possible states of every single component. Years ago one of us (A. Toom) presented a rule to decide whether $$D$$ is an eroder for the case when every component has only two possible states. A. Toom also showed that if $$D$$ is an eroder, then it erodes any island in time, which is linear in the diameter of the island. In this work every component has three possible states. It turned out that the difference between two and three states, which may seem trivial, in fact leads to a qualitative difference: in the three-states case an eroder may take non-linear time to reach 'all zeros'. Also, unlike two-state case, in the three-state case we have, in addition to eroders, to introduce degraders which reduce any island to an island where states of all components take only two possible values. Our main results are stated as three theorems. Theorem 1 gives sufficient (but regretfully not necessary) conditions for a linear degrader and an eroder. Theorems 2 and 3 concentrate on the case when $$D$$ needs a non-linear time to erode an island-a case impossible if states of components take only two values. In addition, Theorem 3 presents a sufficient condition for islands to grow. [ABSTRACT FROM AUTHOR]

This paper considers a class of probabilistic cellular automata undergoing a phase transition with an absorbing state. Denoting by $${\mathcal {U}}(x)$$ the neighbourhood of site $$x$$ , the transition probability is $$T(\eta _x = 1 | \eta _{{\mathcal {U}}(x)}) = 0$$ if $$\eta _{{\mathcal {U}}(x)}= \mathbf {0}$$ or $$p$$ otherwise, $$\forall x \in \mathbb {Z}$$ . For any $$\mathcal {U}$$ there exists a non-trivial critical probability $$p_c( {\mathcal {U}})$$ that separates a phase with an absorbing state from a fluctuating phase. This paper studies how the neighbourhood affects the value of $$p_c( {\mathcal {U}})$$ and provides lower bounds for $$p_c( {\mathcal {U}})$$ . Furthermore, by using dynamic renormalization techniques, we prove that the expected convergence time of the processes on a finite space with periodic boundaries grows exponentially (resp. logarithmically) with the system size if $$p > p_c$$ (resp. $$p

We describe a real-space renormalisation scheme for non-equilibrium probabilistic cellular automata (PCA) models, and apply it to a two-dimensional binary PCA. An exact renormalisation scheme is rare, and therefore we provide a method for computing the stationary probability distribution of states for such models with which to weight the renormalisation, effectively minimising the error in the scale transformation. While a mean-field approximation is trivial, we use the principle of maximum entropy to incorporate nearest-neighbour spin-correlations in the steady-state probability distribution. In doing so we find the fixed point of the renormalisation is modified by the steady-state approximation order. [ABSTRACT FROM AUTHOR]

We study tunneling and mixing time for a non-reversible probabilistic cellular automaton. With a suitable choice of the parameters, we first show that the stationary distribution is close in total variation to a low temperature Ising model. Then we prove that both the mixing time and the time to exit a metastable state grow polynomially in the size of the system, while this growth is exponential in reversible dynamics. In this model, non-reversibility, parallel updatings and a suitable choice of boundary conditions combine to produce an efficient dynamical stability. [ABSTRACT FROM AUTHOR]

We present a detailed numerical analysis of the phase diagrams for some majority voter probabilistic cellular automata and connect the results with theory, enabling us to prove many of the observed features. [ABSTRACT FROM AUTHOR]

Probabilistic cellular automata (PCA) are simple models used to study dynamical phase transitions. There exist mean field approximations to PCA that can be shown to exhibit a phase transition. We introduce a model interpolating between a class of PCA, called majority voters, and their corresponding mean field models. Using graphical methods, we prove that this model undergoes a phase transition. [ABSTRACT FROM AUTHOR]

Bootstrap percolation is a type of cellular automaton on graphs, introduced as a simple model of the dynamics of ferromagnetism. Vertices in a graph can be in one of two states: 'healthy' or 'infected' and from an initial configuration of states, healthy vertices become infected by local rules. While the usual bootstrap processes are monotone in the sets of infected vertices, in this paper, a modification is examined in which infected vertices can return to a healthy state. Vertices are initially infected independently at random and the central question is whether all vertices eventually become infected. The model examined here is such a process on a square grid for which healthy vertices with at least two infected neighbours become infected and infected vertices with no infected neighbours become healthy. Sharp thresholds are given for the critical probability of initial infections for all vertices eventually to become infected. [ABSTRACT FROM AUTHOR]

Whether a system is to be considered complex or not depends on how one searches for correlations. We propose a general scheme for calculation of entropies in lattice systems that has high flexibility in how correlations are successively taken into account. Compared to the traditional approach for estimating the entropy density, in which successive approximations build on step-wise extensions of blocks of symbols, we show that one can take larger steps when collecting the statistics necessary to calculate the entropy density of the system. In one dimension this means that, instead of a single sweep over the system in which states are read sequentially, one take several sweeps with larger steps so that eventually the whole lattice is covered. This means that the information in correlations is captured in a different way, and in some situations this will lead to a considerably much faster convergence of the entropy density estimate as a function of the size of the configurations used in the estimate. The formalism is exemplified with both an example of a free energy minimisation scheme for the two-dimensional Ising model, and an example of increasingly complex spatial correlations generated by the time evolution of elementary cellular automaton rule 60. [ABSTRACT FROM AUTHOR]

We propose a unified approach to reversible and irreversible pca dynamics, and we show that in the case of 1D and 2D nearest neighbor Ising systems with periodic boundary conditions we are able to compute the stationary measure of the dynamics also when the latter is irreversible. We also show how, according to (P. Dai Pra et al. in J. Stat. Phys. 149(4):722-737, ), the stationary measure is very close to the Gibbs for a suitable choice of the parameters of the pca dynamics, both in the reversible and in the irreversible cases. We discuss some numerical aspects regarding this topic, including a possible parallel implementation. [ABSTRACT FROM AUTHOR]

The study of systems with multiple (not necessarily degenerate) metastable states presents subtle difficulties from the mathematical point of view related to the variational problem that has to be solved in these cases. We prove sufficient conditions to identify multiple metastable states. Since this analysis typically involves non-trivial technical issues, we give different conditions that can be chosen appropriately depending on the specific model under study. We show how these results can be used to attack the problem of multiple metastable states via the use of the modern approaches to metastability. We finally apply these general results to the Blume-Capel model for a particular choice of the parameters for which the model happens to have two multiple not degenerate in energy metastable states. We estimate in probability the time for the transition from the metastable states to the stable state. Moreover we identify the set of critical configurations that represent the minimal gate for the transition. [ABSTRACT FROM AUTHOR]

We consider the problem of approximate sampling from the finite volume Gibbs measure with a general pair interaction. We exhibit a parallel dynamics (Probabilistic Cellular Automaton) which efficiently implements the sampling. In this dynamics the product measure that gives the new configuration in each site contains a term that tends to favour the original value of each spin. This is the main ingredient that allows one to prove that the stationary distribution of the PCA is close in total variation to the Gibbs measure. The presence of the parameter that drives the 'inertial' term mentioned above gives the possibility to control the degree of parallelism of the numerical implementation of the dynamics. [ABSTRACT FROM AUTHOR]

We analyze the abelian sandpile model on ℤ for the starting configuration of n particles in the origin and 2 d−2 particles otherwise. We give a new short proof of the theorem of Fey, Levine and Peres (J. Stat. Phys. 198:143-159, ) that the radius of the toppled cluster of this configuration is O( n). [ABSTRACT FROM AUTHOR]

We investigate the low-noise regime of a large class of probabilistic cellular automata, including the North-East-Center model of Toom. They are defined as stochastic perturbations of cellular automata belonging to the category of monotonic binary tessellations and possessing a property of erosion. We prove, for a set of initial conditions, exponential convergence of the induced processes toward an extremal invariant measure with a highly predominant spin value. We also show that this invariant measure presents exponential decay of correlations in space and in time and is therefore strongly mixing. [ABSTRACT FROM AUTHOR]

We consider 3D active plane rotators, where the interaction between the spins is of XY-type and where each spin is driven to rotate. For the clock-model, when the spins take N≫1 possible values, we conjecture that there are two low-temperature regimes. At very low temperatures and for small enough drift the phase diagram is a small perturbation of the equilibrium case. At larger temperatures the massless modes appear and the spins start to rotate synchronously for arbitrary small drift. For the driven XY-model we prove that there is essentially a unique translation-invariant and stationary distribution despite the fact that the dynamics is not ergodic. [ABSTRACT FROM AUTHOR]

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., , doi:). In this paper, we study one-dimensional linear cellular automata with periodic boundary conditions over any finite field ℤ. 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 ℤ) 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 ℤ. [ABSTRACT FROM AUTHOR]

In the Exactly 1 cellular automaton (also known as Rule 22), every site of the one-dimensional lattice is either in state 0 or in state 1, and a synchronous update rule dictates that a site is in state 1 next time if and only if it sees a single 1 in its three-site neighborhood at the current time. We analyze this rule started from finite seeds, i.e., those initial configurations that have only finitely many 1's. Three qualitatively different types of evolution are observed: replication, periodicity, and chaos. We focus on rigorous results, assisted by algorithmic searches, for the first two behaviors. In particular, we explain why replication is observed so frequently and present a method for collecting the smallest periodic seeds. Some empirical observations about chaotic seeds are also presented. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. Previous studies have shown that there exists several exactly renormalizable deterministic automata. We show that the RG fixed points for such self-similar CA are unstable in all directions under renormalization. This implies that the large scale structure of self-similar deterministic elementary cellular automata is destroyed by any finite error probability. As a second result we show that the only non-trivial critical PCA are the different versions of the well-studied phenomenon of directed percolation. We discuss how the second result supports a conjecture regarding the universality class for dynamic criticality defined by directed percolation. [ABSTRACT FROM AUTHOR]

The flip-annihilation process is a random particle process with one-dimensional local interaction in discrete time, initially presented by one of us, namely Toom in 2004. Its components are enumerated by integer numbers and every component has two states, “minus” and “plus”. At every time step two transformations occur. The first one, called “flip”, independently turns every minus into plus with probability β. The second one, called “annihilation”, acts thus: whenever a plus is a left neighbor of a minus, both disappear with probability α independently from other components. What is interesting about this process is that it is ergodic for β> α/2 and non-ergodic for β< α 2/250. It is natural to conjecture that there is some transition curve, which we call the true curve and denote by $\beta =\mathsf{true}(\alpha)$ , which separates the areas of ergodicity and non-ergodicity of this process from each other. The estimates, mentioned above, albeit rigorous, leave a large gap between them and the present article’s purpose is to obtain some closer, albeit non-rigorous, approximations of the true curve. We do it in two ways, one of which is a chaos approximation and the other is a Monte Carlo simulation. Thus we obtain two curves, which are much closer to each other than the rigorous estimations. Also we fill in, albeit only numerically, another shortcoming of the rigorous estimation β< α 2/250, namely that it leaves us uncertain whether the true curve has a zero or positive slope at the point α= β=0. Both approximate curves have a positive slope at α=0, as we hoped. [ABSTRACT FROM AUTHOR]

The problem of metastability for a stochastic dynamics with a parallel updating rule is addressed in the Freidlin–Wentzel regime, namely, finite volume, small magnetic field, and small temperature. The model is characterized by the existence of many fixed points and cyclic pairs of the zero temperature dynamics, in which the system can be trapped in its way to the stable phase. Our strategy is based on recent powerful approaches, not needing a complete description of the fixed points of the dynamics, but relying on few model dependent results. We compute the exit time, in the sense of logarithmic equivalence, and characterize the critical droplet that is necessarily visited by the system during its excursion from the metastable to the stable state. We need to supply two model dependent inputs: (1) the communication energy, that is the minimal energy barrier that the system must overcome to reach the stable state starting from the metastable one; (2) a recurrence property stating that for any configuration different from the metastable state there exists a path, starting from such a configuration and reaching a lower energy state, such that its maximal energy is lower than the communication energy. [ABSTRACT FROM AUTHOR]

We introduce a new class of two-dimensional cellular automata with a bootstrap percolation-like dynamics. Each site can be either empty or occupied by a single particle and the dynamics follows a deterministic updating rule at discrete times which allows only emptying sites. We prove that the threshold density ρ c for convergence to a completely empty configuration is non trivial, 0< ρ c <1, contrary to standard bootstrap percolation. Furthermore we prove that in the subcritical regime, ρ< ρ c , emptying always occurs exponentially fast and that ρ c coincides with the critical density for two-dimensional oriented site percolation on ℤ2. This is known to occur also for some cellular automata with oriented rules for which the transition is continuous in the value of the asymptotic density and the crossover length determining finite size effects diverges as a power law when the critical density is approached from below. Instead for our model we prove that the transition is discontinuous and at the same time the crossover length diverges faster than any power law. The proofs of the discontinuity and the lower bound on the crossover length use a conjecture on the critical behaviour for oriented percolation. The latter is supported by several numerical simulations and by analytical (though non rigorous) works through renormalization techniques. Finally, we will discuss why, due to the peculiar mixed critical/first order character of this transition, the model is particularly relevant to study glassy and jamming transitions. Indeed, we will show that it leads to a dynamical glass transition for a Kinetically Constrained Spin Model. Most of the results that we present are the rigorous proofs of physical arguments developed in a joint work with D.S. Fisher. [ABSTRACT FROM AUTHOR]

The spin-1 Ising model with the nearest-neighbour bilinear and biquadratic interactions and single-ion anisotropy is simulated on a cellular automaton which improved from the Creutz cellular automaton (CCA) for a simple cubic lattice. The simulations have been made for several k= K/ J and d= D/ J in the 0≤ d<3 and −2≤ k≤0 parameter regions. We confirm the existence of the re-entrant and the successive re-entrant phase transitions near the phase boundary. The phase diagrams characterizing phase transitions are presented for comparison with those obtained from other calculations. The static critical exponents are estimated within the framework of the finite-size scaling theory at d=0, 1 and 2 in the interval −2≤ k≤0. The results are compatible with the universal Ising critical behavior. [ABSTRACT FROM AUTHOR]

In this note we analyse an anisotropic, two-dimensional bootstrap percolation model introduced by Gravner and Griffeath. We present upper and lower bounds on the finite-size effects. We discuss the similarities with the semi-oriented model introduced by Duarte. [ABSTRACT FROM AUTHOR]

We study spontaneous symmetry breaking in a one-dimensional driven two-species stochastic cellular automaton with parallel sublattice update and open boundaries. The dynamics are symmetric with respect to interchange of particles. Starting from an empty initial lattice, the system enters a symmetry broken state after some time T 1 through an amplification loop of initial fluctuations. It remains in the symmetry broken state for a time T 2 through a traffic jam effect. Applying a simple martingale argument, we obtain rigorous asymptotic estimates for the expected times 〈 T 1〉 ∝ Lln L and ln 〈 T 2〉 ∝ L, where L is the system size. The actual value of T 1 depends strongly on the initial fluctuation in the amplification loop. Numerical simulations suggest that T 2 is exponentially distributed with a mean that grows exponentially in system size. For the phase transition line we argue and confirm by simulations that the flipping time between sign changes of the difference of particle numbers approaches an algebraic distribution as the system size tends to infinity. [ABSTRACT FROM AUTHOR]

Myxobacteria exhibit a complex life cycle characterized by a sequence of cell patterns that culminate in the formation of three-dimensional fruiting bodies. This paper provides indications that the specific cell shape of myxobacteria might play an important role in the different morphogenetic processes during the life cycle. We introduce a new mechanism for collective migration that can explain the formation of aligned cell clusters in myxobacteria. This mechanism does not depend on cell cooperation, and in particular it does not depend on diffusive signals guiding cell motion. A Cellular Potts Model (CPM) that captures the rod cell shape, cell stiffness and active motion of myxobacteria is presented. By means of numerical simulations of model cell populations where cells interact via volume exclusion, we provide evidence of a purely mechanical mechanism for collective migration, which is controlled by the cells' length-to-width aspect ratio. [ABSTRACT FROM AUTHOR]

Space-time directional Lyapunov exponents are introduced. They describe the maximal velocity of propagation to the right or to the left of fronts of perturbations in a frame moving with a given velocity. The continuity of these exponents as function of the velocity and an inequality relating them to the directional entropy is proved. [ABSTRACT FROM AUTHOR]

We present the Bethe ansatz solution for the discrete time zero range and asymmetric exclusion processes with fully parallel dynamics. The model depends on two parameters: p, the probability of single particle hopping, and q, the deformation parameter, which in the general case, | q| < 1, is responsible for long range interaction between particles. The particular case q = 0 corresponds to the Nagel-Schreckenberg traffic model with v max = 1. As a result, we obtain the largest eigenvalue of the equation for the generating function of the distance travelled by particles. For the case q = 0 the result is obtained for arbitrary size of the lattice and number of particles. In the general case we study the model in the scaling limit and obtain the universal form specific for the Kardar-Parisi-Zhang universality class. We describe the phase transition occurring in the limit p→ 1 when q < 0. [ABSTRACT FROM AUTHOR]

Two fundamental models of critical phenomena are connected. We show that the discrete Bak–Sneppen evolution model is conjugate to the classical contact process. This holds in discrete and continuous time, on all graphs and for random as well as for deterministic choice of neighbors. Thus the extensive theory for the contact process applies to the discrete Bak–Sneppen model, too. [ABSTRACT FROM AUTHOR]

Our results concern long time limit properties of a deterministic dynamics that is common for a wide class of processes that have been studied so far during at least last two decades. The most widely known process from this class is a cellular automaton that acquired number 184 in the classification of S. Wolfram. This CA 184 is being intensively used to model vehicular traffic. However, our results are mainly derived with help of another process that offers a helpful insight into the studied dynamics, it is a so-called Ballistic Annihilation Model (abbreviated by BA). BA is a model for chemical reaction A+B ? inert. In BA, A and B-type particles move in opposite directions with velocities 1 and -1, respectively, and annihilate upon collisions. Certain results concerning BA and CA 184 are also formulated in terms of another process known as a Model of Surface Growth (SG, for short); the surface shape in this process behaves as the integrated profile of particle distribution in CA 184. Our results are as follows. First, we characterize the invariant measures of the dynamics in interest. The bulk of our effort is devoted to the characterization of those of them that are not translation invariant; we call them phase separating invariant measures. In the case of BA, such measures are concentrated on the configurations consisting of two converging infinite blocks of (not necessarily adjacent) particles. In the case of CA 184, a phase separating measure describes the transition from free traffic phase to jammed phase. We also analyze domains of attraction of invariant measures and rates of convergence to them. This analysis then allows us to express the long time limit of particle current in CA 184 as a function of certain characteristics of its initial distribution, when it is translation invariant. This expression has been used in a companion paper (V. Belitsky, J. Krug, E. J. Neves and G. Schütz, A cellular automaton model for two-lane traffic, J. Stat. phys.103(5/6):945--971 (2001)) to show the enhancement of cars’ current caused by the possibility of lane changes in a model of traffic on a two-lane highway that was created by putting two CA 184’s in parallel. Our other results concern hydrodynamic limits of BA and CA 184. We prove that if the integrated profile of initial particle configuration of BA or CA 184 converges, as n ? 8, to some stochastic processW(x), x =, when being re-scaled byn-1 alongx-axis and byc n-1 alongy-axis for some sequencec n, then the integrated profile of particle configuration at timenunder the same re-scaling, will converge, as time? 8, to the local moving minimum of the processW(·), that is, to the processWmin(·) defined byWmin(x):=min{W(y) :x-1= y=x+1}. This hydrodynamic limit is then interpreted in terms of the limiting shape of surface in SG. [ABSTRACT FROM AUTHOR]

It is suggested that the question of existence of a jamming phase transition in a broad class of single-lane cellular-automaton traffic models may be studied using a correspondence to the asymmetric chipping model. In models where such correspondence is applicable, jamming phase transition does not take place. Rather, the system exhibits a smooth crossover between free-flow and jammed states, as the car density is increased. [ABSTRACT FROM AUTHOR]

We obtain an upper large deviations bound which shows that for some models of probabilistic cellular automata (which are far away from the product case) the lower large deviation bound derived in Eizenberg and Kifer J. Stat. Phys. 108: 1255–1280 (2002) is sharp, and so the corresponding large deviations phenomena cannot be described via the traditional Donsker–Varadhan form of the action functional. For models which are close to the product case we derive approximate large deviations bounds using the Donsker–Varadhan functional for the product case. [ABSTRACT FROM AUTHOR]

We discuss similarities and differences between systems of interacting players maximizing their individual payoffs and particles minimizing their interaction energy. Long-run behavior of stochastic dynamics of spatial games with multiple Nash equilibria is analyzed. In particular, we construct an example of a spatial game with three strategies, where stochastic stability of Nash equilibria depends on the number of players and the kind of dynamics. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We consider a prominent feature of hierarchical nonlinear (“complex”) systems: persistent recurrence of abrupt overall changes, called here “critical transitions.” Motivated by the earthquake prediction problem, we formulate a model that uses heuristic constraints taken from the dynamics of seismicity. Our conclusions, though, may apply to hierarchical systems that arise in other areas. We use the Boolean delay equation (BDE) framework to model the dynamics of colliding cascades, in which a direct cascade of loading interacts with an inverse cascade of failures. The elementary interactions of elements in the system are replaced by their integral effect, represented by the delayed switching of an element's state. The present paper is the first of two on the BDE approach to modeling seismicity. Its major results are the following: (i) A model that implements the approach. (ii) Simulating three basic types of seismic regime. (iii) A study of regime switching in a parameter space of the loading and healing rates. The second paper focuses on the earthquake prediction problem. [ABSTRACT FROM AUTHOR]

We consider here prediction of abrupt overall changes (“critical transitions”) in the behavior of hierarchical complex systems, using the model developed in the first part of this study. The model merges the physical concept of colliding cascades with the mathematical framework of Boolean delay equations. It describes critical transitions that are due to the interaction between direct cascades of loading and inverse cascades of failures in a hierarchical system. This interaction is controlled by distinct delays between switching of elements from one state to another: loaded vs. unloaded and intact vs. failed. We focus on the earthquake prediction problem; accordingly, the model's heuristic constraints are taken from the dynamics of seismicity. The model exhibits four major types of premonitory seismicity patterns (PSPs), which have been previously identified in seismic observations: (i) rise of earthquake clustering; (ii) rise of the earthquakes' intensity; (iii) rise of the earthquake correlation range; and (iv) certain changes in the size distribution of earthquakes (Gutenberg–Richter relation). The model exhibits new features of individual PSPs and their collective behavior, to be tested in turn on observations. There are indications that the premonitory phenomena considered are not seismicity-specific, but may be common to hierarchical systems of a more general nature. [ABSTRACT FROM AUTHOR]

If $\{\backslash Bbb\; M\}=\{\backslash Bbb\; Z\}^D$, and $\{\backslash cal\; B\}$ is a finite (nonabelian) group, then $\{\backslash cal\; B\}^\{\{\backslash Bbb\; M\}\}$ is a compact group; a multiplicative cellular automaton (MCA) is a continuous transformation which commutes with all shift maps, and where nearby coordinates are combined using the multiplication operation of $\{\backslash cal\; B\}$. We characterize when MCA are group endomorphisms of $\{\backslash cal\; B\}^\{\{\backslash Bbb\; M\}\}$, and show that MCA on $\{\backslash cal\; B\}^\{\{\backslash Bbb\; M\}\}$ inherit a natural structure theory from the structure of $\{\backslash cal\; B\}$. We apply this structure theory to compute the measurable entropy of MCA, and to study convergence of initial measures to Haar measure. [ABSTRACT FROM AUTHOR]

We consider supercritical vertex percolation in $$\mathbb{Z}^d $$ d with any non-degenerate uniform oriented pattern of connection. In particular, our results apply to the more special unoriented case. We estimate the probability that a large region is isolated from ∞. In particular, “pancakes” with a radius r→∞ and constant thickness, parallel to a constant linear subspace L, are isolated with probability, whose logarithm grows asymptotically as ≍ rdim( L) if percolation is possible across L and as ≍ rdim( L)−1 otherwise. Also we estimate probabilities of large deviations in invariant measures of some cellular automata. [ABSTRACT FROM AUTHOR]

We consider a generalized model of a probabilistic cellular automata described by a Markov chain on an infinite dimensional space and derive certain large deviations bounds for corresponding occupational measures. [ABSTRACT FROM AUTHOR]

We consider the quasi-deterministic behavior of systems with a large number, n, of deterministically interacting constituents. This work extends the results of a previous paper [ J. Statist. Phys. 99:1225–1249 (2000)] to include vector-valued observables on interacting systems. The approach used here, however, differs markedly in that a level-1 large deviation principle (LDP) on joint observables, rather than a level-2 LDP on empirical distributions, is employed. As before, we seek a mapping ψ t on the set of (possibly vector-valued) macrostates such that, when the macrostate is given to be a0 at time zero, the macrostate at time t is ψ t( a0) with a probability approaching one as n tends to infinity. We show that such a map exists and derives from a generalized dynamic free energy function, provided the latter is everywhere well defined, finite, and differentiable. We discuss some general properties of ψ t relevant to issues of irreversibility and end with an example of a simple interacting lattice, for which an exact macroscopic solution is obtained. [ABSTRACT FROM AUTHOR]

In this paper we study a criterion of self-duality for multi-state probabilistic cellular automata with finite range interactions and give some models which satisfy this criterion. [ABSTRACT FROM AUTHOR]

In this paper we study dualities for a class of one-dimensional probabilistic cellular automata with finite range interactions by using a sequence of extended cellular automata. [ABSTRACT FROM AUTHOR]

We present some long time limit properties of a cellular automaton that models traffic of cars on a (infinite) two-lane road. This model, called TL184, is a natural generalization of the cellular automaton classified as 184 by Wolfram (to be abbreviated by CA184) and studied before as a model for one-lane traffic. TL184 models cars' motions on each lane by particles that interact via the CA184 rules, and cars' lane changes by a possibility for particles to flip from one CA184 to another. We calculate the infinite-time limit of the particle current in TL184, starting from a translation invariant measure, and use this result to show how the possibility of lane changes may enhance the current of cars in TL184 compared to that in a corresponding model of two non-interacting one-lane roads. We provide examples which demonstrate that even though the rules that regulate lane changes are completely symmetric, the system does not evolve to an equipartition of cars among both lanes from a given initially asymmetric distribution; moreover, the asymptotic car velocities and currents may be different on different lanes. We also show that, for a particular class of initial distributions, the asymptotic car density on a lane may be a non-monotonic function of the initial car density on this lane. Finally, we derive the current-density relation for an extended continuous-time version of TL184 with asymmetric lane-changing rules. [ABSTRACT FROM AUTHOR]