Integer Gradient for Cellular Automata: Principle and Examples

Luidnel Maignan 1, * Frédéric Gruau 1, 2
* Auteur correspondant
1 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, LRI - Laboratoire de Recherche en Informatique
Abstract : When programming a spatial computing medium such as a cellular automaton, the hop count distance to some set of sources (particles) is an often used information. In particular, we consider the case where the sources themselves are moving. Due to the locality of communication, only an estimation of the distance can be made at each time step, and each location. When no assumption is made on the size of the medium, that distance takes its values in N, which is not desirable, because it does not lead to finite state. This paper shows how to use the modulo operation to project that set of N-fields into a finite set of Z/nZfields. Using the modulo stored at each site, we show that we are still able to compute the local differential of the original field, allowing to manipulate the former as a directional gradient. It allows us to evaluate the direction of the nearest source, provided the sources move at bounded speed, less than one site per time unit. This information can be used to solve several problems of spatial nature. In the particular case of cellular automata, we present two rules using the modulo representation of distance field: Voronoi Diagram and Convex Hull. The two rules applies for moving sources, although at the moment, the convex hull has been implemented only for static sources.
Type de document :
Communication dans un congrès
SASO Workshop, 2008, Venise, Italy. IEEE Computer Society, 2008
Liste complète des métadonnées
Contributeur : Frederic Gruau <>
Soumis le : lundi 29 novembre 2010 - 23:03:09
Dernière modification le : jeudi 24 mai 2018 - 15:59:23


  • HAL Id : inria-00541143, version 1



Luidnel Maignan, Frédéric Gruau. Integer Gradient for Cellular Automata: Principle and Examples. SASO Workshop, 2008, Venise, Italy. IEEE Computer Society, 2008. 〈inria-00541143〉



Consultations de la notice