diaporama

Des théorèmes d'accélérations linéaire sont connus pour de nombreux modèles, comme les machines de Turing où les automates cellulaires en dimension un. Pour les automates de dimension deux, ces théorèmes n'étaient conus qu'avec certains voisinages. 
Nous présentons ici un moyen de réaliser une accélération linéaire avec n'importe quel voisinage en 2D. 

Toutes ces construction sont réalisées pour des langages d'images 2D rectangulaires. La méthode que nous proposons peut s'adapter à des langages d'images de formes quelconques. Nous présenterons aussi cette nouvelle construction. 

Ces constructions montrent encore une fois le lien entre forme du voisinage et forme de l'entrée puisque c'est le même genre de technique qui permet de pallier aux difficultés rencontrées dans ces deux variations du problème.