BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:5262@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20240920T110000
DTEND;TZID=Europe/Paris:20240920T120000
DTSTAMP:20240910T110900Z
URL:https://www.i2m.univ-amu.fr/evenements/seminaire-rauzy-2024-09-20/
SUMMARY:Guillaume THEYSSIER (i2m\, CNRS\, université d'Aix-Marseille): Aut
 omates cellulaires\, problèmes du domino et logique sur des graphes arbit
 raires
DESCRIPTION:Guillaume THEYSSIER: Cet exposé est motivé entre autres par l
 a conjecture de Ballier-Stein qui affirme que le problème du domino sur l
 e graphe de Cayley d'un groupe finiment engendré est décidable si et seu
 lement si le groupe est virtuellement libre. Nous adopterons le point de v
 ue 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". P
 lus 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écidabil
 ité selon le graphe considéré. Notre résultat principal est que ce for
 malisme (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écidabl
 e sur le graphe de Cayley d'un groupe finiment engendré si et seulement l
 e groupe est virtuellement libre.
CATEGORIES:Séminaire,Rauzy
LOCATION:Saint-Charles - FRUMAM  (2ème étage)\, 3 Place Victor Hugo\, Mar
 seille\, 13003\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=3 Place Victor Hugo\, Marse
 ille\, 13003\, France;X-APPLE-RADIUS=100;X-TITLE=Saint-Charles - FRUMAM  (
 2ème étage):geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20240331T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR