Stability of cellular automata trajectories revisited: branching walks and Lyapunov profiles
arXiv:1406.5553
Abstract
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 analogue of Floquet theory for cellular automata.
40 pages, 13 figures
References in corpus (8)
- Cellular automata and Lyapunov exponents
- Space-time directional Lyapunov exponents for cellular automata
- Computation and Universality: Class IV versus Class III Cellular Automata
- Control of cellular automata
- Random growth models with polygonal shapes
- Always Finite Entropy and Lyapunov exponents of two-dimensional cellular automata
- Percolation and disorder-resistance in cellular automata
- Introducing Lyapunov profiles of cellular automata