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, Laboratoire d’Informatique et Systèmes, Université d’Aix-Marseille (PhD obtained in July 2019).
  • Guilhem Gamard, Postdoc, Laboratoire d’Informatique et Systèmes, Université d’Aix-Marseille.
  • Pierre Guillon, Chargé de recherche, Institut de Mathématiques de Marseille, CNRS.
  • 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.
  • 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.
  • Martín Ríos Wilson, PhD Student, Laboratoire d’Informatique et Systèmes, Universidad de Chile & 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).

  • 2019 July
    Adrien Richard and Sylvain Sené become members of the scientific committee of the International Workshop on Boolean Networks 2020 (IWBN’20) that will take place in 2020 January in Concepcíon, Chile.

  • 2019 September 1st - 2020 June 31st
    Kévin Perrot leads a MATh.en.JEANS group (one year of research with a group of pupils supervised by a math teacher) with lycée Mendes-France (Vitrolles) on Un zéro surprenant… (identity of a finite dynamical system, the sandpile group).

  • 2019 September 1st - 2020 December 31st
    Kévin Perrot visits I3S Lab. at Sophia Antipolis, thanks to his CNRS delegation.

  • 2019 October 10th
    Internal meeting on complexity questions and Rice theorem in Marseille (Luminy).

  • 2019 October 15th
    Internal meeting on simulation definitions in Marseille (Luminy).

  • 2019 October 22nd
    Internal meeting on complexity questions and Rice theorem in Marseille (Luminy).

  • 2019 November 14th
    Participation to the Automata Factory 2 workshop at Universidad Adolfo Ibáñez (Santiago, Chile) of Kévin Perrot (talk on Complexity of attractor problems in Boolean networks) and Pacôme Perrotin (talk on Adding inputs to automata networks).

  • 2019 November 25th - December 6th
    Marco Montalva-Medel, Assistant Professor at the University Adolfo Ibañez (Chile), comes to Marseille to visit us.

  • 2019 November 26th
    Internal meeting on updating modes and clocks in Marseille (Luminy).

  • 2019 November 28th
    Internal meeting on complexity questions and Rice theorem in Marseille (Luminy).

  • 2019 December 10th
    Internal meeting on simulation definitions in Marseille (Luminy).

  • 2019 December 20th
    Internal meeting on simulation definitions in Marseille (St Charles).

  • 2020 January 8th
    Florian Bridoux, and Adrien Richard gave presentations at IWBN’20.

  • 2020 January 16th
    Internal meeting on simulation definitions in Marseille (Luminy).

  • 2020 February 3rd
    Internal meeting on updating modes and complexity in Marseille (St Charles).

  • 2020 February 7th
    Internal meeting on simulation definitions in Marseille (Luminy).

  • 2020 February 18th
    Internal meeting on simulation definitions and complexity in Marseille (Luminy).

  • 2020 March 1st - ...
    COVID-19 pandemic constrains FANs activities.

  • 2020 March 15th - 2020 May 15th
    French COVID-19 1st confinement severely constrains FANs activities.

  • 2020 June 12th
    Internal meeting on complexity questions and Rice theorem in Marseille (St Charles).

  • 2020 June 15th
    Internal meeting on simulation questions in Marseille (St Charles).

  • 2020 July 17th
    Internal meeting on complexity questions and Rice theorem in Marseille (St Charles).

  • 2020 September 1st
    Beginning of the organisation of the joint events AUTOMATA and WAN 2021.

  • 2020 October 30th - 2020 December 15th
    French COVID-19 2nd confinement severely constrains FANs activities.

  • 2020 November 2nd
    Online Meeting on AUTOMATA 2021 scientific organisation.

  • 2020 November 20th
    Online meeting on WAN scientific organisation.

  • 2020 November 27th
    Online participation to the Automata Factory 3 workshop organised by Universidad Adolfo Ibáñez (Santiago, Chile) of Guillaume Theyssier (talk on Expansive automata networks).

  • 2020 November 27th
    Online participation to the SDA2 workshop organised by GREYC lab (Caen, France) of Guillaume Theyssier (talk on Parametrized Complexity of Freezing Dynamics).

  • 2021 February 2nd
    Internal meeting on simulation in Marseille (St Charles).

  • 2021 February 12th
    Internal meeting on simulation in Marseille (St Charles).

  • 2021 February 16th
    Kévin Perrot gives a talk on Some fun around cellular automata at C@fé de l’Association des Doctorants en Sciences et Technologies de l’Information et de la Communication (ADSTIC) (Université Côte d’Azur).

  • 2021 March 12th
    Internal meeting on simulation in Marseille (St Charles).

  • 2021 April 3rd - ...
    French COVID-19 3rd confinement severely constrains FANs activities.

  • 2021 July 12th - 2021 July 17th
    AUTOMATA and WAN 2021


FANs publications


