Soutenance de thèse de Martín RíOS WILSON

Un réseau d'automates (RA) est un réseau d'entités (les automates) en interaction. Ces automates ont un nombre fini d'états possibles et sont reliés les uns aux autres par une structure de graphe appelée graphe d'interaction. Chaque automate évolue au cours du temps discret en fonction des états de ses voisins dans le graphe d'interaction, ce qui définit un système dynamique. Ce travail de thèse explore deux questions principales: a) quel est le lien entre les propriétés dynamiques et calculatoires d'un RA ? et b) quel est l'impact de la topologie du graphe d'interaction sur la dynamique globale d'un RA ?. Pour aborder la première question, une notion de complexité calculatoire est définie au regard de problèmes de décision liés à la dynamique des RA. De même, une notion de complexité dynamique est définie en termes de l'existence d'attracteurs de période exponentielle. Un lien fort entre ces deux définitions est présenté qui met en exergue le concept de simulation entre familles de RA. Dans ce contexte, la complexité se caractérise d'un point de vue localisé en étudiant l'existence de structures appelées gadgets qui satisfont deux propriétés: i) ils peuvent interagir localement de manière cohérente comme des systèmes dynamiques et ii) ils sont capables de simuler un ensemble fini de fonctions définies sur un ensemble fini. Enfin, la deuxième question est abordée dans le contexte des RA "freezing". Un RA est "freezing" s'il y a un ordre sur les états de telle sorte que l'évolution de l'état de n'importe quel automate ne diminue pas quelle que soit l'orbite. Un problème général de model-checking capturant de nombreux problèmes de décision classiques est présenté. De plus, lorsque trois paramètres de graphe, le degré maximum, la largeur arborescente et la taille de l'alphabet sont bornés, un algorithme parallèle efficace résolvant le problème mentionné est donné. De plus, il est montré que ce problème est peu susceptible d'être FPT (fixed-parameter tractable) lorsque le paramètre de largeur arborescente ou celui de taille de l'alphabet sont considérés comme unique paramètre.

An automata network (AN) is a network of entities, each holding a state from a finite set and related by a graph structure called an interaction graph. Each node evolves according to the states of its neighbors in the interaction graph, defining a discrete dynamical system. This thesis work explores two main questions: a) what is the link between dynamical and computational properties of an AN? and b) what is the impact of the interaction graph topology on the global dynamics of an AN?. In order to tackle the first question a notion of computational complexity of an AN family is defined in terms of the computational complexity of decision problems related to the dynamics of the network. On the other hand, dynamical complexity of a particular AN family is defined in terms of the existence of attractors of exponential period. A strong link between these two last definitions is presented in terms of the notion of simulation between AN families. In this context, complexity is characterized from a localized standpoint by studying the existence of structures called coherent gadgets which satisfy two properties: i) they can locally interact in a coherent way as dynamical systems and ii) they are capable of simulating a finite set of functions defined over a fixed finite set. Finally, the second question is addressed in the context of a well-known family called freezing automata networks. An AN is freezing if there is an order on states such that the state evolution of any node is non-decreasing in any orbit. A general model checking problem capturing many classical decision problems is presented. In addition, when three graph parameters, the maximum degree, the treewidth and the alphabet size are bounded, a fast-parallel algorithm that solves general model checking problem is presented. Moreover, it is shown that the latter problem is unlikely to be fixed-parameter tractable on the treewidth parameter as well as on the alphabet size when considered as single parameters.