Fondements des réseaux d'automates (booléens) – FANs

Les questions posées dans le projet FANs se placent à la frontière des mathématiques discrètes et de l'informatique théorique. De par leur nature (évoquées dans le résumé des enjeux et des objectifs du projet), ces questions appellent à développer des réponses théoriques qui prennent la forme de théorèmes et de démonstrations associées à ces derniers. Pour arriver à obtenir ces réponses, les méthodes et les approches développées jusque là empruntent essentiellement à la théorie des systèmes dynamiques (discrets), à la théorie de la complexité et à la théorie de la calculabilité.

Les résultats obtenus jusque là dans le cadre de FANs relèvent des deux axes mentionnés, l'axe « mathématique » et l'axe « informatique ».
Dans le premier axe, sur le thème de la sensibilité structurelle, entre autres, nous avons obtenu une classification complète des automates cellulaires élémentaires vis-à-vis de leur sensibilité aux modes de mise à jour (MMJ) bloc-séquentiels. Nous avons également montré que compter le nombre de classes d'équivalence de ces MMJ pour un RA donné est un problème #P-complet, et que ces MMJ ne permettent pas de capturer certaines richesses comportementales que d'autres MMJ plus complexes capturent. Sur le thème lié aux attracteurs des RA, (1) nous avons montré que savoir si un IG donné pouvait admettre un RA ayant plus de k points fixes est un problème pouvant être de complexité en temps arbitrairement élevée selon si k est donné en entrée ou non ; (2) nous avons aussi abordé la question du comptage des cycles limites (plus problématique car les cycles limites sont très sensibles aux MMJ) et avons montré qu'étant donné un RA, savoir s'il existe un MMJ bloc-séquentiel tel qu'il admet au moins (resp. pas) un cycle limite de période p est un problème NP-complet (resp. NP^NP-complet).
Dans le second axe, nos efforts se sont concentrés sur la simulation intrinsèque dans les RA (qui vise à faire des liens de correspondance dynamique et de calculabilité entre ces réseaux), et sur des résultats généraux de complexité. Sur la simulation, nous avons notamment montré l'existence de RA évoluant en parallèle qui ne sont pas simulables séquentiellement mais qu'il existe un RA universel d'alphabet 2q pour la simulation asynchrone de tout RA d'alphabet q. Sur la complexité, nous avons démontré des théorèmes de type Rice pour les RA. En particulier, si une propriété sur la dynamique d’un RA peut s’exprimer par une formule en logique du premier ordre, alors sa complexité est soit bornée, soit NP-difficile, soit coNP-difficile.

Outre les questions de la proposition initiale qui demeurent au centre des activités de FANs, les travaux réalisés au cours des deux premières années ouvrent des perspectives pertinentes dans le cadre général du projet. Entre autres, sur le thème de la sensibilité structurelle, les résultats obtenus engagent à développer les analyses relatives à des MMJ plus complexes, dans le cas déterministe comme dans le cas non-déterministe pour lesquels il semble possible de mettre en avant une hiérarchie fondée sur l'expressivité des MMJ. Dans le contexte du comptage des attracteurs, outre les généralisations des problèmes sur lesquels des résultats ont déjà été obtenus, en créant notamment des ponts entre ce thème et les perspectives du thème précédent (autour de MMJ plus complexes), une perspective pertinente est de mener une analyse plus combinatoire pour le comptage en valeur absolue des attracteurs, en nous fondant notamment sur les propriétés structurelles des RA ou de leur GI. Sur le thème de la simulation, de nombreuses questions restent ouvertes autour de la simulation intrinsèque des RA, fût-elle globale, asymptotique, ou spécifiée en fonction de la question elle-même. Cela demande de maintenir l'effort autour d'une survey du concept lui-même dans la littérature qui vise aussi à proposer une définition la plus générale possible de ce concept dans le contexte des systèmes dynamiques à temps discret et d'en proposer des restrictions pertinentes. Enfin, sur le thème plus général de la complexité dans les RA, le théorème de type Rice obtenu sur les propriétés exprimables en logique du premier ordre ouvre naturellement la voie à des extensions à des logiques d'ordre supérieur.

