Invariant measures for bipermutative cellular automata

Previous Article
A saddle point theorem for functional state-dependent delay differential equations
DCDS Home
This Issue
Next Article
Multiple sign-changing solutions of an elliptic eigenvalue problem

July 2005, 12(4): 723-736. doi: 10.3934/dcds.2005.12.723

Invariant measures for bipermutative cellular automata

1.	Department of Mathematics, Trent University, Peterborough, Ontario, K9L 1Z8, Canada

Received June 2003 Revised December 2004 Published January 2005

Abstract
Related Papers

A right-sided, nearest neighbour cellular automaton (RNNCA) is a continuous transformation $\Phi:\mathcal A^{\mathbb Z} \rightarrow\mathcal A^{\mathbb Z}$ determined by a local rule $\phi:\mathcal A^{\{0,1\}}\rightarrow\mathcal A$ so that, for any $\mathbf a\in\mathcal A^{\mathbb Z}$ and any $z\in\mathbb Z$, $\Phi(\mathbf a)_z = \phi(a_z,a_{z+1})$. We say that $\Phi$ is bipermutative if, for any choice of $a\in\mathcal A$, the map $\mathcal A\ni b \mapsto \phi(a,b)\in\mathcal A$ is bijective, and also, for any choice of $b\in\mathcal A$, the map $\mathcal A\ni a \mapsto \phi(a,b)\in\mathcal A$ is bijective.
We characterize the invariant measures of bipermutative RNNCA. First we introduce the equivalent notion of a quasigroup CA. Then we characterize $\Phi$-invariant measures when $\mathcal A$ is a (nonabelian) group, and $\phi(a,b) = a\cdot b$. Then we show that, if $\Phi$ is any bipermutative RNNCA, and $\mu$ is $\Phi$-invariant, then $\Phi$ must be $\mu$-almost everywhere $K$-to-1, for some constant $K$. We then characterize invariant measures when $\mathcal \mathcal A^{\mathbb Z}$ is a group shift and $\Phi$ is an endomorphic CA.

Keywords: endomorphism, quasigroup, permutative, Cellular automata, Latin square, group shift., invariant measure.

Mathematics Subject Classification: Primary: 37B15; Secondary: 37A5.

Citation: Marcus Pivato. Invariant measures for bipermutative cellular automata. Discrete & Continuous Dynamical Systems - A, 2005, 12 (4) : 723-736. doi: 10.3934/dcds.2005.12.723

[1]	Bernard Host, Alejandro Maass, Servet Martínez. Uniform Bernoulli measure in dynamics of permutative cellular automata with algebraic local rules. Discrete & Continuous Dynamical Systems - A, 2003, 9 (6) : 1423-1446. doi: 10.3934/dcds.2003.9.1423
[2]	Marcelo Sobottka. Right-permutative cellular automata on topological Markov chains. Discrete & Continuous Dynamical Systems - A, 2008, 20 (4) : 1095-1109. doi: 10.3934/dcds.2008.20.1095
[3]	T.K. Subrahmonian Moothathu. Homogeneity of surjective cellular automata. Discrete & Continuous Dynamical Systems - A, 2005, 13 (1) : 195-202. doi: 10.3934/dcds.2005.13.195
[4]	Achilles Beros, Monique Chyba, Oleksandr Markovichenko. Controlled cellular automata. Networks & Heterogeneous Media, 2019, 14 (1) : 1-22. doi: 10.3934/nhm.2019001
[5]	Van Cyr, John Franks, Bryna Kra, Samuel Petite. Distortion and the automorphism group of a shift. Journal of Modern Dynamics, 2018, 13: 147-161. doi: 10.3934/jmd.2018015
[6]	Achilles Beros, Monique Chyba, Kari Noe. Co-evolving cellular automata for morphogenesis. Discrete & Continuous Dynamical Systems - B, 2019, 24 (5) : 2053-2071. doi: 10.3934/dcdsb.2019084
[7]	Petr Kůrka. On the measure attractor of a cellular automaton. Conference Publications, 2005, 2005 (Special) : 524-535. doi: 10.3934/proc.2005.2005.524
[8]	Xinxin Tan, Shujuan Li, Sisi Liu, Zhiwei Zhao, Lisa Huang, Jiatai Gang. Dynamic simulation of a SEIQR-V epidemic model based on cellular automata. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 327-337. doi: 10.3934/naco.2015.5.327
[9]	Van Cyr, Bryna Kra. The automorphism group of a minimal shift of stretched exponential growth. Journal of Modern Dynamics, 2016, 10: 483-495. doi: 10.3934/jmd.2016.10.483
[10]	Mike Boyle, Sompong Chuysurichay. The mapping class group of a shift of finite type. Journal of Modern Dynamics, 2018, 13: 115-145. doi: 10.3934/jmd.2018014
[11]	Vasso Anagnostopoulou. Stochastic dominance for shift-invariant measures. Discrete & Continuous Dynamical Systems - A, 2019, 39 (2) : 667-682. doi: 10.3934/dcds.2019027
[12]	R. Yamapi, R.S. MacKay. Stability of synchronization in a shift-invariant ring of mutually coupled oscillators. Discrete & Continuous Dynamical Systems - B, 2008, 10 (4) : 973-996. doi: 10.3934/dcdsb.2008.10.973
[13]	Akinori Awazu. Input-dependent wave propagations in asymmetric cellular automata: Possible behaviors of feed-forward loop in biological reaction network. Mathematical Biosciences & Engineering, 2008, 5 (3) : 419-427. doi: 10.3934/mbe.2008.5.419
[14]	Jonathan C. Mattingly, Etienne Pardoux. Invariant measure selection by noise. An example. Discrete & Continuous Dynamical Systems - A, 2014, 34 (10) : 4223-4257. doi: 10.3934/dcds.2014.34.4223
[15]	Luis Barreira and Jorg Schmeling. Invariant sets with zero measure and full Hausdorff dimension. Electronic Research Announcements, 1997, 3: 114-118.
[16]	S. A. Krat. On pairs of metrics invariant under a cocompact action of a group. Electronic Research Announcements, 2001, 7: 79-86.
[17]	Jamshid Moori, Amin Saeidi. Some designs and codes invariant under the Tits group. Advances in Mathematics of Communications, 2017, 11 (1) : 77-82. doi: 10.3934/amc.2017003
[18]	Lennard F. Bakker, Pedro Martins Rodrigues. A profinite group invariant for hyperbolic toral automorphisms. Discrete & Continuous Dynamical Systems - A, 2012, 32 (6) : 1965-1976. doi: 10.3934/dcds.2012.32.1965
[19]	Thomas Zaslavsky. Quasigroup associativity and biased expansion graphs. Electronic Research Announcements, 2006, 12: 13-18.
[20]	Giuseppe Da Prato. An integral inequality for the invariant measure of some finite dimensional stochastic differential equation. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3015-3027. doi: 10.3934/dcdsb.2016085

2018 Impact Factor: 1.143

American Institute of Mathematical Sciences