**Note:** *all times indicated in the schedule are in the CEST time zone (UTC+2)*

Time slots:

- 1 hour = 50 minutes talk + 5 minutes for questions + 5 minutes for break
- 45 minutes = 35 minutes talk + 5 minutes for questions + 5 minutes for break
- 30 minutes = 20 minutes talk + 5 minutes for questions + 5 minutes for break

Slides are available next to the abstracts by clicking on the title of each talk.

You can find the Automata invited and regular papers in the OASIcs proceedings and the Automata exploratory papers in the HAL collection.

*09:30 - presentation of the week*

and scribbles

The fixed point construction is a method for designing tile sets and cellular automata with highly nontrivial dynamical and computational properties. It produces an infinite hierarchy of systems where each layer simulates the next one. The simulations are implemented entirely by computations of Turing machines embedded in the tilings or spacetime diagrams. We present an overview of the construction and list its applications in the literature.

*11:00 - Break*

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 Besicovitch and Weyl pseudo-distances are shift-invariant pseudometrics on the set of infinite sequences, that enjoy interesting properties and are suitable to study the dynamics of cellular automata. They correspond to the asymptotic behavior of the Hamming distance of longer and longer prefixes or factors. In this paper we replace Hamming distance by that of Levenshtein, with the aim of studying symbolic dynamical systems in their associated quotient space. We prove that every cellular automaton is Lipschitz with respect to this new distance, moreover, the shift-map is exactly the identity over those spaces. In addition, we show that, in the Besicovitch and Weyl spaces, substitutions are well-defined essentially only when they are uniform. However, we prove that in the new spaces associated to the Levenshtein distance, all substitutions are well-defined, and furthermore Lipschitz. Finally, we propose a general definitions of pseudo-metrics depending on the distance.

*12:30 - Lunch*

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.

The expressive power of the class Conj of conjunctive languages, i.e. languages generated by the conjunctive grammars of Okhotin, is largely unknown, while its restriction LinConj to linear conjunctive grammars equals the class of languages recognized by real-time one-dimensional one-way cellular automata. We prove two weakened versions of the open question Conj ⊆? RealTime1CA, where RealTime1CA is the class of languages recognized by real-time one-dimensional two-way cellular automata:

1) it is true for unary languages;

2) Conj ⊆ RealTime2OCA, i.e. any conjunctive language is recognized by a real-time two-dimensional one-way cellular automaton. Interestingly, we express the rules of a conjunctive grammar in two Horn logics, which exactly characterize the complexity classes RealTime1CA and RealTime2OCA.

*16:00 - Break*

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.

Mean and diam-mean equicontinuity are dynamical properties that have been of use in the study of non-periodic order. We show that the Pacman automaton is not almost diam-mean equicontinuous (it is already known that it is almost mean equicontinuous).

*18:15 - annual meeting of WG1.5* (open to members of WG1.5)

*19:30 - Dinner*

It is well known that the class of regular languages coincides with the class of languages recognized by finite automata. Nevertheless, many other characterizations of this class in terms of computational devices and generative models are present in the literature. For example, by suitably restricting more powerful models such as context-free grammars, pushdown automata, and Turing machines, it is possible to obtain formal models that generate or recognize regular languages only. These restricted formalisms provide alternative representations of regular languages that may be significantly more concise than other models that share the same expressive power. The goal of this work is to provide an overview of old and recent results on these formal systems from a descriptional complexity perspective, that is by considering the relationships between the sizes of such devices. We also present some results related to the investigation of the famous question posed by Sakoda and Sipser in 1978, concerning the size blowups from nondeterministic finite automata to two-way deterministic finite automata

*10:30 - Break*

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.

Though iterated maps and dynamical systems are not new to combinatorics, they have enjoyed a renewed prominence over the past decade through the elevation of the subfield that has become known as dynamical algebraic combinatorics. Some of the problems that have gained popularity can also be cast and analyzed as finite asynchronous cellular automata (CA). However, these two fields are fairly separate, and while there are some individuals who work in both, that is the exception rather than the norm. In this article, we will describe our ongoing work on toggling independent sets on graphs. This will be preceded by an overview of how this project arose from new combinatorial problems involving homomesy, toggling, and resonance. Though the techniques that we explore are directly applicable to ECA rule 1, many of them can be generalized to other cellular automata. Moreover, some of the ideas that we borrow from cellular automata can be adapted to problems in dynamical algebraic combinatorics. It is our hope that this article will inspire new problems in both fields and connections between them.

*12:30 - Lunch*