List

  1. Bridoux, Florian. “Intrinsic Simulations and Complexities in Automata Networks.” PhD thesis, Université d’Aix-Marseille, 2019. In French.         eprint-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’19, 11558:132–43. LNCS, 2019.   DOI-link       eprint-link
  3. Richard, Adrien. “Nilpotent Dynamics on Signed Interaction Graphs and Weak Converses of Thomas’ Rules.” Discrete Applied Mathematics 267 (2019): 160–75.   DOI-link       eprint-link
  4. ———. “Positive and Negative Cycles in Boolean Networks.” Journal of Theoretical Biology 463 (2019): 67–76.   DOI-link       eprint-link
  5. Aracena, Julio, Maximilien Gadouleau, Adrien Richard, and Lilian Salinas. “Fixing Monotone Boolean Networks Asynchronously.” Information and Computation 274 (2020): 104540.   DOI-link       eprint-link
  6. Balbi, Pedro P., Enrico Formenti, Kévin Perrot, Sara Riva, and Eurico L. P. Ruivo. “Non-Maximal Sensitivity to Synchronism in Periodic Elementary Cellular Automata: Exact Asymptotic Measures.” In Proceedings of AUTOMATA’20, 12286:14–28. LNCS. Springer, 2020.   DOI-link       eprint-link
  7. Bridoux, Florian, Alfonso Castillo-Ramirez, and Maximilien Gadouleau. “Complete Simulation in Automata Networks.” Journal of Computer and System Sciences 109 (2020): 1–21.   DOI-link       eprint-link
  8. Bridoux, Florian, Maximilien Gadouleau, and Guillaume Theyssier. “On Simulation in Automata Networks.” In Proceedings of CiE’20, 12098:277–88. LNCS. Springer, 2020.   DOI-link       eprint-link
  9. ———. “Commutative Automata Networks.” In Proceedings of AUTOMATA’20, 12286:43–58. LNCS. Springer, 2020.   DOI-link       eprint-link
  10. ———. “Expansive Automata Networks.” Theoretical Computer Science 843 (2020): 25–44.   DOI-link       eprint-link
  11. Demongeot, Jacques, and Sylvain Sené. “About Block-Parallel Boolean Networks: a Position Paper.” Natural Computing 19 (2020): 5–13.   DOI-link       eprint-link
  12. Goles, Eric, Fabiola Lobos, Gonzalo A. Ruz, and Sylvain Sené. “Attractor Landscapes in Boolean Networks with Firing Memory.” Natural Computing 19 (2020): 295–319.   DOI-link       eprint-link
  13. Nguyen, Viet-Ha, Kévin Perrot, and Mathieu Vallet. “NP-Completeness of the Game KingdominoTM.” Theoretical Computer Science 822 (2020): 23–35.   DOI-link       eprint-link
  14. 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 19 (2020): 51–90.   DOI-link       eprint-link
  15. Perrot, Kévin, Pacôme Perrotin, and Sylvain Sené. “On the Complexity of Acyclic Modules in Automata Networks.” In Proceedings of TAMC’20, 12337:168–80. LNCS. Springer, 2020.   DOI-link       eprint-link
  16. Noûs, Camille, Kévin Perrot, Sylvain Sené, and Lucas Venturini. “#P-Completeness of Counting Update Digraphs, Cacti, and Series-Parallel Decomposition Method.” In Proceedings of CiE’20, 12098:326–38. LNCS. Springer, 2020.   DOI-link       eprint-link
  17. Ruivo, Eurico L. P., Pedro P. Balbi, Marco Montalva-Medel, and Kévin Perrot. “Maximum Sensitivity to Update Schedules of Elementary Cellular Automata over Infinite Configurations.” Information and Computation 274 (2020): 104538.   DOI-link      
  18. Bridoux, Florian, Caroline Gaze-Maillot, Kévin Perrot, and Sylvain Sené. “Complexity of Limit-Cycle Problems in Boolean Networks.” In Proceedings of SOFSEM’21, 12607:135–46. LNCS. Springer, 2021.   DOI-link       eprint-link
  19. Gamard, Guilhem, Pierre Guillon, Kévin Perrot, and Guillaume Theyssier. “Rice-like Theorem for Automata Networks.” In Proceedings of STACS’21, 187:32:1–32:17. LIPIcs. Schloss Dagstuhl, 2021.        
  20. Goles, Eric, Pedro Montealegre, and Kévin Perrot. “Freezing Sandpiles and Boolean Threshold Networks: Equivalence and Complexity.” Advances in Applied Mathematics 125 (2021): 102161.        
  21. Perrot, Kévin, Pacôme Perrotin, and Sylvain Sené. “Optimising Attractor Computation in Boolean Automata Networks.” In Proceedings of LATA’21, 12638:68–80. LNCS. Springer, 2021.   DOI-link       eprint-link
  22. ———. “On Boolean Automata Networks (De)Composition.” Fundamenta Informaticae, 2021. Accepted.         eprint-link


Related publications