Characterizing asymptotic randomization in abelian cellular automata

DOI10.1017/ETDS.2018.75zbMATH Open1441.37017arXiv1703.07289OpenAlexW2604456370WikidataQ129245977 ScholiaQ129245977MaRDI QIDQ5220080FDOQ5220080

Ville Salo, Benjamin Hellouin de Menibus, Guillaume Theyssier

Publication date: 10 March 2020

Published in: Ergodic Theory and Dynamical Systems (Search for Journal in Brave)

Abstract: Abelian cellular automata (CA) are CA which are group endomorphisms of the full group shift when endowing the alphabet with an abelian group structure. A CA randomizes an initial probability measure if its iterated images weak *-converge towards the uniform Bernoulli measure (the Haar measure in this setting). We are interested in structural phenomena, i.e. randomization for a wide class of initial measures (under some mixing hypotheses). First, we prove that an abelian CA randomizes in Ces{`a}ro mean if and only if it has no soliton, i.e. a finite configuration whose time evolution remains bounded in space. This characterization generalizes previously known sufficient conditions for abelian CA with scalar or commuting coefficients. Second, we exhibit examples of strong randomizers, i.e. abelian CA randomizing in simple convergence; this is the first proof of this behaviour to our knowledge. We show however that no CA with commuting coefficients can be strongly randomizing. Finally, we show that some abelian CA achieve partial randomization without being randomizing: the distribution of short finite words tends to the uniform distribution up to some threshold, but this convergence fails for larger words. Again this phenomenon cannot happen for abelian CA with commuting coefficients.

Full work available at URL: https://arxiv.org/abs/1703.07289

Recommendations

• Asymptotic randomization of sofic shifts by linear cellular automata
• Propagation, diffusion and randomization in cellular automata
• Characterization of sets of limit measures of a cellular automaton iterated on a random configuration
• Asymptotic randomization of subgroup shifts by linear cellular automata
• Characterisation of limit measures of higher-dimensional cellular automata

zbMATH Keywords

cellular automataergodic theorysymbolic dynamics

Mathematics Subject Classification ID

Dynamical aspects of measure-preserving transformations (37A05) Dynamical aspects of statistical mechanics (37A60) Symbolic dynamics (37B10) Dynamical aspects of cellular automata (37B15)

Cites Work

• Endomorphisms and automorphisms of the shift dynamical system
• Title not available (Why is that?)
• Limit measures for affine cellular automata
• \(\mu\)-limit sets of cellular automata from a computational complexity perspective
• Statistical mechanics of surjective cellular automata
• Directional dynamics for cellular automata: A sensitivity to initial condition approach
• Investigating topological chaos by elementary cellular automata dynamics
• Cellular Automata and Groups
• On time-symmetry in cellular automata
• Cesàro mean distribution of group automata starting from measures with summable decay
• Probability distributions on locally compact Abelian groups
• Uniform Bernoulli measure in dynamics of permutative cellular automata with algebraic local rules
• Construction of mu-Limit Sets of Two-dimensional Cellular Automata
• Directional dynamics along arbitrary curves in cellular automata
• A first course in harmonic analysis
• An equilibrium state for a one-dimensional life game
• Title not available (Why is that?)
• Statistical Equilibrium in Deterministic Cellular Automata
• Limit measures for affine cellular automata II
• Asymptotic randomization of sofic shifts by linear cellular automata
• Asymptotic randomization of subgroup shifts by linear cellular automata
• Right-permutative cellular automata on topological Markov chains
• Characterization of sets of limit measures of a cellular automaton iterated on a random configuration
• Commutators of Bipermutive and Affine Cellular Automata
• Pre-expansivity in cellular automata

Cited In (6)

• Cold dynamics in cellular automata: a tutorial
• Dynamical behavior of additive cellular automata over finite abelian groups
• Pre-expansivity in cellular automata
• Asymptotic randomization of sofic shifts by linear cellular automata
• Ergodicity of some classes of cellular automata subject to noise
• Cutting corners

This page was built for publication: Characterizing asymptotic randomization in abelian cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5220080)