• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Conservation Laws and Invariant Measures in Surjective Cellular Automata

Jarkko Kari, Siamak Taati, Conservation Laws and Invariant Measures in Surjective Cellular Automata. In: Nazim Fatès, Eric Goles, Alejandro Maass Maass, Ivan Rapaport (Eds.), DMTCS Proceedings, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, Discrete Mathematics and Theoretical Computer Science Proceedings, 113–122, DMTCS, 2011.

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.

BibTeX entry:

@INPROCEEDINGS{inpKaTa11a,
  title = {Conservation Laws and Invariant Measures in Surjective Cellular Automata},
  booktitle = {DMTCS Proceedings, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems},
  author = {Kari, Jarkko and Taati, Siamak},
  series = {Discrete Mathematics and Theoretical Computer Science Proceedings},
  editor = {Fatès, Nazim and Goles, Eric and Maass, Alejandro Maass and Rapaport, Ivan},
  publisher = {DMTCS},
  pages = {113–122},
  year = {2011},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication