Offre de thèse
Compositionalité dans les sous-décalages de type fini
Date limite de candidature
10-05-2025
Date de début de contrat
01-10-2025
Directeur de thèse
JEANDEL Emmanuel
Encadrement
Réunion régulières avec le doctorant.
Type de contrat
école doctorale
équipe
MOCQUAcontexte
La dynamique symbolique en dimension 1 est une modélisation sous forme de mots simplement infinis ou biinfinis de systèmes dynamiques: On code le sytème dynamique par l'ensemble de ses trajectoires une fois discrétisé. Si le système dynamique a de bonnes propriétés (typiquement l'expansivité), la modélisation ne perd aucune information sur le système. Le modèle le plus simple de système dynamique sont ceux dont la modélisation permet d'obtenir un graphe fini, c'est à dire pour lequel l'ensemble des trajectoires peut être transformé en l'ensemble des chemins infinis ou biinfinis sur un graphe fini. On parle alors de sous-décalage de type fini. Une des questions les plus importantes en dynamique symbolique est de déterminer quand deux systèmes sont conjugués (isomorphes), ce qui s'exprime en terme de mots infinis par l'existence d'un automate cellulaire réversible envoyant l'ensemble des trajectoires du premier système sur l'ensemble des trajectoires du deuxième système. Ce problème est résolu pour les systèmes non réversibles (mot simplement infinis) mais est ouvert depuis les années 60 pour les systèmes réversibles (mots biinfinis). --- Symbolic dynamics models dynamical systems using one-sided or two-sided infinite words: the dynamical system is encoded by the set of its trajectories once discretized. If the dynamical system has good properties (typically expansiveness), this modeling retains all the information about the original system. Dynamical systems that are easy to analyse using this method are those whose symbolic representation yields a finite graph—i.e., systems for which the set of trajectories can be transformed into the set of infinite or bi-infinite paths on a finite graph. These are called shifts of finite type. One of the most important questions in symbolic dynamics is to determine whether two such systems are conjugate (isomorphic), which, in terms of infinite words, corresponds to the existence of a reversible cellular automaton mapping the set of trajectories of the first system to the set of trajectories of the second one.. This problem has been solved in the non-reversible case (one-sided infinite words), but remains open since the 1960s for reversible systems (two-sided infinite words).spécialité
Informatiquelaboratoire
LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Mots clés
Dynamique Symbolique, Automates cellulaires, Catégories
Détail de l'offre
Le but de la thèse est de proposer une approche compositionnelle des sous-décalages: Au lieu de considérer des graphes finis, on considère des graphes finis ouverts, i.e., avec entrées et sorties.
Le but de la compositionalité est de pouvoir utiliser des raisonnements du type suivant: Si G1 est conjugué à G2, et G3 conjugué à G4 alors le graphe G obtenu en reliant sorties de G1 aux entrées de G3 est conjugué au graphe obtenu en reliant sorties de G2 aux entrées de G4
Plus précisément, il s'agit de:
- Définir la notion de graphes ouverts et de matrices d'entiers avec bords
- Définir la notion d'automate cellulaire avec bords
- Définir une notion de conjugaison pour les 2 modèles (graphes, sous-décalages, matrices) à travers la notion d'automate cellulaire, compatible avec celle existant sur les graphes non ouverts.
- Définir la notion de sous-décalage avec bords, et démontrer l'équivalence avec les graphes ouverts lorsqu'ils sont de type fini.
-Généraliser les invariants de conjugaison existants (entropie, complexité, groupe de Bowen-Franks) pour les sous-décalages avec bords
- Etablir une structure de catégorie symétrique monoidale pour les sous-décalages avec bords, et établir quels invariants sont fonctoriels.
- Généraliser à d'autres notions d'équivalence, en particulier l'équivalence de flot.
Keywords
symbolic dynamics, cellular automata, category theory
Subject details
The aim of the thesis is to propose a compositional approach to subshifts: instead of considering finite graphs, we consider open finite graphs, i.e., graphs with inputs and outputs. Compositionality enables reasoning of the following kind: if G1 is conjugate to G2, and G3 is conjugate to G4, then the graph G obtained by connecting the outputs of G1 to the input of G3 is conjugate to the graph G' obtained by connecting the outputs of G2 to the inputs of G4. More precisely, the objectives are: - To define the notion of open graphs and of matrices with boundaries. - To define the notion of cellular automata with boundaries - To define a notion of conjugacy for the two models (graphs matrices) via cellular automata, compatible with the existing notion for finite graphs - To define the notion of subshifts with boundaries and prove the equivalence with open graphs in the case of shifts of finite type - To generalize existing conjugacy invariants (entropy, complexity, Bowen–Franks group) to subshifts with boundaries - To establish a symmetric monoidal category structure for subshifts with boundaries, and determine which invariants are functorial - To generalize to other notions of equivalence, in particular flow equivalence
Profil du candidat
Diplôme de M2 en Informatique ou en Mathématiques.
Candidate profile
Masters Degree in Computer Science and/or Mathematics
Référence biblio
Douglas A. Lind and Brian Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, New York, NY, USA, 1995.
Bruce Kitchens, Symbolic Dynamics, Springer, 1988.
Emmanuel Jeandel, Strong Shift Equivalence as a Category Notion, arXiv:2107.10734
David Hillman, Combinatorial spacetimes, Ph.D. thesis, University of Pittsburgh, 1995