We consider reversible and surjective cellular automata perturbed with noise. We show that, in the presence of positive additive noise, the cellular automaton forgets all the information regarding its initial configuration exponentially fast. In particular, the state of a finite collection of cells with diameter n becomes indistinguishable from pure noise after O(log n) time steps. This highlights the seemingly unavoidable need for irreversibility in order to perform scalable reliable computation in the presence of noise.

*15:30 - Break*

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.

Little is known about the dynamics of k-ary (binary, ternary, quaternary, quinary, etc.) reversible number-conserving cellular automata. Here, we present some preliminary results in the case of seven states. We examine one of the most complex seven-state reversible and numberconserving rules and provide a full description of its dynamics.

*17:45 - Break*

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.

A two-state Cellular Automaton (CA) with neighborhood N is called an Interval LifeLike Freezing Cellular if the local rule f can be defined from an interval I ⊂ [0,…,|N|], such that: (1) when a cell c is in state 0, it becomes 1 if and only if the number of neighbors of c in state 1 belongs to I. (2) if c is in 1, then it remains in state 1 independently on the states of their neighbors. Recently (Goles et al. Information and Computation 2020), an exhaustive study of the dynamics and complexity of ILLFCA was carried out in the von Neumann neighborhood, where the complexity and dynamics of such CAs were classified in five groups, namely Trivial, Algebraic, Topological, Fractal and P-Complete rules. In this exploratory paper, we propose a follow-up of the later research, extending it to ILLFCA equipped with the Moore neighborhood. Interestingly, this class contains the famous Life-without-Death, also known as the freezing version of Conway Game of Life. In fact, we show that the family of ILLFCA with Moore neighborhood has a rich diversity of rules, some of them not classifiable in the previous groups.

*19:30 - Dinner*

A Boolean network is a mapping f : {0,1}^{n} → {0,1}^{n}, which can be used to model networks of n interacting entities, each having a local Boolean state that evolves over time according to a deterministic function of the current configuration of states. In this paper, we are interested in disjunctive networks, where each local function is simply the disjunction of a set of variables. As such, this network is somewhat homogeneous, though the number of variables may vary from entity to entity, thus yielding a generalised cellular automaton. The aim of this paper is to review some of the main results, derive some additional fundamental results, and highlight some open problems on the dynamics of disjunctive networks. We first review the different defining characteristics of disjunctive networks and several ways of representing them using graphs, Boolean matrices, or binary relations. We then focus on three dynamical properties of disjunctive networks: their image points, their periodic points, and their fixed points. For each class of points, we review how they can be characterised and study how many they could be. The paper finishes with different avenues for future work on the dynamics of disjunctive networks and how to generalise them.

*10:15 - Break*

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}^{n} → {0,1}^{n}. 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}^{n} ? 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^{2} arcs. Second, for any n ≥ 1, there are n-component BNs f such that every digraph in G(f) has at least n^{2}/9 arcs.

Automata networks are often conceived as a finite generalization of cellular automata. In this paper, we prove that the limit dynamics of any finite automata network under the parallel update schedule correspond exactly to the fixed points of so-called strictly one-way cellular automata. This correspondence is proven to be exact, as any strictly one-way cellular automata can be transformed into a corresponding automata network, where the attractors of the latter correspond exactly to the fixed points of the former. This transformation is easy to operate by using output functions which have been developed in the author’s previous works.

*12:30 - Lunch*

Here is the booklet containing the program and abstracts for WAN talks.

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).

I will begin this talk with a problem from dynamical algebraic combinatorics about toggling independent sets, and frame it as a finite asynchronous cellular automata using ECA rule 1. In analyzing the dynamics, we find two local invariants that define bijections of the “live entries” in the orbits. This defines a simply transitive action of an infinite abelian group. In other words, it endows the live entries with the structure of a Cayley diagram. By studying this action, and using the theory of covering spaces from algebraic topology (which I will not assume prior knowledge of), we are able to classify many combinatorial properties and relationships about the structure of the orbits. Happily, this is all a special case of a more general theory, applicable to other automata networks and combinatorial dynamical systems, which seems to be mostly unexplored. I will pose a number of interesting avenues for future research, in hopes to entice members of the audience. Though it will not be necessary to follow this talk, I or (most likely) a colleague will give a survey talk at AUTOMATA about the connections between dynamical algebraic combinatorics and cellular automata, which will give this problem more context and motivation. Both talks will be filled with lots of examples, colorful pretty pictures, and puns.

*16:15 - Break*

18:30 - **tribute: Michel Morvan**

