Soutenance de thèse de DONOSO Isabel
Titre de thèse
Synchronisme et asynchronisme dans les réseau d'automates : le cas des automates cellulaires élémentaires.
Synchronism and asynchronism in Automata Networks: The Case of Elementary Cellular Automata.
Résumé de la thèse
Un réseau d'automates est un réseau de nœuds, chaque nœud possède un état appartenant à un ensemble fini. Les nœuds sont reliés les uns aux autres via un réseau décrit par une structure de graphe, que l'on appelle communément graphe d'interaction. L'évolution des état des nœuds au cours du temps (discret) définit un système dynamique. Cette thèse examine l'influence de l'ordre dans lequel les nœuds d'un réseau d'automates mettent à jour leur état, ou mode de mise à jour, a sur la dynamique du système. Nous nous concentrerons sur six types de modes de mise à jour déterministes et périodiques : parallèle (le traditionnel), biparti, séquentiel, bloc-séquentiel, bloc-parallèle et horloges locaux. À cette fin, les automates cellulaires élémentaires (ACE) sont utilisés comme des exemples de réseau d'automates simples et bien connus, capables de modeler des systèmes complexes. Ce sujet est exploré sous trois angles mutuellement complémentaires ; premièrement, en analysant théoriquement l'effet que différents modes de mise à jour ont sur la complexité de la dynamique ; deuxièmement, en étudiant expérimentalement l'impact de différents modes de mise à jour à l'aide de quatre règles illustratives ; et troisièmement, en étudiant la convergence des ACE sous des modes de mise à jour séquentiels.
Dans le premier cas, la longueur des plus longs cycles limites les plus longs est utilisée pour mesurer et comparer la complexité, considérant que des cycles limites plus longs peuvent stocker plus de puissance de calcul, et que, étant donné que la grille est finie, ces cycles peuvent toujours être atteints. À cette fin, des techniques d'analyse des règles élémentaires en conjonction avec le mode de mise à jour correspondant sont développées. Dans le deuxième cas, pour aborder les ACE dont l'analyse théorique demeure ouverte, deux règles chaotiques (90 et 150) et deux règles complexes (54 et 110) sont choisies, dont la variabilité sous différents modes de mise à jour est mesurée à l'aide des notions de densité et d'énergie. Finalement, l'étude de la convergence se concentre sur la recherche des règles qui sont toujours capables d'atteindre un point fixe (quand il existe) lorsque les réseaux sont mis à jour séquentiellement, en présentant les concepts de mode de mise à jour universel et de couverture des modes de mise à jour.
De nouvelles façons de classer les règles élémentaires sont ainsi proposées : en fonction de la longueur maximale de leurs cycles limites et de la façon dont elles varient en changeant les modes de mise à jour, et selon l'existence de modes de mise à jour séquentiels universels et de couvertures.
Thesis resume
Automata networks are collections of nodes, each of which holds a state from a finite set and are related to each other through a network described by a graph structure known as the interaction graph, which defines a discrete dynamical system. This thesis delves into the influence that the order in which the nodes of an automata network are updated, known as the update mode, has over the dynamics of the system. We will focus on six types of deterministic and periodic update modes: parallel (the traditional one), bipartite, sequential, block-sequential, block-parallel and local clocks. For that purpose, elementary cellular automata (ECA) are used as a case study, chosen for being simple and well known examples of automata networks that are capable of modeling complex systems. This subject is explored through three mutually complementary angles; firstly, by analyzing theoretically the effect that different update modes have over the complexity of the dynamics; secondly, by studying experimentally the impact of several update modes using four exemplifying rules; and thirdly, by investigating the convergence of ECA under sequential update modes.
In the first case, the length of the longest limit cycles is used to measure and compare complexity, considering that longer limit cycles can store more computational power and that, given that the grid is finite, these cycles can always be reached. To this end, techniques to analyze elementary rules in conjunction with the corresponding update mode are developed. In the second case, to tackle ECA whose theoretical analysis is unwieldy, two chaotic rules (90 and 150) and two complex rules (54 and 110) are chosen, whose variability under different update modes is measured using the notions of density and energy. Finally, the study of convergence is focused on finding which rules are always capable of reaching a fixed point (when it exists) under sequential update modes, introducing the concepts of universal update mode and covering of update modes.
From where, new ways of classifying elementary rules are proposed: according to the maximum length of their limit cycles and how they vary by changing the update modes, and according to the existence of covering and universal sequential update modes.