In this exploratory paper, I will first introduce a notion of stability, more lengthily described in a previous article. In this framework, I will then exhibit an unstable aperiodic tiling. Finally, by building upon the folkloric embedding of Turing machines into Robinson tilings, we will see that the question of stability is undecidable.

The generic limit set of a cellular automaton is a topologically defined set of configurations that intends to capture the asymptotic behaviours while avoiding atypical ones. It was defined by Milnor then studied by Djenaoui and Guillon first, and by Törmä later. They gave properties of this set related to the dynamics of the cellular automaton, and the maximal complexity of its language. In this paper, we prove that every non trivial property of these generic limit sets of cellular automata is undecidable.

We give an explicit and effective construction for rhombus cut-and-project tilings with global n-fold rotational symmetry for any n. This construction is based on the dualization of regular n-fold multigrids. The main point is to prove the regularity of these multigrids, for this we use a result on trigonometric diophantine equations. A SageMath program that computes these tilings and outputs svg files is publicly available in [Lutfalla, 2021].

We prove a sucient condition for the non-existence of a nontrivial Cantor equicontinuous factor in dynamical systems. We study the Coven cellular automaton of three neighbours to show that it does not have a nontrivial Cantor equicontinuous factor. Through this study, we show that the blocking words in this cellular automaton are all of the same form.

State-based opacity is a special type of opacity as a confidentiality property, which describes whether an external intruder cannot make for sure whether secret states of a system have been visited by observing generated outputs, given that the intruder knows complete knowledge of the system’s structure but can only see generated outputs. When the time of visiting secret states is specified as the initial time, the current time, any past time, and at most K steps prior to the current time, the notions of state-based opacity can be formulated as initial-state opacity, current-state opacity, infinite-step opacity, and K-step opacity, respectively. In this paper, we formulate the four versions of opacity for real-time automata which are a widely-used model of real-time systems, and give 2-EXPTIME verification algorithms for the four notions by defining appropriate notions of observer and reverse observer for real-time automata that are computable in 2-EXPTIME.

In this paper, we formalize precisely the sense in which the application of a cellular automaton to partial configurations is a natural extension of its local transition function through the categorical notion of Kan extension. In fact, the two possible ways to do such an extension and the ingredients involved in their definition are related through Kan extensions in many ways. These relations provide additional links between computer science and category theory, and also give a new point of view on the famous Curtis-Hedlund theorem of cellular automata from the extended topological point of view provided by category theory. These links also allow to relatively easily generalize concepts pioneered by cellular automata to arbitrary kinds of possibly evolving spaces. No prior knowledge of category theory is assumed.

We show that a cellular automaton on a mixing subshift of finite type is a von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto its image in the category of sofic shifts and block maps. It follows from [S.-Törmä, 2015] that von Neumann regularity is decidable condition, and we decide it for all elementary CA.

We propose a definition of graph subshifts of finite type that extends the power of both subshifts of finite type from classical symbolic dynamics and finitely presented groups from combinatorial group theory. These are sets of (finite or infinite) graphs that are defined by forbidding finitely many local patterns. The definition makes it not obvious to forbid finite graphs, but we prove that some nontrivial subshifts actually contain only infinite graphs: these are built either by forcing aperiodicity (such as in classical constructions of subshifts of finite type on the grid), or no residual finiteness of the period group.

In this paper, we are interested in classifying the different arising (topological) structures of three-dimensional Turing-like patterns. By providing examples for the different structures, we confirm a conjecture regarding these structures within the setup of three-dimensional Turing-like pattern. Furthermore, we investigate how these structures are distributed in the parameter space of the discrete model. We found twofold versions of so-called “zero-“ and “one-dimensional” structures as well as “two-dimensional” structures and use our experimental findings to formulate several conjectures for three-dimensional Turing-like patterns and higher-dimensional cases.

Boolean networks are discrete dynamical systems where each automaton has its own Boolean function for computing its state according to the configuration of the network. The updating mode then determines how the configuration of the network evolves over time. Many of updating modes from the literature, including synchronous and asynchronous modes, can be defined as the composition of elementary deterministic configuration updates, i.e., by functions mapping configurations of the network. Nevertheless, alternative dynamics have been introduced using ad-hoc auxiliary objects, such as that resulting from binary projections of Memory Boolean networks, or that resulting from additional pseudo-states for Most Permissive Boolean networks. One may wonder whether these latter dynamics can still be classified as updating modes of finite Boolean networks, or belong to a different class of dynamical systems. In this paper, we study the extension of updating modes to the composition of non-deterministic updates, i.e., mapping sets of finite configurations. We show that the above dynamics can be expressed in this framework, enabling a better understanding of them as updating modes of Boolean networks. More generally, we argue that non-deterministic updates pave the way to a unifying framework for expressing complex updating modes, some of them enabling transitions that cannot be computed with elementary and non-elementary deterministic updates.

A Boolean network (BN) with n components is a discrete dynamical system described by the successive iterations of a function f : {0,1}ⁿ → {0,1}ⁿ. In most applications, the main parameter is the interaction graph of f : the digraph with vertex set {1, …,n} that contains an arc from j to i if f_i depends on input j. What can be said on the set G(f) of the interaction graphs of the BNs h isomorphic to f, that is, such that h ⚬ π = π ⚬ f for some permutation π of {0,1}ⁿ ? It seems that this simple question has never been studied. Here, we report some basic facts. First, if n ≥ 5 and f is neither the identity or constant, then G(f) is of size at least two and contains the complete digraph on n vertices, with n² arcs. Second, for any n ≥ 1, there are n-component BNs f such that every digraph in G(f) has at least n²/9 arcs.

Boolean automata networks, genetic regulation networks, and metabolic networks are just a few examples of modeling by discrete dynamical systems (DDS). Unfortunately, in most cases, real phenomena modeled by DDS have very complex dynamics. However, it has been empirically observed that in many cases this complex behavior seems to be the result of the “cooperation” of many simpler systems. Equipping finite discrete dynamical systems with an algebraic structure of semiring provides a suitable context for hypothesis verification on the dynamics of DDS. Indeed, a hypothesis on the systems can be translated into polynomial equations over DDS (with a constant right-hand term). Solutions to these equations provide the validation to the initial hypothesis. The issue is that general equations over DDS are plagued by undecidability. In order to avoid the swamp of undecidability, we study the original equation through some abstractions of the problem (regarding different properties of the possible solutions such as cardinality of sets of states, asymptotic and transient behavior). We will show how one can solve, simplify and intersect them to identify the possible solutions to validate or not an initial hypothesis.

Two natural operations to combine finite, discrete dynamical systems (or, from the opposite perspective, to decompose them into smaller ones) are their alternative and their synchronous execution. By choosing these two operations as sum and product, we obtain a commutative semiring structure. The resulting algebra is quite complex; for instance, most systems are irreducible, but those that are reducible sometimes admit multiple factorisations into irreducibles. We present some results related to the resolution of polynomial equations on the semiring of dynamical systems, which turns out to be undecidable in general, and NP-complete even for linear equations. Furthermore, we describe some recent research on the existence of prime dynamical systems; these are systems that, whenever they appear in the decomposition of a system, they necessarily appear in all the others as well, and are thus fundamental building blocks. We do not know yet if prime systems exist, or even if there exists a computable primality test, but several interesting classes of systems have been proved to be non-prime, including systems only consisting of limit cycles (which includes the asymptotic behaviour of any dynamical system).

The concept of simulation between computational models appears in many works in computability, complexity, dynamics… with a heterogeneous level of explicitness. We will discuss some examples appearing in the literature, distinguish them according to some properties, and propose a general framework that can be refined into many such examples.

Our work addresses the synthesis of Boolean networks from constraints on their domain and emerging dynamical properties of the resulting network. The synthesis is expressed as a Boolean satisfiability problem, described as a logic program containing both the modelling formalism (Most Permissive Boolean network, MPBN) and the data on the biological process (static and dynamical knowledge : prior knowledge network, experimental measurement dynamics, observations on the reachable phenotypes depending on conditions…). We enable the modelling of processes implying bifurcations as in cell differentiation, thanks to the implementation of constraints in Answer-Set Programming that address the notion of trajectory (succession of changes in gene state), non-reachability (bifurcating event) and stability (differentiated cell). To illustrate the method, I present an application leveraging scRNA-seq data as dynamical knowledge for the modelling. This example notably shows that, by facing dynamical data with a large prior knowledge network, the method allows to retain the essential interactions to reproduce the behaviors.

Network models of cell signaling and regulation are ubiquitous because of their ability to integrate the current knowledge of a biological process and test new findings and hypotheses. An often asked question is how to control a network model and drive it towards its dynamical attractors (which are often identifiable with phenotypes or stable patterns of activity of the modeled system), and which nodes and interventions are required to do so. In this talk, we introduce two recently developed network control methods - feedback vertex set control and stable motif control - that use the graph structure of a network model to identify nodes that drive the system towards an attractor of interest (i.e., nodes sufficient for attractor control). Feedback vertex set control makes predictions that apply to all network models with a given graph structure and stable motif control makes predictions for a specific model instance, and this allows us to compare the results of model-independent and model-dependent network control. We apply these methods to various biological network models and discuss the aspects of each method that makes its predictions dependent or independent of the model. In addition, and if time permits, I will talk about some of the mechanistic models of oncogenic signaling I have worked on (the epithelial-to-mesenchymal transition in liver cancer and drug resistance in breast cancer) and the insights we have learned from them.

An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node depending on its neighbors. The global dynamics of the network is then induced by an update scheme describing which nodes are updated at each time step. We study how update schemes can compensate the limitations coming from symmetric local interactions. Our approach is based on intrinsic simulations and universality and we study both dynamical and computational complexity. By considering several families of concrete symmetric AN under several different update schemes, we explore the edge of universality in this two-dimensional landscape. On the way, we develop a proof technique based on an operation of glueing of networks, which allows to produce complex orbits in large networks from compatible pseudo-orbits in small networks.

Boolean networks are often used as modelling tools, for instance in the investigation of biological systems. Regulations between Boolean species are encoded in interaction graphs, and the resulting qualitative behaviours are captured in state transition graphs describing the possible dynamics according to different interpretations (e.g. synchronous or asynchronous). One drawback of adopting a Boolean approach is that regulation thresholds are inevitably “squashed”, and trajectories that are visible in multilevel or continuous modelling frameworks can be lost. In this talk, I will discuss some properties of a class of Boolean networks that can be obtained by adding “buffer” variables to separate the regulation thresholds. The asynchronous dynamics of these extended networks can recover many behaviours seen in more refined models. We will see how the associated state transition graphs relate to dynamics arising from other interpretations, e.g. generalised asynchronous or most permissive dynamics, and discuss some of their properties. We will see, in particular, that if all thresholds are separated and all cycles in the interaction graph admit at least one buffer, then the asynchronous attractors are in one-to-one correspondence with the minimal trap spaces. I will conclude by outlining some open questions on buffer-extended Boolean networks.

Given a fixed integer k, the maximum (minimum) fixed point problem is the following: given a signed graph G, is there a Boolean network with at least (most) k fixed points and with G as interaction graph? Firstly, we prove that the maximum fixed point problem is NP-complet if k > 1 and polynomial otherwise. Secondly, we prove that the minimum fixed point problem is NEXPTIME-complet for every k. We also present complexity results when k is a part of the input.

We address the complexity of the problem of determining if a given conjunctive Boolean network has a limit cycle for some block-sequential update schedule. We prove that this problem is NP-complete even in the case of only sequential schemes.