*19:30 - Dinner (daurade, fumet de poisson)*

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.

An automata network is a finite graph where each node holds a state from some finite alphabet and is equipped with an update function that changes its state according to the configuration of neighboring states. More concisely, it is given by a finite map f : A^{n} → A^{n}. In this presentation, we will show how some automata networks can or cannot be simulated by some other automata networks with a prescribed update mode. When we consider non-Boolean alphabets and for any network size, we show that there are intrinsically non-sequential transformations (i.e. which cannot be obtained as a composition of sequential updates of some network). We also conjecture that any network of size at least 3 with a Boolean alphabet can be computed sequentially. Moreover, we show that there is no universal automaton network that can produce all non-bijective functions via compositions of sequential updates. Eventually, we show that there are universal automata networks for sequential updates if one is allowed to use a larger alphabet and then use either projection onto or restriction to the original alphabet.

*10:45 - Break*

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 controllability is a major challenge in network medicine. The problem is to rewire the molecular network for reprogramming the cell fate. The reprogramming action is considered as a control usually performed once. However, in some cases, a therapy has to follow a time-scheduled drug administration protocol. Furthermore, some diseases are induced by a sequence of mutations leading to a sequence of actions on molecules. In this paper, we extend the single control action method by investigating the sequential control of Boolean networks. We present a novel theoretical framework for formal study of control sequences, leading to algorithms resolving the PSPACE-hard problem of inferring minimal parsimonious control sequences under the synchronous dynamics.

*12:15 - Free time*

*12:30 - Lunch*

14:00 - **Working sessions** (complexity, combinatorial dynamics, updating modes, modelling…) only onsite

*16:00 - Break*

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.

We address the problem of determining the dynamical behaviors of synchronous conjunctive networks which can be simulated by some conjunctive network with a block-sequential schedule. In particular, we show a polynomial algorithm that given a conjunctive network N and a scheme s, returns a conjunctive network N’ (if it exists) such that N’ updated with s has the same dynamical behavior that N synchronously updated.

*18:15 - Free time*

*19:30 - Dinner*

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 S a Boolean finite dynamical system (FDS), and f an isometry of the hypercube, we consider the conjugated FDS φ = f ⚬ S ⚬ inv(f). This conjugate conserves all the dynamical properties of S. Moreover, the regulatory graphs of two conjugated FDS are similar: they have the same topology; edges may switch their signs, but signs of circuits remain unchanged. The logical rules may be modified; for example, logical operators OR and AND may be interchanged between two conjugated FDS, but not OR and XOR. The group of all the isometries of the hypercube then defines classes of Boolean FDS, gathering all the conjugates of a given Boolean FDS, in other words gathering all the isometric dynamics. Thus, we classify the set of Boolean FDS on the basis of those isometries. We can then restrict the dynamical analysis of all the Boolean FDS to one representative per class, and thereby considerably restrict the dynamical analysis of all the Boolean FDS. Relying on invariants properties, we propose a constructive method to provide, given a FDS, a representative regulatory graph of its class of FDS under isometries, that fits the addressed questions. We illustrate the efficiency of the method in concrete situations. For instance, the analysis of well-known motifs is strongly improved thanks to the reduction of the space to explore.

*10:45 - Break*

In this talk, we’ll show that testing properties on the transition graph of an automata network, given the network itself as input, is algorithmically hard as soon as the considered property is nontrivial. This echoes the Rice theorem: any property of the function computed by a Turing machine, given the machine itself machine as input, is algorithmically undecidable as soon as the considered property is nontrivial. Of course, a metric ton of fine print is missing here: I haven’t said what is a “property”, what is “algorithmically hard”, and what is “nontrivial”. Come to the talk, and you’ll know.

*12:00 - Free time*

*12:30 - Lunch*

14:00 - **Working sessions** (complexity, combinatorial dynamics, updating modes, modelling…) only onsite

*16:00 - Break*

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.

Update digraphs are the convenient objects to discuss block-sequential update schedules (ordered partitions of the automata set). We will first see that counting update digraphs is #P-hard in general (with an introduction to counting classes), but can be done in polynomial time on graphs of treewidth 2 (series-parallel). Fixed points are invariant under block-sequential update schedules, but limit-cycles are not. We will see a related problem complete for NP^{NP}, one level above NP in the polynomial hierarchy.

*18:15 - Free time*

*19:00 - Dinner*

09:30 - **Working sessions** (complexity, combinatorial dynamics, updating modes, modelling)

11:30 - **Working sessions restitution**

*12:30 - Happy formal ending and picnic*