Séminaires : Séminaire de Logique Lyon-Paris

Equipe(s) : lm,
Responsables :O. Finkel, T. Ibarlucía, A. Khélif, S. Rideau, A. Vignati
Email des responsables :
Salle : https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge
Adresse :Sophie Germain
Description

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion


Orateur(s) Laurent Bartholdi - ENS,
Titre Problèmes de domino sur les groupes
Date06/04/2020
Horaire16:00 à 17:00
Diffusion
Résume

Soit G un groupe, fixé une fois pour toutes. On s'intéresse aux
sous-décalages sur G de type fini: ce sont les sous-ensembles fermés
G-invariants de {1,...,d}^G définis par un ensemble fini de mots
interdits. Dualement, ce sont aussi les G-algèbres booléennes de
présentation finie.

Plus précisément, on s'intéresse aux problèmes de décision suivants:
est-il décidable, à partir d'une liste de mots interdits, si le
sous-décalage associé est non-vide? ou même mieux s'il contient un
ouvert donné (spécifié par des valeurs sur un ensemble fini de
coordonnées)? Dualement, l'algèbre associée est-elle triviale? ou
a-t-elle problème du mot résoluble?

Ces problèmes ont été surtout considérés pour G=ℤ^2, auquel cas on parle
de «pavages de Wang»; ces deux problèmes sont indécidables.

Selon une conjecture de Jeandel, ces problèmes sont algorithmiquement
résolubles seulement si G a un sous-groupe libre d'indice fini. Je
décrirai l'état du problème, et ajouterai une contribution, obtenue en
collaboration avec Ville Salo: pour le groupe de
l'«allumeur de réverbères» G=ℤ/2≀ℤ.

Ce groupe est important car il apparaît à la frontière entre "arbre"
(groupes libres) et "plan" (Z^2). Nous montrons que son problème de
domino est indécidable.

Sallehttps://bigbluebutton.imj-prg.fr/b/sil-gwg-gge
AdresseSophie Germain
© IMJ-PRG