caa a22 4500 445842903 CHVBK 20180317145350.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s11047-010-9222-0 doi (NATIONALLICENCE)springer-10.1007/s11047-010-9222-0 On the hierarchy of conservation laws in a cellular automaton [Elektronische Daten] [Enrico Formenti, Jarkko Kari, Siamak Taati] Conservation laws in cellular automata (CA) are studied as an abstraction of the conservation laws observed in nature. In addition to the usual real-valued conservation laws we also consider more general group-valued and semigroup-valued conservation laws. The (algebraic) conservation laws in a CA form a hierarchy, based on the range of the interactions they take into account. The conservation laws with smaller interaction ranges are the homomorphic images of those with larger interaction ranges, and for each specific range there is a most general law that incorporates all those with that range. For one-dimensional CA, such a most general conservation law has—even in the semigroup-valued case—an effectively constructible finite presentation, while for higher-dimensional CA such effective construction exists only in the group-valued case. It is even undecidable whether a given two-dimensional CA conserves a given semigroup-valued energy assignment. Although the local properties of this hierarchy are tractable in the one-dimensional case, its global properties turn out to be undecidable. In particular, we prove that it is undecidable whether this hierarchy is trivial or unbounded. We point out some interconnections between the structure of this hierarchy and the dynamical properties of the CA. In particular, we show that positively expansive CA do not have non-trivial real-valued conservation laws. Springer Science+Business Media B.V., 2010 Cellular automata nationallicence Conservation laws nationallicence Energy nationallicence Reversibility nationallicence Undecidability nationallicence Dynamical systems nationallicence Chaos nationallicence Formenti Enrico Laboratoire I3S, Université de Nice Sophia Antipolis, 2000 route des Lucioles, Les Algorithmes - Bât. Euclide B, BP 121, 06903, Sophia Antipolis Cedex, France aut Kari Jarkko Department of Mathematics, University of Turku, 20014, Turku, Finland aut Taati Siamak Laboratoire I3S, Université de Nice Sophia Antipolis, 2000 route des Lucioles, Les Algorithmes - Bât. Euclide B, BP 121, 06903, Sophia Antipolis Cedex, France aut Natural Computing Springer Netherlands 10/4(2011-12-01), 1275-1294 1567-7818 10:4<1275 2011 10 11047 https://doi.org/10.1007/s11047-010-9222-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11047-010-9222-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Formenti Enrico Laboratoire I3S, Université de Nice Sophia Antipolis, 2000 route des Lucioles, Les Algorithmes - Bât. Euclide B, BP 121, 06903, Sophia Antipolis Cedex, France aut NATIONALLICENCE 700 1- Kari Jarkko Department of Mathematics, University of Turku, 20014, Turku, Finland aut NATIONALLICENCE 700 1- Taati Siamak Laboratoire I3S, Université de Nice Sophia Antipolis, 2000 route des Lucioles, Les Algorithmes - Bât. Euclide B, BP 121, 06903, Sophia Antipolis Cedex, France aut NATIONALLICENCE 773 0- Natural Computing Springer Netherlands 10/4(2011-12-01), 1275-1294 1567-7818 10:4<1275 2011 10 11047 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer