CE40 - Mathématiques, informatique théorique, automatique et traitement du signal

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

Résumé de soumission

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.

Coordinateur du projet

Laboratoire d'Informatique et Systèmes (Laboratoire public)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

Laboratoire d'Informatique et Systèmes

Aide de l'ANR 187 482 euros
Début et durée du projet scientifique : décembre 2018 - 48 Mois

Liens utiles