1. Études de la complexité algorithmique des réseaux d'automates
- Author
-
Perrot, Kévin, Perrot, Kévin, Calcul Naturel (CANA), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Aix-Marseille Université, and Olivier Bournez
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Interaction graph ,Systèmes dynamiques discrets (en temps et espace) ,Graphe d'interaction ,[MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS] ,[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS] ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] ,Discrete dynamical systems (in time and space) ,Réseaux d'automates ,Complexité algorithme ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,Automata networks ,Algorithmic complexity - Abstract
Automata networks model all finite discrete dynamics. Each automaton has a state, evolving in discrete time steps, according to the states of other automata. The structure of interactions is described by a graph and local transition functions. A global dynamics is obtained with an update schedule, describing which automata apply their local function to change state, deterministically or nondeterministically. This rich expressivity allows to modelize phenomena observed in nature, where the paradigm of going from local rules to global behavior captures the essence of "complex" systems.An automata network is encoded by the (Boolean) circuits of its local functions. Since space is finite, the whole dynamics can be computed. We intend to understand variants of the model, through characterizing the computational complexities of problems: related to computing the graph of interactions, related to the asymptotic dynamics of a given automata network, related to the asymptotic dynamics of all possible networks on a given structure of interactions, and related to update schedules. It indirectly deals with the capacity to embed computation in different aspects of the model.We will draw key elements on the structure of interactions, the principle of locality, the importance of state alphabets, and encodings. This work will result in long term perspectives, on the extension of some partial information on a network, and the statement of "Rice-like" theorems formalized using model theory., Les réseaux d'automates modélisent toute dynamique discrète finie. Chaque automate possède un état, qui évolue en étapes de temps discrètes, selon l'état des autres automates. La structure des interactions est décrite par un graphe et des fonctions locales de transition. Une dynamique globale est obtenue avec un mode de mises à jour, décrivant quels automates appliquent leur fonction locale pour changer d'état, de façon déterministe ou non déterministe. Cette grande expressivité permet la modélisation de phénomènes observés dans la nature, où le paradigme du passage des règles locales au comportement global capture l'essence des systèmes « complexes ».Un réseau d'automates est encodé par les circuits (booléens) de ses fonctions locales. Puisque l'espace est fini, toute la dynamique peut être calculée. Nous proposons une compréhension des variantes du modèle, à travers la caractérisation des complexités algorithmiques de problèmes: liés au calcul du graphe des interactions, liés à la dynamique asymptotique d'un réseau d'automates donné, liés à la dynamique asymptotique de tous les réseaux possibles sur une structure d'interactions donnée, et liés à plusieurs modes de mises à jour. Il s'agira indirectement d'appréhender la capacité à implémenter du calcul dans les différentes facettes du modèle.Nous dégagerons des éléments clés sur la structure des interactions, le principe de localité, l'importance des alphabets d'états, et les encodages. Ce travail aboutira à des perspectives sur le long terme, guidées par l'extension d'informations partielles sur un réseau, et l'énoncé de théorèmes « à la Rice » formulés grâce à la théorie des modèles.
- Published
- 2022