In this article, co-written with Véronique Terrier for the Latin 2002 conference, we investigate how increasing the dimension of the array can help to draw signals on cellular automata. We show the existence of a gap of constructible signals in any dimension. We exhibit two cellular automata in dimension 2 to show that increasing the dimension allows to reduce the number of states required for some constructions.
A few words about this article
While researching for this result, I made some computer-guided experimentation. You may for example enjoy a Geomview file of a space-time diagram of a 3-states cellular automaton generating a signal of width \(\log(t)\) above the real-time signal. It was produced by a C program (available below). I used to put a Java applet here to see the structure. As I do not have the time to convert it to some more modern format, please use geomview to see it.
The talk is available in English (version Latin 2002) and French. The slides were made with a custom-style using ppower4, a technology nowadays obsoleted by beamer for LaTeX slides. It was kind of fun at the time.
The documents
Citing this publication
This publication was made in the proceedings of the Latin 2002 conference that took place this year in Cancun (Mexico).
@InProceedings{dt02,
author = {Jean-Christophe Dubacq and V{\'e}ronique Terrier},
title = {Signals for Cellular Automata in Dimension 2 or Higher},
booktitle = {LATIN 2002: Theoretical Informatics, 5th Latin American Symposium, Cancun, Mexico, April 3-6, 2002, Proceedings},
pages = {451--464},
year = {2002},
editor = {Sergio Rajsbaum},
volume = {2286},
series = {Lecture Notes in Computer Science},
month = may,
publisher = {Springer},
isbn = {3-540-43400-3}
}