Offre de thèse
Structures de communication dans les pavages
Date limite de candidature
27-04-2026
Date de début de contrat
01-10-2026
Directeur de thèse
HOYRUP Mathieu
Encadrement
Le doctorant fera partie de l'équipe Inria Mocqua au Loria, bénéficiera d'un bureau, d'un ordinateur et d'un financement lui permettant d'assister à des conférences.o
Type de contrat
école doctorale
équipe
MOCQUAcontexte
Produire une coloration du plan satisfaisant certaines contraintes locales est un problème qui a été montré indécidable par Berger en 1966. Une des raisons pour lesquelles ce problème est difficile est que des contraintes locales induisent des contraintes globales difficiles à satisfaire conjointement, et induisent implicitement un réseau d'interdépendance entre les cases du plan. Ce projet de thèse cherche à rendre explicite de tels réseaux de corrélations, en définissant des structures mathématiques capturant la communication nécessaire entre les cases pour produire un pavage correct.spécialité
Informatiquelaboratoire
LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Mots clés
Dynamique symbolique, Topologie
Détail de l'offre
Les pavages du plan sont des colorations d'une grille satisfaisant des contraintes locales données. Produire de tels pavages, étant donné un ensemble fini de contraintes locales, est un fameux problème indécidable: il n'existe pas d'algorithme général permettant de le résoudre (Berger 1966). Intuitivement, des contraintes locales induisent des corrélations à longue distance difficiles à prédire et à satisfaire. L'objectif général de ce projet est de développer une compréhension de ces corrélations en identifiant le degré de communication nécessaire entre les cases de la grille pour produire un pavage correct.
Ce projet fait appel à des outils informatiques et mathématiques divers, tels que la dynamique symbolique, la topologie, la combinatoire, l'algorithmique distribuée. Nous chercherons à établir des liens entre des notions de corrélations spécifiques à chacune de ces disciplines. Plus précisément, chacun de ces domaines fournit des outils permettant de décomposer un objet complexe en objets plus simples, et de mesurer l'interdépendance entre ces derniers (mélange, ergodicité, corrélations, complexité de communication, algorithme réparti). Il s'agira d'établir des liens formels entre ces notions, en commençant par l'analyse d'exemples concrets et en cherchant à généraliser les relations observées.
Nous chercherons à proposer des objets capturant des degrés de communication et d'identifier, étant donné un ensemble de contraintes locales, la ou les structures de communications induites. Plusieurs pistes sont envisageables et pourront être explorées au fur et à mesure de l'avancée des travaux. Les travaux (Fatès, Marcovici et Taati 2022), (Favereau, Hoyrup 2025) et (Gangloff, Hellouin et Opocha 2026) pourront servir de points de départ. Il s'agira alors de confronter ces définitions à des classes de pavages particulières, par exemples des classes restreintes de tuiles de Wang, ou des diagrammes espace-temps d'automates cellulaires élémentaires, permettant d'identifier les limites de ces définitions et de proposer des généralisations.
Keywords
Symbolic dynamics, Topology
Subject details
A tiling of the plane is a coloration of the grid satisfying given local constraints. Producing such tilings is a famous problem, known to be undecidable from the work of (Berger 1966). Intuitively, local constraints induce long-range correlations that are difficult to predict and satisfy. The general goal of this project is to improve our understanding of those correlations by identifying the degree of communication that is needed between the cells in order to produce a correct tiling. The theories and techniques underlying this project come from various fields from computer science and mathematics, such as symbolic dynapics, topology, combinatorics or distributed algorithms. We will establish relationship between notions of correlations arising from each one of these fields. More precisely, they provide tools that enable one to decompose a complex object into simple ones, and to measure the inderdependence between them (mixing, ergodicity, correlations, communication complexity, distributed algorithm). We will establish formal connection between these notions, starting with concrete examples and generalising by defining suitable concepts. The sutdent will propose objects capturing degree of communications and try to identify, given a set of local constraints, the induced communication structures. Several directions can be followed, and the articles (Fatès, Marcovici et Taati 2022), (Favereau, Hoyrup 2025) and (Gangloff, Hellouin et Opocha 2026) can serve as a starting point. The student will apply these theoretical developments to particular classes of tilings, such as Wang tiles or space-time diagrams of cellular automata, and try to identify the limits of the definition and possibly propose extensions of them.
Profil du candidat
Master en informatique théorique, fort intérêt pour les systèmes dynamiques symboliques et la topologie.
Candidate profile
Master degree in theoretical computer science, strong interest in symbolic dynamical systems and topology.
Référence biblio
- Berger. The Undecidability of the Domino Problem. Memoirs of the American Mathematical Society (1966)
- Fatès, Marcovici et Taati. Self-stabilisation of Cellular Automata on Tilings. Fundam. Informaticae 185(1): 27-82 (2022)
- Favereau et Hoyrup. Ergodic Theory and Dynamical Systems 45(11): 3377-3418 (2025)
- Gangloff, Hellouin et Opocha. Short-range and long-range order: a transition in block-gluing behavior in Hom shifts. Soumis (2026).