I like to use combinatorial tools to understand the long-term behavior of dynamical systems. As far as I am concerned, a dynamical system is a couple (X,T) where X is a set of configurations (the possible “states” in which the system can be) and T:X→X is a transition function (that takes you to one configuration to the “next one”). For instance, if the system at hand is a Turing machine, X will be the set of triples (head position, control state, tape contents) and T will be the function corresponding to the transition table of the machine.
“Long-term behavior” means that my systems do not terminate. This makes sense, even in computer science: many programs have to run for as long as needed, with no foreseeable termination. Think: operating systems, SMTP servers, autopilots, and the like. Reasonable questions on such systems are:
Formally speaking, if x∈X is a configuration, we call the sequence x, T(x), T²(x), T³(x), …, the trajectory of x. In computer science terms, it is the “execution” of the system starting at x. As you can see, all the questions above can be formalized as questions about the set of possible trajectories of the system at hand.
Now, how do we answer those questions? They don't look that combinatorial so far. If we can partition X into two pieces X₁⨆X₂ (to fix the ideas, think: X₁ is the set of configurations where the system works, and X₂ is the set of configurations where it fails), then we can project each trajectory on a right-infinite word over alphabet {1,2}. When the partition is well-chosen, those right-infinite words retain enough information to answer the questions we want. For instance, in the illustration below, the right-hand trajectory converges to an attractor, and this is appears in its encoding: the word is eventually periodic (and even eventually monochrome).
My general goal is use this idea in two original ways.
The Kari tileset is an aperiodic set of 14 Wang tiles published in 1996. It is designed to embed a function f:ℝ→ℝ, which has aperiodic orbits, into tiles. In such a tiling, each line is supposed to encode a real number x, and local constraints enforce that the line above encodes f(x). However, real numbers are not encoded using the standard, positional representation; rather, they are written in balanced representation. Not only that construction broke the record of the smallest aperiodic tileset from its time, it also was the first aperiodic tileset not built around a substitution. In other terms, the Kari tileset seemed not self-similar, while all its predecessors were. Still, two questions remained.
In 2014 I proved, with Bruno Durand and Anaël Grandjean, the two following results.
Theorem. In Kari tilings, each line has a well-defined average.
This implies no emergent behavior. In particular, we can see all Kari tilings are codings of trajectory of the function f:ℝ→ℝ, viewed as a dynamical system. Instead of coding into symbols, however, each point is encoded into lines of symbols.
Theorem. The set of Kari tilings has nonzero topological entropy.
Since auto-similar tilesets yield sets of tilings with zero topological entropy, we have a separation.
A finite word q is a quasiperiod of an infinite word w if and only if w is covered with copies of q, possibly overlapping. An infinite word may have several, or even infinitely many quasiperiods (the Fibonacci word, for instance). In the latter case, we say that the word is multi-scale quasiperiodic. On finite words, quasiperiodicity is linked with bioinformatics. On infinite words, it is linked to Sturmian words, substitutions, and questions of factor complexity and topological entropy. Even though there's a rich literature on quasiperiodic words, there were no general method to determine the set of quasiperiods of a given infinite word. In 2016, I proved with Gwenaël Richomme that:
Theorem. The set of quasiperiods of an infinite word w only depends on its set of right-special prefixes and prefixes whose square is a factor of w.
We don't need the definitions of right-special factors and square factors here. The point is that those types of prefixes are simple, natural, and well-studied elsewhere in combinatorics on words. The characterization above is explicit, which enables the design of algorithms to determine quasiperiods on classes of computable infinite words. Moreover,
Theorem. Standard Sturmian words can be defined in terms of quasiperiods.
Intuitively, standard Sturmian words are those with “the largest” amount of quasiperiods after periodic words. Besides, they are a classical subfamily of Sturmian words, subject of a wealth of literature. That result thus reinforces the idea that quasiperiodicity is a natural notion of symmetry over infinite words.
With Florian Barbero and Anaël Grandjean, I proved in 2020 that:
Theorem. If w is a biinfinite word (infinite both to the left and to the right), its set of quasiperiods can be expressed from its set of right-special, left-special, and square factors.
This is not just a trivial generalization of the previous results. In a biinfinite word, there is no concept of “prefix”, and that absence has deep consequences on the combinatorics of the problem. We had to develop new tools and ideas to prove that result. Moreover,
Theorem. The set of quasiperiods of a biinfinite Sturmian word can be expressed from its set of bispecial factors.
We started the study of biinfinite quasiperiodic words because the origin in right-infinite words kept us from stating some questions of interest. Those questions were designed to lead to results on two-dimensional words.
An infinite picture is a two-dimensional word, infinite in four directions (up, down, left, right). A block is a finite, rectangular 2D word. A block q is a quasiperiod of an infinite picture w if and only if w is covered with occurrences of q, possibly overlapping. The study of quasiperiodic infinite pictures was initially motivated by a careful observation of Kari tilings, which seemed to have two-dimensional quasiperiodic behavior. However, that notion being new, we first have to answer to all the natural questions. With Gwenaël Richomme, I proved in 2015:
Theorem. For all block q, either:
There is a simple combinatorial condition to tell which case occurs. Intuitively, the first case covers the vast majority of the blocks (for the second case, think: q is a single letter). The key ingredient of the proof is to start from q, and use it to build several “tiles” that we can use to tessellate the plane. If the construction work, then we can easily produce chaotic tessellations and we get the first case. If it doesn't, then we can prove that q-quasiperiodic pictures are periodic.
Besides, the concept of multi-scale coverability also generalizes.
Theorem. Any multi-scale quasiperiodic picture has zero topological entropy and converging factor frequencies. Besides, there exist such pictures that are aperiodic.
Unfortunately, understanding the combinatorics in Kari tilings would require to generalize those results to non-rectangular quasiperiods. However, 2D quasiperiodicity is not only useful for Kari tilings: those results were also the starting point of another theorem. In 2017, with Gwenaël Richomme, Jeffrey Shallit and Taylor J. Smith, I proved the following statement.
Theorem. If a finite picture can be tiled by two blocks A and B in two different ways, then A and B are powers of a same block C.
That result is a generalization of the Lyndon-Schützenberger theorem, a classical result of combinatorics on words, to pictures.
An automata network is a finite graph where each node is a finite automaton. There is no external input: each automaton reads the current state of its inbound neighbors to update itself. As far as I am concerned, all the automata of a network update synchronously and in parallel. Automata networks are thus a generalization to cellular automata to arbitrary “grids”, where each cell possibly has a different update function. That model was initially introduced in theoretical biology to model neural networks and dynamics of genetic regulation, but it was since used in engineering, control theory and distributed algorithmics.
For instance, we could have two automata A₁ and A₂, both with Σ={0,1,2}. Let A₁(a₁, a₂)= a₁+1 if a₁≠2, and a₁-1 otherwise. Let A₂(a₁, a₂)= a₂+1 if a₁≠2, and a₂-1 otherwise. An automata network with those update functions is displayed below, along with its dynamics. (The doubly-boxed nodes of the dynamics are limit configurations.)
When we need to give an automata network as input to an algorithm, we give its interaction graph plus one boolean circuit for each finite automaton. This is consistent with applications, as well as with the intuition: in an automata network, each node is a “tiny computer” on a network, and we get the “source code” of the program running on each node.
With Pierre Guillon, Guillaume Theyssier and Kévin Perrot, we proved in 2021 that:
Theorem.
Any question expressible in first-order logic about the dynamics of deterministic automata networks is either
O(1), or NP-hard, or coNP-hard.
This also holds for first-order questions about the limit dynamics of deterministic networks.
Both these statements still hold if we are restricted to bijective automata networks.
Note that, in the theorem above, the question is fixed once and for all, it is not part of the input. If we require the first-order formula to be part of the input instead, then the problem becomes PSPACE-complete. Besides, if N is a level of the polynomial hierarchy, then there exist a first-order question that is N-hard in this context.
The main ingredient of the proof is the following: deterministic automata networks have finitely many possible configurations. Therefore, for pumping reasons, the trajectory of each configuration ends up in a cycle. This implies that the transition graph (the graph of the dynamics, where each vertex is a configuration of the system and each edge is a transition) has a very specific shape. Namely, each connected component has a central cycle, and each node of that cycle is the root of an upwards tree. Thanks to Fraïssé, we know that there are finitely many classes of elementary equivalence for first-forder logic if we fix the number of quantifiers of our formulae. Thus we can collapse each tree on its elementary equivalence class, and turn the transition graph of a deterministic automata network into a collection of cyclic words over a finite alphabet. The rest is (hard) combinatorial work, thus I see that collapse as a trajectory coding.
The surprising thing about this theorem is that we have a dichotomy: if P≠NP, then it is not possible to express in first-order logic a polynomial-time testable question on the dynamics of deterministic automata networks. There is more.
Theorem.
Any effectively nontrivial property of limit sets of automata networks is PSPACE-complete.
Testing whether an automata network has “many” limit configurations is either PSPACE-complete or coNP-hard (but Σ₃), depending on the definition of “many”.
Finally, the first hardness result can be generalized in two directions.
Theorem. Any property expressible in Monadic Second-Order logic (MSO) on the dynamics of nondeterministic automata netowrks is either O(1), or NP-hard, or coNP-hard.
The generalization to nondeterminism is not a trivial thing. For instance, the question: “is this network deterministic?” can be expressed in first-order logic (and a fortiori in MSO). It is O(1) if we restrict ourselves to deterministic automata networks, but at least NP-hard in general. Thus we needed new ideas and tools both for the generalization to nondeterminism and to MSO.
That last result is a theorem of graph theory rather than automata network. It expresses that, if we are given a graph as boolean circuits (this is a kind of oracle model), then it is not possible to express in MSO a question testable in polynomial time.
I also helped to design, test, and evaluate the performance of two image restoration algorithms with my friend Thang Cong Fam.
