Surjective Two-Neighbor Cellular Automata on Prime Alphabets

: Jarkko Kari, Ville Salo, Ilkka Törmä

: Jarkko Kari, Martin Kutrib, Andreas Malcher

: Giessen

: 2013

: IFIG Research Reports

: Proceedings 19th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2013): Exploratory Papers

: IFIG Research Reports

: 31

: 38

: 8

: http://www.informatik.uni-giessen.de/reports/Report1302.pdf

In this article, we present a simple proof for the fact that a surjective cellular automaton with neighborhood size 2 on a prime alphabet is permutive in some coordinate. We discuss the optimality of this result, and the existence of non-closing cellular automata of a given neighborhood and alphabet size.