Abstract FR:

En regroupant un segment de plusieurs cellules en une unique nouvelle cellule, nous introduisons la notion d'automate groupe. Un tel nouvel automate cellulaire peut se definir algebriquement et peut etre vu comme une puissance du premier. Nous introduisons une relation de pre-ordre sur les automates cellulaires en disant que x est plus petit que y si une puissance de x est un sous-automate d'une puissance y. On transforme la structure de pre-ordre dans un ordre en considerant les classes d'equivalence. On montre d'abord que cet ordre admet un minimum global et que des classes d'equivalences tres naturelles apparaissent comme petites pour cet ordre. Parmis ces classes, citons non seulement l'extension des deux premieres classes de wolfram (automates nilpotents et automates periodiques), mais encore des classes d'automates cellulaires algebriquement simples (addition sur les entiers modulo p avec p premier). Nous montrons egalement qu'on peut trouver dans l'ordre deux chaines infinies admettant un maximum. Par contre, l'ordre n'admet pas de maximum global. Ce dernier resultat montre qu'il n'existe pas d'automate universel vis a vis de cette notion de regroupement. Il implique aussi qu'il n'existe pas un automate cellulaire intrinsequement universel en temps reel. L'etude de cet ordre conduit a des resultats d'indecidabilite. Tout d'abord, savoir si deux automates sont equivalents est indecidable (consequence d'un theoreme non trivial de culik et kari). Meme si on ajoute des conditions restrictives, on est conduit a des resultats d'indecidabilite mettant en jeu des techniques complexes : pavages nord-ouest deterministes.