Walks in Rigid Environments: Continuous Limits

We derive the continuous limits of kinetic equations for spatially discrete systems generated by the motion of a particle in a random array of scatterers. The type of scatterer at a vertex changes after the r-th visit of the particle to this vertex, where 1r. Such deterministic cellular automata belong to the class of walks in rigid environments. It has been recently shown that they form the simplest dynamical models with sub-diffusive, diffusive and super-diffusive behaviour. Due to the deterministic character of the dynamics, the continuous limit equations obtained for these models are of the Euler type rather than the diffusive type. The reason for that is that the fluctuations in these models are relatively small and there is no scaling of probabilities similar, for example, to those in the case of biased random walk, that can account for them.     

Non-Markovian decoherent quantum walks

Quantum walks act in obviously different ways from their classical counterparts, but decoherence will lessen and close this gap between them. To understand this process, it is necessary to investigate the evolution of quantum walks under different decoherence situations. In this article, we study a non-Markovian decoherent quantum walk on a line. In a short time regime, the behavior of the walk deviates from both ideal quantum walks and classical random walks. The position variance as a measure of the quantum walk collapses and revives for a short time, and tends to have a linear relation with time. That is, the walker's behavior shows a diffusive spread over a long time limit, which is caused by non-Markovian dephasing affecting the quantum correlations between the quantum walker and his coin. We also study both quantum discord and measurement-induced disturbance as measures of the quantum correlations, and observe both collapse and revival in the short time regime, and the tendency to be zero in the long time limit. Therefore, quantum walks with non-Markovian decoherence tend to have diffusive spreading behavior over long time limits, while in the short time regime they oscillate between ballistic and diffusive spreading behavior, and the quantum correlation collapses and revives due to the memory effect.     

Quantum Walks,Weyl Equation and the Lorentz Group

Quantum cellular automata and quantum walks provide a framework for the foundations of quantum field theory, since the equations of motion of free relativistic quantum fields can be derived as the small wave-vector limit of quantum automata and walks starting from very general principles. The intrinsic discreteness of this framework is reconciled with the continuous Lorentz symmetry by reformulating the notion of inertial reference frame in terms of the constants of motion of the quantum walk dynamics. In particular, among the symmetries of the quantum walk which recovers the Weyl equation—the so called Weyl walk—one finds a non linear realisation of the Poincaré group, which recovers the usual linear representation in the small wave-vector limit. In this paper we characterise the full symmetry group of the Weyl walk which is shown to be a non linear realization of a group which is the semidirect product of the Poincaré group and the group of dilations.     

A study on correlated exponential random walks

Based on the linear Boltzmann transport formulation, we investigate the statistics of correlated exponential random walks that are continuous in space and discrete in time. We show that asymptotically, the correlated random walk process is diffusive and derive an effective diffusion constant. We investigate the power spectral characteristics of the associated random forces. We also present some results on the first passage time distribution and establish that asymptotically it reduces to that associated with simple Gaussian walks.     

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

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

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

Universality class of nonequilibrium phase transitions with infinitely many absorbing states

We consider systems whose steady states exhibit a nonequilibrium phase transition from an active state to one-among an infinite number-absorbing state, as some control parameter is varied across a threshold value. The pair contact process, stochastic fixed-energy sandpiles, activated random walks, and many other cellular automata or reaction-diffusion processes are covered by our analysis. We argue that the upper-critical dimension below which anomalous fluctuation driven scaling appears is d(c)=6, in contrast to a widespread belief. We provide the exponents governing the critical behavior close to or at the transition point to first order in an epsilon =6-d expansion.     

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.     

Random Walks in Space Time Mixing Environments

We prove that random walks in random environments, that are exponentially mixing in space and time, are almost surely diffusive, in the sense that their scaling limit is given by the Wiener measure.     

Continuity of Information Transport in Surjective Cellular Automata

We introduce a local version of the Shannon entropy in order to describe information transport in spatially extended dynamical systems, and to explore to what extent information can be viewed as a local quantity. Using an appropriately defined information current, this quantity is shown to obey a local conservation law in the case of one-dimensional reversible cellular automata with arbitrary initial measures. The result is also shown to apply to one-dimensional surjective cellular automata in the case of shift-invariant measures. Bounds on the information flow are also shown.     

Reversibility Problem of Multidimensional Finite Cellular Automata

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.     

Two-dimensional cellular automata

A largely phenomenological study of two-dimensional cellular automata is reported. Qualitative classes of behavior similar to those in one-dimensional cellular automata are found. Growth from simple seeds in two-dimensiona! cellular automata can produce patterns with complicated boundaries, characterized by a variety of growth dimensions. Evolution from disordered states can give domains with boundaries that execute effectively continuous motions. Some global properties of cellular automata can be described by entropies and Lyapunov exponents. Others are undecidable.This work was supported in part by the U.S. Office of Naval Research under Contract No. N00014-80-C-0657.     

Infinite Ergodic Walks in Finite Connected Undirected Graphs

The micro-canonical, canonical, and grand canonical ensembles of walks defined in finite connected undirected graphs are considered in the thermodynamic limit of infinite walk length. As infinitely long paths are extremely sensitive to structural irregularities and defects, their properties are used to describe the degree of structural imbalance, anisotropy, and navigability in finite graphs. For the first time, we introduce entropic force and pressure describing the effect of graph defects on mobility patterns associated with the very long walks in finite graphs; navigation in graphs and navigability to the nodes by the different types of ergodic walks; as well as node’s fugacity in the course of prospective network expansion or shrinking.     

A random walk on a random channel with absorbing barriers

We consider random walks on one-dimensional random channels between two absorbing barriers. The problem can perhaps be used to model the diffusion of a molecule in a “random” membrane, the molecule traversing a random channel formed by the constituent membrane molecules. We are able to analytically follow the transition from diffusive to non-diffusive behavior as the minimum number of channel segments required to traverse the membrane increases.     

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.     

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.     

Stationary states and hydrodynamics of FHP cellular automata

The large scale behavior of FHP-type cellular automata is investigated in the presence of some additional random effects. It is shown that every translationinvariant stationary state of the modified model is a superposition of product measures. By means of the entropy argument of Yau and of Olla, Varadhan, and Yau, the macroscopic (Euler-type) equations governing the hydrodynamic behavior of FHP automata are also derived.Dedicated to Oliver Penrose on the occasion of his 65th birthday.