Conservation Laws and Invariant Measures in Surjective Cellular Automata

Abstract : 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.
Type de document :
Communication dans un congrès
Fatès, Nazim and Goles, Eric and Maass, Alejandro and Rapaport, Iván. 17th International Workshop on Celular Automata and Discrete Complex Systems, 2011, Santiago, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, pp.113-122, 2011, DMTCS Proceedings
Liste complète des métadonnées

https://hal.inria.fr/hal-01196135
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 9 septembre 2015 - 11:14:54
Dernière modification le : mercredi 29 août 2018 - 11:02:02
Document(s) archivé(s) le : lundi 28 décembre 2015 - 23:01:13

Fichier

dmAP0108.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01196135, version 1

Collections

Citation

Jarkko Kari, Siamak Taati. Conservation Laws and Invariant Measures in Surjective Cellular Automata. Fatès, Nazim and Goles, Eric and Maass, Alejandro and Rapaport, Iván. 17th International Workshop on Celular Automata and Discrete Complex Systems, 2011, Santiago, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, pp.113-122, 2011, DMTCS Proceedings. 〈hal-01196135〉

Partager

Métriques

Consultations de la notice

153

Téléchargements de fichiers

182