Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Linear Algebra Based Bounds fo...

Linear Algebra Based Bounds for One-dimensional Cellular Automata

Jarkko Kari, Linear Algebra Based Bounds for One-dimensional Cellular Automata. In: Markus Holzer, Martin Kutrib, Giovanni Pighizzini (Eds.), Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Gie{\ss}en/Limburg, Germany, July 25-27, 2011. Proceedings, Lecture Notes in Computer Science 6808, 1–7, Springer, 2011.

Abstract:

One possible complexity measure for a cellular automaton is the size of its neighborhood. If a cellular automaton is reversible with a small neighborhood, the inverse automaton may need a much larger neighborhood. Our interest is to find good upper bounds for the size of this inverse neighborhood. It turns out that a linear algebra approach provides better bounds than any known combinatorial methods. We also consider cellular automata that are not surjective. In this case there must exist so-called orphans, finite patterns without a pre-image. The length of the shortest orphan measures the degree of non-surjectiveness of the map. Again, a linear algebra approach provides better bounds on this length than known combinatorial methods. We also use linear algebra to bound the minimum lengths of any diamond and any word with a non-balanced number of pre-images. These both exist when the cellular automaton in question is not surjective. All our results deal with one-dimensional cellular automata. Undecidability results imply that in higher dimensional cases no computable upper bound exists for any of the considered quantities.

BibTeX entry:

@INPROCEEDINGS{inpKari_Jarkko11b,
  title = {Linear Algebra Based Bounds for One-dimensional Cellular Automata},
  booktitle = {Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Gie{\ss}en/Limburg, Germany, July 25-27, 2011. Proceedings},
  author = {Kari, Jarkko},
  volume = {6808},
  series = {Lecture Notes in Computer Science},
  editor = {Holzer, Markus and Kutrib, Martin and Pighizzini, Giovanni},
  publisher = {Springer},
  pages = {1–7},
  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