ANR project: Foundations of Automata Networks

Welcome to the webpage of ANR project FANs. The project started in January 2019 and will finish in December 2022.


Project


Foundations of Automata Networks

Context

An increasing number of interaction systems is being understood as computational processes. At the foundation of these, interactions and dynamics do combine in a fascinating way. Our understanding of such processes sheds light on real interaction systems, omnipresent in physics, in biology, in daily life.

The objective of FANs is precisely to develop further our knowledge of automata networks (ANs), a reference abstract model for such systems, through fundamental and in-depth studies on the characteristics of computational processes that govern them. In other words, FANs aims at “augmenting the theory of ANs”, via approaches from fundamental computer science. Our motivation comes from : 1) the fact that we think that fundamental computer science gives an appropriate framework for the study of such networks, 2) our interest for real life networks, which drives us to study AN per se rather than as a tool for modelling. Indeed, we are convinced that this constructive and innovative approach perfectly fits the objective of finding general laws, necessary for understanding real systems.

Despite the (deliberate) simplicity of ANs, they can at the same time simulate a Turing machine in constant space, catch the natural way of designing interactions, and model their dynamics as observed in real networks. However, even though this model has been introduced in the 1940s, the state of the art assesses a form of paradox between the interest given to ANs from the applicative point of view and the current weaknesses from the theoretical point of view. Yet, it seems essential to boil down this paradox by the development of AN theory, in order to renew applicative fallouts. In this sense, FANs is in favour of a come-back to the roots of AN theory, by paying attention to fundamental problems of dynamics, complexity, and computability.

Main research directions

FANs offers to study the dynamics of ANs with a special concern on the concept of intrinsic simulation. Although largely examined in the framework of cellular automata, tilings and self-assembly, the concept of intrinsic simulation has not yet been seen in depth in the context of ANs. Nevertheless, it is central for the understanding of what founds/builds information transmissions and computations operated in discrete dynamical systems. Thereby, FANs proposes to develop this innovative concept in order to better understand the dynamical and computational complexity of ANs. Moreover, another objective of FANs is to establish formal relations between static characteristics (i.e., their interaction graphs and their local functions) and dynamics (i.e., their transition graphs) of ANs, with a particular care on the links between cycles of interactions and their attractors and basins. Here, we propose to lead works combining dynamical system theory and combinatorics, by improving the existing bound on the number of fixed points of ANs admitting a given interaction graph. Towards this aim, we will consider the influence of negative feedback cycles, which has never been done before. Furthermore, we will initiate studies regarding the counting of complex attractors, which hardly depend on update modes. The latter organise updates over discrete time, and their influence will also be studied in order to better understand causal relations within the dynamics of AN. In the long term, these developments will also surely participate in understanding problems related to the synthesis and composition of such networks, which have strong applicative impacts in biology, on the nowadays key questions of functional modularity in gene regulatory networks and cellular reprogramming.


Members

Consortium

  • Sylvain Sené (head), Professeur des universités, Laboratoire d’Informatique et Systèmes, Université d’Aix-Marseille.

  • Florian Bridoux, PhD student, Laboratoire d’Informatique et Systèmes, Université d’Aix-Marseille.
  • Pierre Guillon, Chargé de recherche, Institut de Mathématiques de Marseille, CNRS.
    Temporarily at Interdisciplinary Scientific Center Poncelet, Moscow, Russia.
  • Kévin Perrot, Maître de conférences, Laboratoire d’Informatique et Systèmes, Université d’Aix-Marseille.
  • Pacôme Perrotin, PhD student, Laboratoire d’Informatique et Systèmes, Université d’Aix-Marseille.
  • Adrien Richard, Chargé de recherche, Laboratoire d’Informatique, Signaux et Systèmes de Sophia Antipolis, CNRS.
    Temporarily at Center for Mathematical Modeling, Santiago, Chile.
  • Guillaume Theyssier, Chargé de recherche, Institut de Mathématiques de Marseille, CNRS.

Local collaborators

  • Nicolas Durbec, PhD Student, Laboratoire d’Informatique et Systèmes, Université d’Aix-Marseille.
  • Antonio E. Porreca, Maître de conférences, Laboratoire d’Informatique et Systèmes, Université d’Aix-Marseille.


Institutions


Events


  • 2019 January 25th
    Kick-off meeting in Marseille (France).

  • 2019 February 15th
    Internal meeting on sequential programming in Marseille (St Charles).

  • 2019 February 25th - March 3rd
    Julio Aracena, Professor at the University of Concepción (Chile), comes to Marseille to visit us.

  • 2019 March 1st
    Internal meeting on simulation definitions in Marseille (St Charles).

  • 2019 March 4th - March 8th
    Kévin Perrot gives a talk on Maximum Fixed Point Problem for the conference AOL’19 in Hanoi (Vietnam), and visits Ha Duong Phan at the Institute of Mathematics of the Vietnam Academy of Science and Technology.

  • 2019 March 11th - March 14th
    Nicolas Durbec presents a poster on Maximum Fixed Point Problem for GDR IM annual days in Orléans (France).

  • 2019 April 2nd
    Internal meeting on complexity questions in Marseille (Luminy).

  • 2019 May 16th - May 17th
    Jacques Demongeot and François Robert, resp. Professor emeritus and former Professsor at Grenoble University, come to Marseille to visit us.

  • 2019 May 18th
    Kévin Perrot gives a popularisation talk on Complexity and Computability - on solving problems with computers at the regional day of association of mathematics teachers in public schools (APMEP) in Marseille (Saint-Charles).

  • 2019 May 20th
    Sylvain Sené gives a popularisation talk on Natural Computation for Life Sciences, and Vice Versa! at the MPCI thematic school 2019 in Marseille (Château-Gombert).


FANs publications


  1. Perrot, Kévin, Marco Montalva-Medel, Pedro P. B. de Oliveira, and Eurico L. P. Ruivo. “Maximum Sensitivity to Update Schedule of Elementary Cellular Automata over Periodic Configurations.” Natural Computing, 2019.   DOI-link   HAL-link  
  2. Bridoux, Florian, Nicolas Durbec, Kévin Perrot, and Adrien Richard. “Complexity of Maximum Fixed Point Problem in Boolean Networks.” In Proceedings of CiE’2019, 11558:132–43. LNCS, 2019.   DOI-link    
  3. Goles, Eric, Fabiola Lobos, Gonzalo A. Ruz, and Sylvain Sené. “Attractor Landscapes in Boolean Networks with Firing Memory.” Natural Computing, 2019. Accepted.      


Related publications