Aspects structurels de la calculabilité des espaces de pavages

Mots clés

Pavages, Calculabilité

Détail de l'offre

Un pavage est une coloration des sommets d'une grille respectant des règles locales, généralement sous la forme d'une liste de motifs interdits. Les pavages sont des modèles discrets qui apparaissent en informatique théorique, dans l'étude des systèmes dynamiques, en physique statistique et cristallographie. Les liens entre pavages et calculabilité sont anciens et profonds. De nombreux problèmes naturels s'avèrent être indécidables, comme le problème du domino ou le calcul de l'entropie d'un pavage. Des travaux récents cherchent à délimiter précisément la frontière entre décidabilité et indécidabilité pour des classes de pavages dépendant de certains paramètres. Ce sujet de thèse propose une étude plus structurelle des liens entre propriétés dynamiques, combinatoires et calculatoires.

Une première direction consiste à étudier le 'paysage de calculabilité' d'un espace de pavages, à savoir la décidabilité des problèmes classiques lorsqu'on se restreint aux sous-pavages de ce pavage. Cette approche a des similitudes avec l'étude des pavages définis sur d'autres structures - groupes [1,2,3], graphes réguliers, fractales discrètes [4], pavages géométriques [5] - où la décidabilité est liée aux propriétés algébriques de la structure. L'approche que nous proposons permettrait d'analyser des systèmes individuels. Quelques résultats récents vont dans cette direction, notamment concernant l'entropie [6] ou le problème du domino [7], mais pas de manière systématique.

Une deuxième direction concerne la complexité et l'expressivité des invariants de conjugaison. Les invariants permettent de montrer que des pavages ne sont pas conjugués, c'est-à-dire pas isomorphes en tant que systèmes dynamiques. Nous proposons d'étudier les relations entre leur expressivité et leur complexité, en cherchant notamment à identifier la complexité minimale permettant de séparer tous les pavages d'une classe donnée.