Évènement

Guillaume THEYSSIER
i2m, CNRS, université d'Aix-Marseille
https://theyssier.perso.math.cnrs.fr/

Date(s) : 20/09/2024   iCal
11h00 - 12h00

Cet exposé est motivé entre autres par la conjecture de Ballier-Stein qui affirme que le problème du domino sur le graphe de Cayley d’un groupe finiment engendré est décidable si et seulement si le groupe est virtuellement libre. Nous adopterons le point de vue des automates cellulaires (dont nous donnerons une définition sur des graphes arbitraire) et de la logique du premier ordre sur leurs orbites, i.e. des propriétés comme « avoir un point fixe », « être injectif », « être surjectif », etc. Le problème du domino correspond à décider si un automate cellulaire donné vérifie une certaine propriété de ce type, en l’occurrence la propriété « avoir un point fixe », mais il est naturel de s’intéresser aussi à d’autres propriétés comme « être injectif ». Plus généralement, à toute formule du premier ordre sur les orbites est associé un problème de décision dont on peut questionner la décidabilité selon le graphe considéré. Notre résultat principal est que ce formalisme (logique du premier ordre sur les orbites d’automates cellulaires) est équivalent à la logique monadique du second ordre sur les graphes. Nous en déduirons plusieurs corollaires, dont l’existence d’une formule du premier ordre sur les orbites d’automates cellulaires qui est décidable sur le graphe de Cayley d’un groupe finiment engendré si et seulement le groupe est virtuellement libre.

Emplacement
Saint-Charles - FRUMAM (2ème étage)

Catégories

• Séminaire