Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > On the Hierarchy of Conservati...

On the Hierarchy of Conservation Laws in a Cellular Automaton

Enrico Formenti, Jarkko Kari, Siamak Taati, On the Hierarchy of Conservation Laws in a Cellular Automaton. Natural Computing 10(4), 1275–1294, 2011.

Abstract:

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 onedimensional 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 onedimensional 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 realvalued conservation laws.

BibTeX entry:

@ARTICLE{jFoKaTa11a,
  title = {On the Hierarchy of Conservation Laws in a Cellular Automaton},
  author = {Formenti, Enrico and Kari, Jarkko and Taati, Siamak},
  journal = {Natural Computing},
  volume = {10},
  number = {4},
  pages = {1275–1294},
  year = {2011},
}

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

Publication Forum rating of this publication: level 1

Edit publication