zbMATH — the first resource for mathematics

The most general conservation law for a cellular automaton. (English) Zbl 1142.68443
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 194-203 (2008).
Summary: We study the group-valued and semigroup-valued conservation laws in cellular automata (CA). We provide examples to distinguish between semigroup-valued, group-valued and real-valued conservation laws. We prove that, even in one-dimensional case, it is undecidable if a CA has any non-trivial conservation law of each type. For a fixed range, each CA has a most general (group-valued or semigroup-valued) conservation law, encapsulating all conservation laws of that range. For one-dimensional CA the semigroup corresponding to such a most general conservation law has an effectively constructible finite presentation, while for higher-dimensional ones no such effective construction exists.
For the entire collection see [Zbl 1136.68005].

68Q80 Cellular automata (computational aspects)
PDF BibTeX Cite
Full Text: DOI