Accueil Publimath  Aide à la recherche   Recherche Avancée   Imprimer la fiche   Aidez-nous à améliorer cette fiche  Vidéo d'aide
Certification IDDN Valid HTML 4.01 Transitional
Auteur(s) : Moutot Etienne

Titre : Around the Domino Problem - Combinatorial Structures and Algebraic Tools. (Autour du problème du Domino - Structures combinatoires et outils algébriques.)

Editeur : Université de Lyon Lyon, 2020
Format : A4, 106 p. Bibliogr. p. 99-106

Type : thèse, Informatique, Lyon, 2020 Langue : Anglais Support : papier

Public visé : chercheur, enseignant, formateur

Classification : A79Thèses et mémoires universitaires
Formation à l'enseignement, initiale et continue.
 G99Divers (par exemple : ensembles convexes, revêtements, mosaïques, géométries non-euclidiennes, géométries finies)
Formation à l'enseignement, initiale et continue.
 P29Informatique théorique (structuration des données, codage des données, théorie du codage et de l'information, analyse des algorithmes et problèmes de complexité, modes de calcul et complexité calculatoire, langages formels)
Formation à l'enseignement, initiale et continue.
 

Résumé : Abstract

Étant donné un ensemble fini de tuiles carrés, le problème du domino est la question : "est-il possible de paver le plan entier en utilisant ces tuiles ?"
Ce problème est connu pour être indécidable dans le cas des pavages du plan, et est très fortement lié à la question de la périodicité des pavages. Dans cette thèse nous abordons ce problème de deux point de vue différents : en regardant le cas particulier des pavages de faible complexité et en le généralisant aux structures plus généra les des groupes.
Un pavage du plan est dit de faible complexité s'il y apparait moins de mn rectangles de taille m x n. Nivat conjecture en 1997 qu'un tel pavage est nécessairement périodique, avec comme conséquence que le problème du domino serait décidable pour les pavages de faible complexité. En continuant de développer des outils algébriques introduits par Kari et Szabados, nous prouvons une version généralisée de la conjecture de Nivat pour une classe de pavages particuliers (certains des sous-décalage algébrique). Nous parvenons également à montrer que la conjecture de Nivat est vraie pour tout pavage uniformément récurrent, avec comme conséquence que le problème du domino est effectivement décidable pour les pavages de faible complexité.
Le problème du domino peut se formuler dans le cadre plus général des graphes de Cayley de groupes. Dans cette thèse nous développons de nouvelles techniques permettant de relier les graphes de Cayley de certains groupes à des graphes de substitutions. Une première technique nous permet de montrer qu'il existe à la fois des pavages fortement apériodiques et faiblement-non-fortement apériodiques pour les groupes de Baumslag-Solitar BS(l,n). Une seconde nous permet de montrer que le problème du domino est indécidable pour les groupes de surface, ce qui fourni une nouvelle classe de groupe vérifiant la conjecture disant que que le problème du domino d'un groupe est décidable si et seulement si le groupe est virtuellement libre.

Notes :
Cette thèse est présentée dans Tangente n° 199 .

Une version texte intégral est en téléchargement sur le site https://hal.science/tel-02967024

Mots clés :


© ADIREM-APMEP -2003- ISSN 1292-8054 Mise à jour 24/01/2023
Accueil Publimath  Aide à la recherche   Recherche Avancée   Imprimer la fiche   Aidez-nous à améliorer cette fiche  Vidéo d'aide
Certification IDDN Valid HTML 4.01 Transitional