Preface
This special issue of the Journal of Cellular Automata follows AUTOMATA 2010, the 16th international workshop on cellular automata & discrete complex systems, held in Nancy, France, 14th – 16th June 20101.
The five papers it contains extend some earlier shorter versions: three of these first versions appeared in the DMTCS proceedings2, and two of them were presented as “short papers” in the workshop and appeared in the local proceedings3. The papers of this issue reflect the diversity of approaches in the field of cellular automata.
The paper by Gütschow et al. presents a deep analysis of how cellular automata generate self-similar patterns. Such patterns are often found in the space-time diagrams of various rules but little has been known so far as to which mathematical conditions allow this type of pattern to exist.
The paper by Baird and Fagin tackles the delicate question to find conserved quantities in the evolution of cellular automata. This problem has of course a central position for all the researchers that use cellular automata as a modelling tool but even without being motivated by practical purposes, the question has a beauty for itself. Interestingly, the authors suggest that the conservation of various quantities may serve as a basis for building a new classification of rules.
The third paper is the work of Goles and Moreira, which is closely related to the previous issue: the authors examine the number-conserving properties of various rules, which is a special – but not trivial ! – case of the question examined in the second paper. The path they follow is to examine how communication complexity gives insights on this highly important topic.
I am very happy that the current issue contains a contribution from the Professor Nishio, who is has been a “pillar” of our community. His paper presents his advances on the way we can analyse the neighbourhood of a cellular automaton, a topic that he has been covering with the most serious scrutiny these last years.
The last paper of the issue presents a key “application” of cellular automata: the generation of pseudo-random sequences by means of non-homogeneous linear cellular automata. I say “application” with the greatest care as I consider the frontier between “theory” and “practice” to be falsely clear: every scientist is the “theoretician” of someone and the “applier” of someone else! It is though always stimulating to see that the problems that nourish our community come from various horizons, among which cryptography.
My last words will be to express my warmest acknowledgements to all the persons that made this publication possible: the authors for their work and patience, the reviewers for the time and energy they invested in a careful reading of the manuscripts and all the persons that helped us make AUTOMATA 2010… “an event”.
Nazim Fatès, Nancy,
December 23, 2011
1 see http://automata.loria.fr/
2 see http://www.dmtcs.org, volume AL
3 see http://hal.inria.fr/inria-00549645, ISBN 978-2-905267-74-0