## Teaching

I teach at the computer science department of the IUT d'Orsay.

I am responsible (since 2017) of the class M1105: "Design of documents and interfaces" for first-year students. Some material for 2019-2020:

- The handout and general planning ;
- The worksheet no.1 (with its helpsheet and an example), the worksheet no.2 (with its helpsheet and an example), the worksheet no.3 (with its helpsheet and an example) ;
- The final project and the grading sheet.

I also teach in the database course and the first-year project. I am co-responsible for the timetable design and responsible for the open days in the departement.

Some old teaching material:

- Some "développements" for the mathematics agrégation, computer science option. No guarantee of anything.
- Vectorial calculus class given in Spanish at the Universidad Andrés Bello. The material was designed in collaboration by Daniel Pons Rubio and his team.

## Research

My research revolves around **symbolic systems**, that is, systems whose configurations are infinite words (in one or more dimensions). I am interested in particular in **cellular automata**, **subshifts / tiling systems**, and some Turing machines. They are dynamical systems and models of computation.

The problems I study and my tools lie in the following rough areas:

**Topological and measure-theoretical dynamics, ergodic theory**, equilibrium or limit points and measures, and how generic ideas and tools adapt to the symbolic case;**Computability and decidability**, the interaction of dynamics and the ability to perform computation, and the difficulty to decide dynamical problems / compute dynamical objects;**Discrete probabilities and self-organisation**with probabilistic tools such as random walk and interacting particle systems.

For more details on my research interests, take a look below and click on each title to learn more.

The publications below are classified by theme, in (roughly) reverse order of when i worked on it. Publication in conferences (C) and journals (J) are numbered in the order I finished writing them.

###
Subshifts / Tilings
A configuration on a finitely generated group is a coloring of the Cayley graph associated with the group by a finite set of symbols, generalising the usual cases on Z and Z^2. Since the Cayley graph is regular (an inbound edge and an outbound edge by generator), one can define restrictions on allowed neighbouring symbols, for example using Wang tiles. A set of such restrictions defines a subshift on the group.

It is interesting to note that a given set of restrictions can apply to all groups with the same number of generators, and defines a subshift on each such group. In addition to studying individual subshifts, we can study the relationship between subshifts on the different groups to find global properties.

In J7, we study two known conditions on subshifts of Z^2 and of the free group. We show that these conditions are equivalent and necessary for the existence of a configuration on any amenable groupe.

A configuration on a finitely generated group is a coloring of the Cayley graph associated with the group by a finite set of symbols, generalising the usual cases on Z and Z^2. Since the Cayley graph is regular (an inbound edge and an outbound edge by generator), one can define restrictions on allowed neighbouring symbols, for example using Wang tiles. A set of such restrictions defines a subshift on the group.

It is interesting to note that a given set of restrictions can apply to all groups with the same number of generators, and defines a subshift on each such group. In addition to studying individual subshifts, we can study the relationship between subshifts on the different groups to find global properties.

In J7, we study two known conditions on subshifts of Z^2 and of the free group. We show that these conditions are equivalent and necessary for the existence of a configuration on any amenable groupe.

**Necessary conditions for tiling finitely generated amenable groups**

Published in

*Discrete and Continuous Dynamical Systems*, 2020

[publication, arXiv, HAL, bibtex]

###
Subshifts / Tilings
Decidability / Computability
Almost all classical undecidability results on subshifts of finite type of higher dimension rely on the existence of aperiodic points, a phenomenon that shaped this research area.

In C5, we show that any aperiodic point of a Z^2-subshift have a certain structure that describes the distance between locations where the different periods are broken. This lets us characterise the leve of undecidability of the problem of deciding whether a subshift has an aperiodic point, and to describe the properties of Z^2-subshifts with no aperiodic points.

An open question is what happens to this structure, and those other questions, in dimension 3 or more.

Almost all classical undecidability results on subshifts of finite type of higher dimension rely on the existence of aperiodic points, a phenomenon that shaped this research area.

In C5, we show that any aperiodic point of a Z^2-subshift have a certain structure that describes the distance between locations where the different periods are broken. This lets us characterise the leve of undecidability of the problem of deciding whether a subshift has an aperiodic point, and to describe the properties of Z^2-subshifts with no aperiodic points.

