Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > The Most General Conservation ...

The Most General Conservation Law for a Cellular Automaton

Enrico Formenti, Jarkko Kari, Siamak Taati, The Most General Conservation Law for a Cellular Automaton. In: E. A. Razborov A. A. Semenov A. Slissenko A. Hirsch (Ed.), Proceedings of the Third International Computer Science Symposium in Russia, LNCS 5010, 194-203, Springer, 2008.

Abstract:

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.

Files:

Full publication in PDF-format

BibTeX entry:

@INPROCEEDINGS{inpFoKaTa08a,
  title = {The Most General Conservation Law for a Cellular Automaton},
  booktitle = {Proceedings of the Third International Computer Science Symposium in Russia},
  author = {Formenti, Enrico and Kari, Jarkko and Taati, Siamak},
  volume = {5010},
  series = {LNCS},
  editor = {Hirsch, E. A. Razborov A. A. Semenov A. Slissenko A.},
  publisher = {Springer},
  pages = {194-203},
  year = {2008},
  keywords = {cellular automata, conservation laws, decidability},
}

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

Edit publication