Abstract FR:

Cette these concerne un type particulier de parallelisme: les automates cellulaires. L'auteur etudie le probleme de la synchronisation d'une ligne de fusiliers, et notamment, le probleme ouvert concernant l'existence ou non d'un automate synchronisant dont l'ensemble des etats ne contiendrait que cinq elements. Deux approches sont decrites: 1) une premiere (descendante et constructive) montre comment, apres avoir construit un automate avec treize etats, il est possible de diminuer la cardinalite de l'ensemble par des codages successifs. Le procede de minsky (divide-and-conquer) est la base de ces solutions; 2) une deuxieme (ascendante et analytique) etudie certains comportements observes dans quelques automates n'ayant qu'un nombre tres reduit d'etats. Il est possible de construire des automates a deux etats qui passent par toutes les configurations possibles. Leur etude est ramenee a celle des automates cylindriques, permettant de mettre en avant des liens non triviaux avec la theorie des nombres. Il est montre comment quelques calculs simulent le comportement d'automates treillis en pavant le diagramme espace-temps par des losanges