Jarkko Kari ; Siamak Taati
-
Conservation Laws and Invariant Measures in Surjective Cellular Automata
dmtcs:2968 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2011,
DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems
-
https://doi.org/10.46298/dmtcs.2968
Conservation Laws and Invariant Measures in Surjective Cellular AutomataArticle
Authors: Jarkko Kari 1,2; Siamak Taati 3
0000-0003-0670-6138##0000-0002-6503-2754
Jarkko Kari;Siamak Taati
1 Departement of Mathematics, University of Turku
2 University of Turku
3 Department of Mathematics
We discuss a close link between two seemingly different topics studied in the cellular automata literature: additive conservation laws and invariant probability measures. We provide an elementary proof of a simple correspondence between invariant full-support Bernoulli measures and interaction-free conserved quantities in the case of one-dimensional surjective cellular automata. We also discuss a generalization of this fact to Markov measures and higher-range conservation laws in arbitrary dimension. As a corollary, we show that the uniform Bernoulli measure is the only shift-invariant, full-support Markov measure that is invariant under a strongly transitive cellular automaton.
Cellular automata and discrete dynamical systems; Funder: Research Council of Finland; Code: 131558
Bibliographic References
6 Documents citing this article
Natalia V. Menshutina;Andrey V. Kolnoochenko;Evgeniy A. Lebedev, 2020, Cellular Automata in Chemistry and Chemical Engineering, Annual Review of Chemical and Biomolecular Engineering, 11, 1, pp. 87-108, 10.1146/annurev-chembioeng-093019-075250.
Jarkko Kari, 2018, Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments, New Generation Computing, 36, 3, pp. 145-172, 10.1007/s00354-018-0034-6.
Pierre-Yves Louis;Francesca R. Nardi, 2018, Probabilistic Cellular Automata, Emergence, complexity and computation, 10.1007/978-3-319-65558-1.
Roberto Fernández;Pierre-Yves Louis;Francesca R. Nardi, Emergence, complexity and computation, Overview: PCA Models and Issues, pp. 1-30, 2018, 10.1007/978-3-319-65558-1_1.
Jean Mairesse;Irène Marcovici, 2014, Probabilistic cellular automata and random fields with i.i.d. directions, Annales de l Institut Henri Poincaré Probabilités et Statistiques, 50, 2, 10.1214/12-aihp530, https://doi.org/10.1214/12-aihp530.