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

Equipe(s) : lm,
Responsables :O. Finkel, A. Khélif, S. Rideau, T. Tsankov, A. Vignati
Email des responsables :
Salle : Zoom ID: 824 8220 9628; s'inscrire à la liste ou contacter silvain.rideau@imj-prg.fr pour le mot de passe.
Adresse :
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.

SalleZoom ID: 824 8220 9628; s'inscrire à la liste ou contacter silvain.rideau@imj-prg.fr pour le mot de passe.
Adresse
© IMJ-PRG