Les travaux de ces deux premières années menés par les membres de FANs ont abouti à la publication (ou à l'acceptation avant fin 2020) de :
- 11 articles dans des journaux internationaux à comité de lecture reconnus, parmi lesquels Advances in Applied Mathematics, Discrete Applied Mathematics, Fundamenta Informaticae Information and Computation, Journal of Theoretical Biology, Natural Computing, Theoretical Computer Science ;
- 8 papiers dans des conférences internationales avec actes et comité de programme reconnues, parmi lesquelles Cellular Automata and Discrete Complex Systems (AUTOMATA, 2020), Computability in Europe (CiE, 2019, 2020), Language and Automata Theory and Applications (LATA, 2021), Theoretical Aspects of Computer Science (STACS, 2021), Theory and Applications of Models of Computation (TAMC, 2020), Theory and Practice of Computer Science (SOFSEM, 2021) ;
- la thèse de F. Bridoux.
La liste détaillée de ces productions est disponible sur le site web du projet.

Les systèmes d'interaction sont de mieux en mieux compris comme des processus informatiques. Aux fondements de ceux-ci, les interactions et la dynamique se combinent de manière fascinante. De notre connaissance de tels processus dépendra notre compréhension des systèmes réels, omniprésents en physique, en biologie, dans notre vie quotidienne.

L'objectif de FANs est précisément de développer la connaissance sur les réseaux d’automates (RA) qui constituent un modèle abstrait de référence de tels systèmes, au travers d'études fondamentales et profondes sur les caractéristiques des processus informatiques qui les gouvernent. Autrement dit, FANs vise à « augmenter la théorie des RA », au moyen d'approches issues de l'informatique fondamentale. Notre motivation vient : 1) du fait que nous pensons que l'informatique fondamentale fournit un cadre approprié pour traiter de tels réseaux, 2) de notre intérêt pour les réseaux réels, qui nous pousse à étudier les RA per se plutôt que comme des outils de modélisation. En effet, nous sommes convaincus que cette approche constructive et innovante (un retour aux fondamentaux) est parfaitement adaptée pour trouver des lois générales, indispensables pour comprendre les systèmes réels.

Malgré la simplicité (délibérée) des RA, ceux-ci peuvent en même temps simuler une machine de Turing en espace constant, capturer la manière naturelle de concevoir les interactions et modéliser leur dynamique telle qu'observée dans les réseaux réels. Cependant, bien que ce modèle ait été introduit dans les années 1940, l'état de l'art force le constat d'une forme de paradoxe entre l'intérêt donné aux RA du point de vue applicatif et les actuelles faiblesses du point de vue théorique. Or, il semble essentiel de réduire ce paradoxe en développant cette théorie pour renouveler les retombées applicatives. En ce sens, FANs appelle à un retour aux racines de la théorie des RA, en s'attachant aux problèmes de dynamique, de complexité et de calculabilité.

FANs propose d'étudier la dynamique des RA en portant une attention particulière sur le concept de simulation intrinsèque. Bien que déjà largement étudié dans le cadre des automates cellulaires, des pavages et de l’auto-assemblage, le concept de simulation intrinsèque ne l’a jamais été en profondeur dans le contexte des RA. Or, il est central pour comprendre les fondements des transmissions d’information et des calculs opérés dans les systèmes dynamiques discrets. Ainsi, FANs propose de développer ce concept innovant afin de comprendre la complexité dynamique et calculatoire des RA. Par ailleurs, un autre objectif de FANs est d'établir des relations formelles entre les caractéristiques statiques (i.e., leurs graphes d’interaction et leurs fonctions locales de transition) et dynamiques (i.e., leur graphe de transition) des RA, en s'attachant en particulier aux liens entre les cycles d'interaction et les attracteurs et leurs bassins. Ici, nous proposons de mener des travaux mêlant théorie des systèmes dynamiques et combinatoire, en améliorant la borne existante du nombre de points fixes des RA admettant un graphe d’interaction donné. Pour ce faire, nous considérerons l’influence des cycles négatifs, ce qui n’a jamais été fait jusque là. Nous poursuivrons ces travaux en initiant des études de comptage d’attracteurs complexes, qui dépendent fortement des modes de mise à jour. Ceux-ci organisent les mises à jour dans le temps discret, et leur influence sera également étudiée pour mieux comprendre les relations causales des dynamiques des RA. À plus long terme, ces développements permettront également de mieux appréhender les problèmes de synthèse et de composition dans ces réseaux, qui ont des portées applicatives réelles en biologie, sur les questions actuellement clés de modularité fonctionnelle des réseaux de régulation et de reprogrammation cellulaire.