Personal page of Benjamin Hellouin

drapeau Orcid
Me

Since September 2017, I am assistant professor in the GaLAC team (Graphs, Algorithmics and Combinatorics) at the Laboratoire de Recherche en Informatique (LRI), Paris-Sud University. I teach at the Institut Universitaire de Technologie (IUT) of Orsay.

Most documents on this page were written while I was paid by the French (or Chilean) government. I allow and encourage anyone to reuse their contents freely. If you have any question, comment, or if you need a tex sourcefile:


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:

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:


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:

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.

J7
With Hugo Maturana Cornejo:
Necessary conditions for tiling finitely generated amenable groups
Published in Discrete and Continuous Dynamical Systems, 2020
[publication, arXiv, HAL, bibtex]

Subshifts / Tilings Decidability / Computability
Structure of the locations where periods are broken.

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.

C5
With Anaël Grandjean and Pascal Vanier:
Aperiodic points in Z^2-subshifts.
Published in ICALP, 2018.
[publication, arXiv, HAL, bibtex]

Subshifts / Tilings Decidability / Computability
DIfficulty of computing the entropy depending on the irreducibility rate.

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.

J6
With Silvère Gangloff:
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
Automate cellulaire randomisant fortement. Automate cellulaire randomisant en moyenne.

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.

J5
With Ville Salo and Guillaume Theyssier:
Characterizing Asymptotic Randomization in Abelian Cellular Automata.
Published in Ergodic Theory and Dynamical Systems, 2020.
[publication, arXiv, HAL, bibtex]

Model of computation Decidability / Computability
Temporal evolution of a Langton's Turmite.

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.

J4
With Anahí Gajardo, Diego Maldonado and Andrés Moreira:
Nontrivial Turmites are Turing-universal.
Published in Journal of Cellular Automata, 2018.
[publication, arXiv, bibtex]

Cellular automata Typical behaviour Discrete probabilities
Space-time diagram for the 3-state cyclic cellular automaton.

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:

  1. Identify and describe the particles, understand and prove the relationship with the corresponding particle system;
  2. 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".

S
With Yvan Le Borgne:
Asymptotic behaviour of the one-dimensional "Rock-Paper-Scissors" cyclic cellular automaton.
Submitted to Annals of Applied Probability, 2019.
[arXiv, HAL, bibtex]
J3
With Mathieu Sablik:
Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches.
Published in Journal of Statistical Physics, 2017.
[publication, arXiv, HAL, bibtex]
C3
With Mathieu Sablik:
Entry times in cellular automata with simple defects dynamics.
Published in Automata/JAC, 2012.
[publication, arXiv, HAL, bibtex]
C2
With Mathieu Sablik:
Self-organization in cellular automata: a particle-based approach.
Published in DLT, 2011.
[publication, manuscrit, bibtex]

Cellular automata Model of computation Decidability / Computability
Interaction at the border of two computation area in the two-dimensional construction.

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.

J2
With Martin Delacourt:
Characterisation of limit measures of higher-dimensional cellular automata.
Published in Theory of Computing Systems, 2017.
[publication, arXiv, HAL, bibtex]
C4
With Martin Delacourt:
Construction of mu-limit sets of two-dimensional cellular automata.
Published in STACS, 2015.
[publication, preprint, bibtex]
J1
With Mathieu Sablik:
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
Union of maximal matching in the construction of graph with bounded clique-width.

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.

C1
With Takeaki Uno:
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.

Curriculum

Pdf version inFrench or in English.


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.