Soficité des espaces de pavages multidimensionnels

En dynamique symbolique, un sous-shift multidimensionnel est un language formel de coloriages infinis de l'espace discret défini en termes de motifs interdits. Comme les langages de mots finis, pour lesquels ont été définies des classes de complexité (qui incluent classiquement les langages locaux, rationnels, algébriques ou calculablement énumérables…) en fonction de l'expressivité des différentes machines qui les reconnaissent (respectivement : les automates locaux, les automates finis, les automates à piles et les machines de Turing), les sous-shifts ont été classifiés en sous-shifts de types finis (définis par des familles finies de motifs interdits), sous-shifts effectifs (définis par des familles calculablement énumérables) et sous-shifts sofiques : ces derniers forment une classe intermédiaire entre les deux précédentes, et sont définis comme les images morphiques des sous-shifts de types finis par des automates cellulaires.Nous nous intéressons à la question suivante : quand un sous-shift donné est-il sofique ? Autrement dit, comment prouve-t-on (ou réfute-t-on) la soficité d'un sous-shift ? Si cette question est résolue en dimension 1 (les sous-shifts sofiques en dimension 1 étant similaires aux langages rationnels, le théorème de Myhill-Nerode caractérise la soficité en dimension 1 par comptage du nombre de « contextes »), décrire la frontière entre les sous-shifts multidimensionnels sofiques et effectifs reste un problème ouvert en dynamique symbolique.Cette thèse se divise en deux parties indépendantes, précédées de chapitres préliminaires d'introduction et de définitions des notions étudiées (de dynamique symbolique, calculabilité…). Dans la première partie, nous étudions les ensembles d'extensions des sous-shifts multidimensionnels (qui, informellement, comptent les classes de motifs qui peuvent être librement échangés dans les configurations d'un sous-shift) selon leur (in)calculabilité : en particulier, nous prouvons que les entropies d'extensions des sous-shifts (i.e. le taux de croissance du nombre d'ensemble d'extensions) peuvent être entièrement caractérisées calculablement dans la hiérarchie arithmétique des nombres réels, le niveau précis dépendant de la complexité et des propriétés dynamiques vérifiées par le sous-shift considéré. Dans la seconde partie, nous prouvons une condition suffisante pour la soficité des sous-shifts multidimensionnels s'appuyant sur une quantification de « l'information utile » contenue dans les motifs : plus précisément, nous introduisons une notion de représentation inductive (qui, informellement, décrit l'information échangée par des motifs adjacents d'une taille donnée pour vérifier la validité locale d'une configuration), et nous prouvons qu'admettre des représentations calculables de petites complexité est une condition suffisante pour la soficité d'un sous-shift. Enfin, nous présentons ces résultats comme une complexité de communication sur des coloriages infinis, et argumentons que la complexité de communication non-déterministe forme un cadre riche pour l'étude de la soficité des sous-shifts multidimensionnels.