Résumé :

De nombreux systèmes dynamiques discrets sont influencés par le graphe sur lequel ils opèrent. Dans le cas des réseaux d'automates, il existe un lien fort entre les propriétés de la dynamique (existence et nombre de points fixes, longueur des transients) et des propriétés très étudiées en théorie des graphes : la forte connexité et l'existence de cycles pairs. La largeur arborescente est classiquement connue pour avoir une forte influence sur la complexité de différents problèmes. On peut conjecturer que celle-ci pourrait avoir une forte influence sur la Turing-complétude dans les sous-shifts de graphes. Nous pouvons également nous intéresser à ce qu'il se passerait si nous laissions la dynamique évoluer la structure du graphe sur laquelle elle s'opère. De tels objets, appelés dynamiques causales de graphes, sont la source d'une multitude de questions. Outre leur intérêt en physique théorique où ils permettent d'apporter des éléments de réponse à des questions en cosmologie et dynamique des fluides en tant que modèle physique, ces dynamiques pourraient également apporter des algorithmes parallélisables pour des problèmes classiques en informatique.