Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Bounds on Non-Surjective Cellu...

Bounds on Non-Surjective Cellular Automata

Jarkko Kari, Pascal Vanier, Thomas Zeume, Bounds on Non-Surjective Cellular Automata. In: Rastislav Kralovic, Damian Niwinski (Eds.), Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings, Lecture Notes in Computer Science 5734, 439–450, Springer, 2009.

Abstract:

Cellular automata (CA) are discrete, homogeneous dynamical systems. Non-surjective one-dimensional CA have finite words with no preimage (called orphans), pairs of different words starting and ending identically and having the same image (diamonds) and words with more/ fewer preimages than the average number (unbalanced words). Using a linear algebra approach, we obtain new upper bounds on the lengths of the shortest such objects. In the case of an n-state, non-surjective CA with neighborhood range 2 our bounds are of the orders O(n^2), O(n^3/2) and O(n) for the shortest orphan, diamond and unbalanced word, respectively.

BibTeX entry:

@INPROCEEDINGS{inpKaVaZe09a,
  title = {Bounds on Non-Surjective Cellular Automata},
  booktitle = {Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings},
  author = {Kari, Jarkko and Vanier, Pascal and Zeume, Thomas},
  volume = {5734},
  series = {Lecture Notes in Computer Science},
  editor = {Kralovic, Rastislav and Niwinski, Damian},
  publisher = {Springer},
  pages = {439–450},
  year = {2009},
}

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

Publication Forum rating of this publication: level 1

Edit publication