Foundations of (Boolean) automata networks – FANs

The questions raised by the FANs project lie at the frontier between discrete mathematics and theoretical computer science. By their nature (mentioned in the summary of the challenges and objectives of the project), these questions call for the development of theoretical answers that take the form of theorems and demonstrations associated with them. To obtain these answers, the methods and approaches developed so far mainly borrow from (discrete) dynamical system theory, complexity theory and computability theory.

The results obtained so far within the framework of FANs fall under the two axes mentioned, the “mathematical” axis and the “computer science” axis.
In the first axis, on the theme of structural sensitivity, among others, we obtained a complete classification of elementary cellular automata with respect to their sensitivity to block-sequential updating modes (UMs). We have also shown that counting the number of equivalence classes of these UMs for a given AN is a #P-complete problem, and that these UMs do not capture certain behavioral varieties that other more complex UMs capture. On the topic related to the attractors of ANs, (1) we have shown that knowing if a given IG could admit an AN having more than k fixed points is a problem that can be of arbitrarily high time complexity depending on whether k is given as input or not ; (2) we also addressed the question of counting limit cycles (more problematic because limit cycles are very sensitive to UMs) and showed that, given an AN, knowing whether there is a block-sequential UM such as it admits at least a (resp. no) limit cycle of period p is an NP-complete problem (resp. NP^NP-complete).
In the second axis, our efforts have focused on intrinsic simulation in ANs (which aims to make dynamical correspondence and computability links between these networks), and on general results of complexity. About simulation, we have in particular shown the existence of ANs evolving in parallel which cannot be simulated sequentially but that there is a universal AN of alphabet 2q for the asynchronous simulation of any AN of alphabet q. About complexity, we have proved Rice-type theorems for ANs. In particular, if a property on the dynamics of an AN can be expressed by a formula in first order logic, then its complexity is either bounded, or NP-difficult, or coNP-difficult.

In addition to the questions of the initial proposal which remain at the center of FANs activities, the work carried out during the first two years opens up relevant perspectives within the general framework of the project. Among other things, on the theme of structural sensitivity, the results obtained encourage the development of analyzes relating to more complex UMs, in the deterministic as well as in the non-deterministic case for which it seems possible to put forward a hierarchy based on the expressiveness of UMs. In the context of attractor counting, in addition to generalizations of the problems on which results have already been obtained, notably by creating bridges between this theme and the perspectives of the previous theme (around more complex UMs), a relevant perspective is to to carry out a more combinatorial analysis for the counting in absolute value of the attractors, by basing ourselves in particular on the structural properties of the ANs or their IGs. On the theme of simulation, many questions remain open around the intrinsic simulation of ANs, be it global, asymptotic, or specified according to the question itself. This requires maintaining the effort around a survey of the concept itself in the literature which also aims to propose the most general possible definition of simulation in the context of dynamical discrete-time systems and to propose relevant restrictions of it. Finally, on the more general theme of complexity in AR, the Rice-type theorem obtained on properties expressible in first-order logic naturally opens the way to extensions to higher-order logics.

The work of these first two years carried out by the members of FANs resulted in the publication (or the acceptance before the end of 2020) of:
- 11 articles in recognized international peer-reviewed journals, including Advances in Applied Mathematics, Discrete Applied Mathematics, Fundamenta Informaticae Information and Computation, Journal of Theoretical Biology, Natural Computing, Theoretical Computer Science;
- 8 papers in recognized international conferences with proceedings and program committee, including 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);
- the thesis of F. Bridoux.
The detailed list of these productions is available on the project website.

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.