An open question is what happens to this structure, and those other questions, in dimension 3 or more.

**Aperiodic points in Z^2-subshifts.**

Published in

*ICALP*, 2018.

[publication, arXiv, HAL, bibtex]

###
Subshifts / Tilings
Decidability / Computability
The entropy of a subshift is a real parameter that corresponds to the exponential growth rate of the number of admissible finite patterns. Given a subshift of finite type, computing its entropy is a well-studied problem which was solved on a few rare examples. It is often very difficult and undecidable in the general case.

In J6, we study how the difficulty of the problem changes depending on a parameter that represents a mixing rate for the subshift. In a more general class, decidable subshifts, we characterise the threshold where the problem go from decidable to undecidable. We conjecture this threshold also holds for subshifts of finite type.

The entropy of a subshift is a real parameter that corresponds to the exponential growth rate of the number of admissible finite patterns. Given a subshift of finite type, computing its entropy is a well-studied problem which was solved on a few rare examples. It is often very difficult and undecidable in the general case.

In J6, we study how the difficulty of the problem changes depending on a parameter that represents a mixing rate for the subshift. In a more general class, decidable subshifts, we characterise the threshold where the problem go from decidable to undecidable. We conjecture this threshold also holds for subshifts of finite type.

**Effect of quantified irreducibility on the computability of subshift entropy.**

Published in

*Discrete and Continuous Dynamical Systems*, 2019.

[publication, arXiv, HAL, bibtex]

###
Cellular automata
Typical behaviour
A family of cellular automata exhibit a phenomenon called *randomisation* that can be described as follows. Draw an random initial configuration according to an arbitrary probability measure and iterate the cellular automaton on this configuration. As the number of iteration (time) tends to infinity, the pattern that appear at any given place tends to be distributed among all possible patterns with equal probability.

Automata for which this phenomenon is best-understood are the abelian cellular automata, that is, the endomorphisms when the alphabet is endowed with a commutative group structure. Proofs are generally base on Fourier analysis.

In J5, we characterise abelian cellular automata that exhibit this behaviour in Cesàro mean convergence by an elementary combinatorial property, which generalises most existing results in this context. Moreover, we provide an example of randomisation in direct convergence, a phenomenon which had never been formally proven before.

A family of cellular automata exhibit a phenomenon called *randomisation* that can be described as follows. Draw an random initial configuration according to an arbitrary probability measure and iterate the cellular automaton on this configuration. As the number of iteration (time) tends to infinity, the pattern that appear at any given place tends to be distributed among all possible patterns with equal probability.

Automata for which this phenomenon is best-understood are the abelian cellular automata, that is, the endomorphisms when the alphabet is endowed with a commutative group structure. Proofs are generally base on Fourier analysis.

In J5, we characterise abelian cellular automata that exhibit this behaviour in Cesàro mean convergence by an elementary combinatorial property, which generalises most existing results in this context. Moreover, we provide an example of randomisation in direct convergence, a phenomenon which had never been formally proven before.

**Characterizing Asymptotic Randomization in Abelian Cellular Automata.**

Published in

*Ergodic Theory and Dynamical Systems*, 2020.

[publication, arXiv, HAL, bibtex]

###
Model of computation
Decidability / Computability
Langton's insects are a family of Turing machines working on two-dimensional tapes with simple rules: the tape alphabet is Z/nZ; when the insect visits a cell, it increments the letter and turns by an angle given by the letter and the insect's rule, and goes forward by one step.

Despite their simplicity, those models exhibit complex dynamical behaviours. Starting from a simple configuration - say, uniform - they have highly irregular trajectories, apparently disordered and chaotic with some transitory symmetries. Some of them converge to a periodic behaviour after a very long time, which is the object of Langton's conjecture.

J4, which is mostly Diego Maldonado's master thesis work, show that the family of Turmites is able to embed universal computation (through simulating a cellular automaton), the input being written in a finite part of an otherwise periodic initial configuration. This lets us show the P-completeness of a prediction problem for those models, the same situation as the classical ones.

Langton's insects are a family of Turing machines working on two-dimensional tapes with simple rules: the tape alphabet is Z/nZ; when the insect visits a cell, it increments the letter and turns by an angle given by the letter and the insect's rule, and goes forward by one step.

