Séminaires à venir

Les automates cellulaires sont des systèmes dynamiques discrets qui peuvent être définis sur n'importe quel groupe finiment engendré. L'étude des liens entre les propriétés élémentaires de leurs orbites et le groupe sur lequel ils sont définis s'est révélée d'une grande richesse, donnant lieu par exemple au théorème du Jardin d'Éden qui fournit une caractérisation des groupes moyennables. On peut se demander quelles propriétés du groupe peuvent être capturées par des propriétés élémentaires des orbites d'automates cellulaires. Dans cet exposé, nous nous intéressons à une généralisation des automates cellulaires à des graphes arbitraires, et aux propriétés des orbites que l'on peut exprimer en logique du premier ordre. Nous verrons que, dans ce cadre, la logique du premier ordre sur les orbites est équivalente à la logique monadique du second ordre sur les graphes, ce qui est gage d'une grande expressivité. Pour les graphes de Cayley de groupes, nous obtenons comme corollaire une propriété des orbites qui est décidable si et seulement si le groupe est virtuellement libre, ce qui est à rapprocher de la conjecture de Ballier-Stein, affirmant qu'il en serait de même pour le problème du domino.
NB: cet exposé ne suppose aucun prérequis sur les automates cellulaires, ni en logique.