Conservation Laws and Invariant Measures in Surjective Cellular Automata

J. Kari; S. Taati

doi:10.46298/dmtcs.2968

Conservation Laws and Invariant Measures in Surjective Cellular Automata

J. Kari, S. Taati

extern

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 onedimensional 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.

Original language	English
Title of host publication	Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems
Publisher	Discrete Mathematics and Theoretical Computer Science
Pages	113-122
Number of pages	10
DOIs	https://doi.org/10.46298/dmtcs.2968
Publication status	Published - 21 Nov 2011

Access to Document

10.46298/dmtcs.2968

2103-6774-1-PB
Open Access (free)
Final published version, 260 KB

Cite this

@inproceedings{17b5714d4fb041deae7663cdc536032c,

title = "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 onedimensional 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.",

author = "J. Kari and S. Taati",

note = "Automata 2011",

year = "2011",

month = nov,

day = "21",

doi = "10.46298/dmtcs.2968",

language = "English",

pages = "113--122",

booktitle = "Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems",

publisher = "Discrete Mathematics and Theoretical Computer Science",

}

Conservation Laws and Invariant Measures in Surjective Cellular Automata. / Kari, J.; Taati, S.
Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems. Discrete Mathematics and Theoretical Computer Science, 2011. p. 113-122.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Conservation Laws and Invariant Measures in Surjective Cellular Automata

AU - Kari, J.

AU - Taati, S.

N1 - Automata 2011

PY - 2011/11/21

Y1 - 2011/11/21

N2 - 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 onedimensional 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.

AB - 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 onedimensional 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.

U2 - 10.46298/dmtcs.2968

DO - 10.46298/dmtcs.2968

M3 - Conference contribution

SP - 113

EP - 122

BT - Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems

PB - Discrete Mathematics and Theoretical Computer Science

ER -

Conservation Laws and Invariant Measures in Surjective Cellular Automata

Abstract

Access to Document

Fingerprint

Cite this