Limitation de la complexité de certains invariants des sous-décalages par contraintes dynamiques et structurelles ; Limitation of the Complexity of Some Invariants of Subshifts by Dynamical and Structural Constraints
Titel:
Limitation de la complexité de certains invariants des sous-décalages par contraintes dynamiques et structurelles ; Limitation of the Complexity of Some Invariants of Subshifts by Dynamical and Structural Constraints
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Etant donnés un ensemble fini de symboles et une liste de règles spécifiant lesquels d'entre eux peuvent apparaître côte à côte, on peut construire un ensemble -- possiblement vide -- de lignes infinies de symboles dans les deux directions, obéissant à ces règles, appelées configurations. Un ensemble de configurations est appelé un sous-décalage unidimensionnel, et il s'agit de l'objet mathématique au coeur de la dynamique symbolique. La notion de sous-décalage peut être généralisée en indexant les symboles par Z² -- ce qui revient à paver le plan infini discret -- ou par n'importe quel groupe de type fini. De nombreuses questions peuvent être posées sur les sous-décalages, notamment s'il existe un algorithme capable de déterminer lesquels d'entre eux sont vides à partir de leurs règles ; et pour un sous-décalage non vide, s'il contient beaucoup de configurations, ou certaines particulièrement complexes. Ces questions correspondent à des invariants de conjugaison : le Problème du Domino, l'entropie, l'apériodicité, la complexité arithmétique du langage. Cette thèse, subdivisée en trois parties essentiellement indépendantes, étudie comment tous ces invariants sont affectés sous différentes conditions, et comment certaines contraintes sur les sous-décalages peuvent causer des changements dans leur comportement. Dans la première partie, nous nous intéressons aux attracteurs topologiques des automates cellulaires, qui sont des sous-décalages, et montrons quelle complexité maximale ils peuvent atteindre dans la hiérarchie arithmétique. Dans la deuxième partie, nous fixons des restrictions horizontales sur les sous-décalages bidimensionnels, et souhaitons savoir si le Problème du Domino reste indécidable et quelles sont les entropies possibles pour leurs sous-systèmes de type fini. Dans la troisième partie, nous étendons la définition de sous-décalage aux groupes de type fini, et présentons trois méthodes de constructions distinctes sur les groupes de Baumslag-Solitar, montrant que leur notion d'apériodicité est plus ...