Topological properties of cellular automata on trees

Gabriele Fici
(Université Nice Sophia Antipolis, France)
Francesca Fiorenzi
(Université Paris-Sud 11, France)

We prove that there do not exist positively expansive cellular automata defined on the full k-ary tree shift (for k>=2). Moreover, we investigate some topological properties of these automata and their relationships, namely permutivity, surjectivity, preinjectivity, right-closingness and openness.

In Enrico Formenti: Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires (AUTOMATA&JAC 2012), La Marana, Corsica, September 19-21, 2012, Electronic Proceedings in Theoretical Computer Science 90, pp. 255–266.
Published: 13th August 2012.

ArXived at: http://dx.doi.org/10.4204/EPTCS.90.20 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org