Welcome to the webpage of ANR project FANs. The project started in January 2019 and will finish in December 2022.
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.
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.
Sylvain Sené (head), Professeur des universités, Laboratoire d’Informatique et Systèmes, Université d’Aix-Marseille.
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 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).
Julio Aracena, Adrien Richard, and Lilian Salinas. Maximum number of fixed points in AND-OR-NOT networks. Journal of Computer and System Sciences, 80:1175-1190, 2014.
Julio Aracena, Adrien Richard, and Lilian Salinas. Number of fixed points and disjoint cycles in monotone Boolean networks. SIAM Journal on Discrete Mathematics, 31:1702-1725, 2017.
Florian Bridoux, Pierre Guillon, Kévin Perrot, Sylvain Sené, and Guillaume Theyssier. On the cost of simulating a parallel Boolean automata network by a block-sequential one. Proceedings of TAMC’17, LNCS 10185, 112-128, 2017.
Jacques Demongeot, Mathilde Noual, and Sylvain Sené. Combinatorics of Boolean automata circuits dynamics. Discrete Applied Mathematics, 160: 398-415, 2012.
Maximilien Gadouleau and Adrien Richard. Simple dynamics on graphs. Theoretical Computer Science, 628:62-77, 2016.
Tarek Melliti, Damien Regnault, Adrien Richard, and Sylvain Sené. Asynchronous simulation of Boolean networks by monotone Boolean networks. Proceedings of ACRI’16, LNCS 9863, 182-191, Springer, 2016.
Tarek Melliti, Mathilde Noual, Damien Regnault, Sylvain Sené, and Jérémy Sobieraj. Asynchronous dynamics of Boolean automata double-cycles. Proceedings of UCNC’15, LNCS 9252, 250-262, Springer, 2015.
Tarek Melliti, Damien Regnault, Adrien Richard, and Sylvain Sené. On the convergence of Boolean automata networks without negative cycles. Proceedings of AUTOMATA’13, LNCS 8155, 124-138, Springer, 2013.
Mathilde Noual and Sylvain Sené. Synchronism vs asynchronism in monotonic Boolean automata networks. Natural Computing, 17:393-402, 2018.