Théo Grente (France Energies Marines, Caen)

Dans cet exposé je présenterai une méthode utilisant les bases de Groebner pour rechercher des automates cellulaires (AC) ayant une propriété donnée. Cette méthode a d’abord été conçue pour concevoir des équations différentielles partielles (PDE) intéressantes à partir d’AC. Pour faire le lien entre le comportement discret des AC et le comportement continu des PDE, on va se servir d’un objet intermédiaire : les ISPS (Interacting Stochastic Particle Systems).

En utilisant les ISPS, on peut traduire la fonction de transition d’un AC de rayon (taille du voisinage) donné en un polynôme sur un anneau multivarié. Une fois sous cette forme, on peut se servir des bases de Groebner pour déterminer quelles conditions doit remplir cet AC pour pouvoir être dérivé en PDE. En effectuant cette méthode sur plusieurs tailles de voisinage d’AC, une conjecture a été établie sur les conditions devant être vérifiées par un AC de rayon donné pour pouvoir être dérivé en PDE. Une preuve de cette conjecture a ensuite été trouvée et sera présentée dans cet exposé.

Cette méthode, consistant à transformer la fonction de transition d’un AC en polynôme sur un anneau mutivarié pour pouvoir ensuite utiliser les bases de Groebner, est généralisable à la recherche d’autres propriétés sur les AC. Un autre exemple d’application sera présenté dans cet exposé.