Despite their simplicity, those models exhibit complex dynamical behaviours. Starting from a simple configuration - say, uniform - they have highly irregular trajectories, apparently disordered and chaotic with some transitory symmetries. Some of them converge to a periodic behaviour after a very long time, which is the object of Langton's conjecture.

J4, which is mostly Diego Maldonado's master thesis work, show that the family of Turmites is able to embed universal computation (through simulating a cellular automaton), the input being written in a finite part of an otherwise periodic initial configuration. This lets us show the P-completeness of a prediction problem for those models, the same situation as the classical ones.

**Nontrivial Turmites are Turing-universal.**

Published in

*Journal of Cellular Automata*, 2018.

[publication, arXiv, bibtex]

###
Cellular automata
Typical behaviour
Discrete probabilities
Self-organisation is the emergence of a structured behaviour from a simple or random initial configuration. In cellular automata, it often takes the form of growing regions consisting of a simple repeated pattern separated by borders that evolve at constant speed and interact as particles. Thus, tools from interacting particle systems and random walks can be used to describe the typical behaviour of the automaton.

This study can be roughly decomposed into two steps:

- Identify and describe the particles, understand and prove the relationship with the corresponding particle system;
- Obtain qualitative and quantitative results on this system and understand their consequences on the behaviour of the automaton.

In J3, which contains and generalises C2 and C3, we define a framework and tools to perform this study in arbitrary cellular automata. For example, we provide results that determine which particles survive asymptotically and the speed of convergence to the limit measure in some cases.

In S, we consider the so-called 3-state cyclic cellular automaton whose states are in a "rock-paper-scissors" relationship. This automaton is a simple example of a particle system and also used as a toy model, for example in population dynamics. We determine the asymptotic behaviour starting from an independant nonuniform initial measure, and observe a paradoxal behaviour of "survival of the weakest".

Self-organisation is the emergence of a structured behaviour from a simple or random initial configuration. In cellular automata, it often takes the form of growing regions consisting of a simple repeated pattern separated by borders that evolve at constant speed and interact as particles. Thus, tools from interacting particle systems and random walks can be used to describe the typical behaviour of the automaton.

This study can be roughly decomposed into two steps:

- Identify and describe the particles, understand and prove the relationship with the corresponding particle system;
- Obtain qualitative and quantitative results on this system and understand their consequences on the behaviour of the automaton.

In J3, which contains and generalises C2 and C3, we define a framework and tools to perform this study in arbitrary cellular automata. For example, we provide results that determine which particles survive asymptotically and the speed of convergence to the limit measure in some cases.

In S, we consider the so-called 3-state cyclic cellular automaton whose states are in a "rock-paper-scissors" relationship. This automaton is a simple example of a particle system and also used as a toy model, for example in population dynamics. We determine the asymptotic behaviour starting from an independant nonuniform initial measure, and observe a paradoxal behaviour of "survival of the weakest".

**Asymptotic behaviour of the one-dimensional "Rock-Paper-Scissors" cyclic cellular automaton.**

Submitted to

*Annals of Applied Probability*, 2019.

[arXiv, HAL, bibtex]

**Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches.**

Published in

*Journal of Statistical Physics*, 2017.

[publication, arXiv, HAL, bibtex]

**Entry times in cellular automata with simple defects dynamics.**

Published in

*Automata/JAC*, 2012.

[publication, arXiv, HAL, bibtex]

**Self-organization in cellular automata: a particle-based approach.**

Published in

*DLT*, 2011.

[publication, manuscrit, bibtex]

###
Cellular automata
Model of computation
Decidability / Computability
When an initial configuration is drawn at random - say, uniformly - what variety and complexity can we expect to see by iterating cellular automata on this condiguration? A way to handle this question is to consider limit measures, which are a description of typical asymptotic behaviour. Which limit measures are reachable by cellular automata is also a description of the computational power of this (probabilistic) model of computation.

In the following works, we completely characterise reachable limit measures by computability conditions. Formally, we show that hey are exactly the semi-computable measures, the same situation as for Turing machines.

