Cluster growth in particle-conserving cellular automata

A class of simple two-dimensional cellular automata with particle conservation is proposed for easy simulations of interacting particle systems. The automata are defined by the exchange of states of neighboring cells, depending on the configurations around the cells. By attributing an energy to a configuration of cells, we can select significant rules from the huge number of possible rules and classify them into several groups, based on the analogy with a binary alloy. By numerical calculations, cluster growth is found in two kinds of phases which reveal gas-solid coexistence and liquid droplets. Normalized scaling functions are obtained, and dynamical scaling is examined.     

On irreversibility of von Neumann additive cellular automata on grids

The von Neumann cellular automaton appears in many different settings in Operations Research varying from applications in Formal Languages to Biology. One of the major questions related to it is to find a general condition for irreversibility of a class of two-dimensional cellular automata on square grids (σ⁺-automata). This question is partially answered here with the proposal of a sufficient condition for the irreversibility of σ⁺-automata.     

Rigidity of Branch Groups Acting on Rooted Trees

Automorphisms of groups acting faithfully on rooted trees are studied. We find conditions under which every automorphism of such a group is induced by a conjugation from the full automorphism group of the rooted tree. These results are applied to known examples such as Grigorchuk groups, Gupta–Sidki group, etc.     

大电流监测信号提取的光收发及信号处理

近年来,大电流的监测成了人们十分关心的问题,这是由于大电流有强磁、高压、电流大等一系列的直接监测所不能克服的问题。这就需要把高压大电流的强电信号,经过提取后变成能在实验室中直接观测的弱电信号。为此,如何从高压大电流的信号中提取出随实时信号变化而实时变化的小信号就变成了一个关键问题。详细介绍了监测信号提取的光收发电路原理和后续信号处理电路,分析了各部分的作用,给出了必要的分析结果。     

An efficient hydrodynamic cellular automata for simulating fluids with large viscosities

A hydrodynamic cellular automata (HDCA) for simulating two-dimensional fluids with large viscosities is proposed. The model is characterized by a mean free path which is of the same size as in the FHP-II model, but with a viscosity more than 10 times larger. This new model should make simulations of flows at low Reynolds number more efficient.     

Complex genetic evolution of artificial self‐replicators in cellular automata

It is widely believed that evolutionary dynamics of artificial self‐replicators realized in cellular automata (CA) are limited in diversity and adaptation. Contrary to this view, we show that complex genetic evolution may occur within simple CA. The evolving self‐replicating loops (“evoloops”) we investigate exhibit significant diversity in macro‐scale morphologies and mutational biases, undergoing nontrivial genetic adaptation by maximizing colony density and enhancing sustainability against other species. Nonmutable subsequences enable genetic operations that alter fitness differentials and promote long‐term evolutionary exploration. These results demonstrate a unique example of genetic evolution hierarchically emerging from local interactions between elements much smaller than individual replicators. © 2004 Wiley Periodicals, Inc. Complexity 10: 33–39, 2004     

A transport model for the evolution of urban systems

When comparing an urban system to an elasto-plastic lattice, an analogy to the solid state of matter can be exploited using the concepts of the band theory similarly. Thereafter, the population dynamics – in a region of certain stability in the state space and within appropriate energy bands – can be described in terms of Cellular Automata, with two mobile agents or pseudo particles: the inhabitant (representative of an average individual) and the recurson (representative of its multidimensional resources). As in the solid state, transition rules take the form of two coupled transport equations, comprising the terms equivalent to the generation-recombination and circulation processes. The first process can be compared to a predator–prey growth model, typical of Ecology; whereas the circulation process – composed of a drift component and a diffusion component – should be compared to the concentration-sprawl demographic balance seen in urban occupation and dynamics. Thus, it needs to be defined and determined an urban potential function, an equivalent population charge, mobility and diffusion parameters, as well as net growth factors. This analogy, discussed within the context of a case study for Great Mendoza, plausibly explains the varied growth rates of the political departments, as well as the principal urban trends for spatial occupation.     

Finite turns and the regular closure of linear context-free languages

Turn bounded pushdown automata with different conditions for beginning a new turn are investigated. Their relationships with closures of the linear context-free languages under regular operations are studied. For example, automata with an unbounded number of turns that have to empty their pushdown store up to the initial symbol in order to start a new turn are characterized by the regular closure of the linear languages. Automata that additionally have to re-enter the initial state are (almost) characterized by the Kleene star closure of the linear languages. For both a bounded and an unbounded number of turns, requiring to empty the pushdown store is a strictly stronger condition than requiring to re-enter the initial state. Several new language families are obtained which form a double-stranded hierarchy. Closure properties of these families under AFL operations are derived. The regular closure of the linear languages share the strong closure properties of the context-free languages, i.e., the family is a full AFL. Interestingly, three natural new language families are not closed under intersection with regular languages and inverse homomorphism. Finally, an algorithm is presented parsing languages from the new families in quadratic time.     

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.     

Algebraic spatial correlations in lattice gas automata violating detailed balance

In this paper we discuss the existence of generic long-range correlations in spatially homogeneous and stable equilibrium states of closed lattice gas automata whose stochastic collision rules violate the symmetry conditions of detailed balance and in addition satisfy local conservation laws. Such correlations occur even though the collision rules are strictly local and invariant under all symmetries of the lattice. First a phenomenological (Langevin equation) approach is discussed. Next we present a theoretical analysis on the basis of an approximate microscopic (ring kinetic) theory. This theory is used to calculate the amplitude ofr ^– tails in the spatial correlations, and the result is compared with computer simulations.