J1 provides a construction for dimension 1. J2, which extends and generalises C4, introduces a more complex construction that gives the same result for higher dimensions.

When an initial configuration is drawn at random - say, uniformly - what variety and complexity can we expect to see by iterating cellular automata on this condiguration? A way to handle this question is to consider limit measures, which are a description of typical asymptotic behaviour. Which limit measures are reachable by cellular automata is also a description of the computational power of this (probabilistic) model of computation.

In the following works, we completely characterise reachable limit measures by computability conditions. Formally, we show that hey are exactly the semi-computable measures, the same situation as for Turing machines.

J1 provides a construction for dimension 1. J2, which extends and generalises C4, introduces a more complex construction that gives the same result for higher dimensions.

**Characterisation of limit measures of higher-dimensional cellular automata.**

Published in

*Theory of Computing Systems*, 2017.

[publication, arXiv, HAL, bibtex]

**Construction of mu-limit sets of two-dimensional cellular automata.**

Published in

*STACS*, 2015.

[publication, preprint, bibtex]

**Characterization of sets of limit measures of a cellular automaton iterated on a random configuration.**

Published in

*Ergodic Theory and Dynamical Systems*, 2018.

[publication, arXiv, HAL, bibtex]

### GraphsParametrised complexityCounting
Counting matchings or perfect matchings in graphs is a difficult problem: #P-complete in the general case. It remains difficult in many subclasses, but there are some polynomial-time algorithms obtained by bounding a parameter called clique-width.

In C1, we enrich existing methods to count maximal matchings and some other extensions. The algorithm runs in time O(n^poly(k)) where k is the clique-width.

This article is the result of an M1 internship.

Counting matchings or perfect matchings in graphs is a difficult problem: #P-complete in the general case. It remains difficult in many subclasses, but there are some polynomial-time algorithms obtained by bounding a parameter called clique-width.

In C1, we enrich existing methods to count maximal matchings and some other extensions. The algorithm runs in time O(n^poly(k)) where k is the clique-width.

This article is the result of an M1 internship.

**Maximal matching and path matching counting in polynomial time for graphs of bounded clique width.**

Published in

*TAMC*, 2011.

[publication, arXiv, bibtex]

### Ph.D. thesis

I did my Ph.D., titled ** Asymptotic behaviour of Cellular Automata: Computation and Randomness**, under the supervision of Xavier Bressaud and Mathieu Sablik at the Aix-Marseille University. The thesis defense took place in Marseille on the September 26th, 2014. Here is the manuscript.

## Supervision

Below is a list of students I supervised as interns. If their email is given, they have consented to be contacted if you want to ask them about the experience.- Third year (L3):
- Guillaume Lasnier (
**guillaume.lasnier [at] universite-paris-saclay [point] fr**) for 3 weeks in 2019. - Margot Ferré (
**margot-ferre [at] orange [point] fr**) for 3 weeks in 2019.

- Guillaume Lasnier (
- Fifth year (M2):
- Léo Paviet-Salomon (
**leo.paviet-salomon [at] ens-lyon [point] fr**) for 5 months in 2020.

- Léo Paviet-Salomon (

## Curriculum

Pdf version inFrench or in English.

- sept. 2017 - current:
**Associate professor**in the GALaC team, LRI, Paris-Sud University. - sept. 2016 - sept. 2017:
**ATER**(teaching post-doc) in the Automata team, IRIF, Paris Diderot University. - sept. 2014 - sept. 2016:
**Post-doctorate**under the direction of Cristobal Rojas, Universidad Andrés Bello (Santiago). - sept. 2011 - sept. 2014:
**Ph.D. in informatics**:*Asymptotic behaviour of cellular automata: computation and randomness*.

## Miscellaneous

I a ma fervent go player. You can meet me at the Orsay go club, at a tournament in Paris, or online ("Jhyn" on every server, mostly OGS).

Come speak Japanese to me to hear me mumble something about Ishikawa Takuboku. Language-learning friends of misery, I recommend Anki, a flexible multiplatform flashcard system.

I owe to Emmanuel Jeandel to introduce me, among other things, to rateyourmusic.

You can find me bouldering Arkoze sometimes.

Some webcomics: SSSS if you like languages and maps, Subnormality with too many words, A softer world the poetic.