Site personnel de Benjamin Hellouin

drapeau Orcid
Me

J'organise une rencontre hebdomadaire de go sur le plateau de Saclay : l'Etoile Noire.

Depuis septembre 2017, je suis maître de conférences dans l'équipe GaLAC (Graphes, Algorithmes, Combinatoire) au Laboratoire Interdisciplinaire des Sciences du Numérique (LISN, ex-LRI), université Paris-Saclay. J'enseigne au département Informatique de l'Institut Universitaire de Technologie (IUT) d'Orsay.

La plupart des documents sur ce site ont été réalisés lorsque j'étais payé par l'État français (ou chilien). J'autorise et j'encourage chacun à réutiliser librement leur contenu. Pour toute question ou commentaire, ou si vous avez besoin d'une source tex :


Enseignement

J'enseigne dans le département informatique de l'IUT d'Orsay.

En 2022, je suis surtout responsable du projet Web de première année et d'un cours de M2 : Calculabilité, Complexité, Modèles de Calcul.

Je suis co-responsable des emplois du temps et responsable des journées Portes Ouvertes de l'IUT.

Un rassemblement de vieux matériel pédagogique :


Encadrement

Voici les étudiants que j'ai encadrés (en thèse ou en stage de niveau M2 -- mes excuses pour les autres). Ceux dont le mail est indiqué ont donné leur accord pour être contactés.

Pierre Béaur (pierre [point] beaur [at] universite-paris-saclay.fr) est en train d'effectuer une thèse sous la codirection de Nathalie Aubrun et moi-même.


Sujets de recherche et publications

Ma recherche concerne les systèmes symboliques, c'est-à-dire les systèmes dont la configuration est décrite par un mot infini (en une dimension ou plus). J'étudie en particulier les automates cellulaires, les pavages / sous-décalages et certaines machines de Turing. Ce sont à la fois des systèmes dynamiques et des modèles de calcul.

Les problèmes que j'étudie et mes outils de travail peuvent se ranger dans les catégories suivantes :

Pour des directions de recherche plus précises, voir ci-dessous et cliquez sur le nom de chaque thème pour plus de détails.

Les publications ci-dessous sont classées thématiquement, par ordre antichronologique (approximatif) de mon travail sur chaque thème. Les publications en conférences (C) et en journaux (J) sont numérotées par ordre de fin de rédaction, qui n'est pas forcément celui de publication.

Sous-décalages / Pavages Décidabilité / Calculabilité

Un pavage symbolico-géométrique.

Les pavages géométriques consistent à recouvrir le plan en utilisant des copies d'un ensemble de tuiles, le plus souvent des polygones. Le mot "géométrique" est par opposition à "symbolique" où les contraintes sont données par des motifs interdits (couleurs ou symboles) plutôt que par la géométrie des tuiles.

Dans C8, nous étudions le problème classique du Domino dans un contexte mixte. Des contraintes géométriques sous-jacentes sont données à l'avance, des contraintes symboliques (colorations des tuiles) sont données en entrée, et il faut décider s'il est possible de paver le plan en respectant l'ensemble des contraintes. Nous montrons que ce problème reste indécidable quand les tuiles sont des losanges, comme dans le cas classique (correspondant à une seule tuile carrée), quelles que soient les autres contraintes géométriques sous-jacentes.

C8
Avec Victor Lutfalla :
The Domino problem is undecidable on every rhombus subshift.
Publié à Developements in Language Theory (DLT), 2023.
[publication, arXiv, bibtex]

Sous-décalages / Mots Automates

Une substitution est une transformation de mots consistant à remplacer chaque lettre par un mot ($a\to ab, b\to a$). Les points fixes ou les points limites pour une substitution ou, plus généralement, un ensemble de substitutions (systèmes S-adiques), sont des mots infinis très étudiés pour leurs propriétés dynamiques et combinatoires. Les mots Sturmiens en sont un exemple typique.

Dans C7, nous étudions les conditions sous lesquelles un automate fini (ou un sous-shift sofic) peut accepter un mot infini de ce type. Nous produisons des algorithmes fondés sur la notion de désubstitution d'automate pour décider ce problème dans la plupart des cas, et quelques résultats combinatoires concernant leur structure.

C7
Avec Pierre Béaur :
Sturmian and infinitely desubstitutable words accepted by an ω-automaton.
Publié à WORDS, 2023.
[publication, arXiv, HAL, bibtex]

Sous-décalages / Pavages Graphes

Le graphe Ken-Katabami.

Les Hom shifts sont une classe de pavages décrits par des contraintes d'adjacence qui sont les mêmes dans toutes les directions, ce qui fait qu'elles peuvent être décrites par un graphe fini non dirigé sur l'ensemble des couleurs. Cette classe contient plusieurs modèles très étudiés, comme les k-coloriages, le modèle de la glace carré ou des noyaux durs.

Dans S, nous étudions les propriétés de mélange de ces pavages ; autrement dit, la distance qu'il faut mettre entre deux motifs pour qu'il soit possible de les compléter en un pavage valide. On montre l'existence d'une transition entre les comportements logarithmiques et linéaires qui dépend des propriétés algébriques et topologiques du graphe. En particulier, le graphe ci-contre représente le premier Hom shift connnu ayant un taux de mélange logarithmique.

S
Avec Silvère Gangloff et Piotr Opocha :
Short-range and long-range order: a transition in block-gluing behavior in Hom shifts.
Soumis.
[arXiv, HAL, bibtex]

Sous-décalages / Pavages Groupes

Un pavage d'un groupe finiment généré est une assignation d'un symbole à chaque sommet du graphe de Cayley associé au groupe, une généralisation des cas classiques Z et Z^2. Comme le graphe de Cayley est régulier (une arête sortante et une entrante par générateur), on peut définir des restrictions sur les symboles voisins autorisés de manière uniforme, par exemple en utilisant des tuiles de Wang. Un ensemble de telles restrictions définit un sous-décalage sur ce groupe.

Il est intéressant de noter qu'un jeu de restrictions donné fonctionne pour tous les groupes ayant le bon nombre de générateurs, et définit un sous-décalage sur chacun de ses groupes. En plus d'étudier les sous-décalages individuels, on peut étudier la relation entre ces sous-décalages et chercher des propriétés globales.

Dans J7, nous étudions deux conditions connues sur les sous-décalages de Z^2 et du groupe libre. Nous montrons que ces deux conditions sont équivalentes et nécessaires pour l'existence d'un pavage sur tout groupe moyennable.

J7
Avec Hugo Maturana Cornejo :
Necessary conditions for tiling finitely generated amenable groups.
Publié à Discrete and Continuous Dynamical Systems, 2020.
[publication, arXiv, HAL, bibtex]

Sous-décalages / Pavages Modèle de calcul Décidabilité / Calculabilité

Structure des lieux de bris de périodes.

Presque tous les résultats classiques d'indécidabilité dans les sous-décalages de type fini de dimension >1 reposent sur l'existence de points apériodiques, un phénomène qui a donné sa forme actuelle à ce domaine de recherche.

Dans C5, nous démontrons que tout point apériodique d'un sous-décalage de Z^2 dispose d'une certaine structure qui décrit la distance entre les lieux où la périodicité est brisée. Cela nous permet de caractériser le degré d'indécidabilité du problème de décider si un sous-décalage possède un point apériodique, et de décrire des propriétés des sous-décalages de Z^2 sans point apériodique.

Dans C6, nous montrons que ce phénomène n'a pas lieu en dimension 4 et plus, et que le degré d'indécidabilité du problème ci-dessus est bien plus élevé qu'en dimension 2 (hors de la hiérarchie arithmétique). De tels sauts de difficulté sont rares au-dessus de la dimension 2.

Le cas de la dimension 3 est ouvert et nous continuons à travailler sur ce sujet (avec Antonin Callard et Ville Salo).

C6
Avec Antonin Callard :
The aperiodic domino problem in higher dimension.
Publié à STACS, 2022.
[publication, arXiv, HAL, bibtex]
C5
Avec Anaël Grandjean et Pascal Vanier :
Aperiodic points in Z^2-subshifts.
Publié à ICALP, 2018.
[publication, arXiv, HAL, bibtex]

Sous-décalages / Mots Décidabilité / Calculabilité

Difficulté de calculer l'entropie en taux du taux d'irréductibilité.

L'entropie d'un sous-décalage est un paramètre réel qui correspond au taux de croissance exponentiel du nombre de motifs admissibles. Étant donné un sous-décalage de type fini, calculer son entropie est une question bien étudiée. Quelques rares exemples non triviaux ont été résolus, mais ce problème se révèle très difficile et indécidable dans le cas général.

Dans J6, nous étudions la manière dont la difficulté de ce problème évolue lorsque l'on fait varier un paramètre qui représente le taux de mélange du sous-décalage. Dans une classe plus générale, les sous-décalages décidables, nous caractérisons exactement le seuil auquel le problème passe de décidable à indécidable. Nous conjecturons que ce seuil est le même pour les sous-décalages de type fini.

J6
Avec Silvère Gangloff :
Effect of quantified irreducibility on the computability of subshift entropy.
Publié dans Discrete and Continuous Dynamical Systems, 2019.
[publication, arXiv, HAL, bibtex]

Automates cellulaires Comportement en moyenne

Automate cellulaire randomisant fortement. Automate cellulaire randomisant en moyenne.

Une famille d'automates cellulaires - aux contours encore mal connus - présente un phénomène, dit de randomisation, qu'on peut décrire comme suit. Tirons une configuration initiale au hasard, suivant une mesure de probabilité arbitraire, et itérons l'automate cellulaire sur cette configuration. Comme le nombre d'itérations (le temps) tend vers l'infini, le motif qui apparaît à un endroit donné tend à être n'importe quel motif possible avec égale probabilité.

Les automates sur lesquels ce phénomène est le mieux compris sont les automates cellulaires abéliens, c'est-à-dire correspondant à un endomorphisme quand l'alphabet est muni d'une structure de groupe commutatif. Les preuves sont fondées le plus souvent sur l'analyse de Fourier.

Dans J5, nous caractérisons les automates cellulaires abéliens qui présentent ce comportement pour la convergence en moyenne par une propriété combinatoire simple, ce qui généralise la plupart des résultats existant pour ce contexte. De plus, nous montrons un exemple où la convergence se fait de manière directe, ce dont il n'existait pas de preuve formelle auparavant.

J5
Avec Ville Salo et Guillaume Theyssier :
Characterizing Asymptotic Randomization in Abelian Cellular Automata.
Publié dans Ergodic Theory and Dynamical Systems, 2020.
[publication, arXiv, HAL, bibtex]

Modèle de calcul Décidabilité / Calculabilité

Évolution temporelle d'une turmite de Langton.

Les insectes de Langton sont une famille de machines de Turing sur ruban 2D à règles simples : l'alphabet du ruban est Z/nZ ; quand l'insecte visite une case, il incrémente la lettre lue, tourne d'un angle qui dépend la lettre lue et de la règle de l'insecte, et avance d'un pas.

En dépit de leur simplicité, ces modèles présentent des dynamiques complexes. Partant d'une configuration simple - uniforme par exemple - ils présentent des trajectoires irrégulières, apparemment désordonnées et chaotiques avec certaines symétries passagères. Certains modèles convergent vers un comportement périodique après un temps très long, ce qui est l'objet de la conjecture de Langton.

J4, qui est principalement le travail de thèse de master de Diego Maldonado, nous montre que la famille des Turmites est capable de calcul universel (simulation d'un automate cellulaire), l'entrée étant écrite sur une partie finie d'une configuration initiale périodique. Cela nous permet de montrer la P-complétude d'un problème de prédiction pour ces modèles, comme c'est le cas pour les modèles de calcul classique.

J4
Avec Anahí Gajardo et Diego Maldonado et Andrés Moreira :
Nontrivial Turmites are Turing-universal.
Publié dans Journal of Cellular Automata, 2018.
[publication, arXiv, bibtex]

Automates cellulaires Comportement en moyenne Probabilités discrètes

Diagramme espace-temps de l'automate cyclique à 3 états.

L'auto-organisation correspond à l'émergence d'un comportement structuré à partir d'une configuration initiale simple ou tirée au hasard. Un mécanisme courant d'auto-organisation dans les automates cellulaires consiste en l'apparition de régions contenant en un motif simple répété séparées par des frontières qui évoluent à vitesse constante et interagissent telles des particules. Ainsi, des outils de systèmes de particules en interactions et de marches aléatoires sont utilisés pour décrire le comportement en moyenne de l'automate.

Cette étude peut grossièrement se décomposer en deux étapes :

  1. Identifier et décrire les particules, comprendre et prouver les relations avec le système de particules correspondant ;
  2. Prouver des résultats qualitatifs et quantitatifs sur ces systèmes et comprendre leur conséquence sur le comportement de l'automate.

Dans J3, qui rassemble et généralise C2 et C3, nous définissons un cadre et des outils généraux pour effectuer cette étude dans des automates cellulaires quelconques. Par exemple, nous fournissons des résultats pour déterminer quelles particules survivent asymptotiquement et la vitesse de convergence à la mesure limite dans certains cas.

Dans J8, nous considérons un automate cellulaire dit cyclique à trois états en relation de « pierre-papier-ciseaux ». Cet automate est un exemple simple de système de particules également utilisé comme modèle-jouet, par exemple en dynamique des populations. Nous déterminons le comportement asymptotique partant d'une mesure initiale indépendante non uniforme, qui présente un comportement paradoxal de « survie du plus faible ».

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

Automates cellulaires Modèle de calcul Décidabilité / Calculabilité

Interaction entre frontières de zones de calcul dans la construction 2D.

Quand une configuration initiale est tirée au hasard - disons, uniformément -, quelle variété et quel niveau de complexité peut-on s'attendre à observer en itérant un automate cellulaire sur cette configuration ? Une manière de traiter cette question est de considérer les mesures limites possibles, qui sont une description du comportement asymptotique. Comprendre l'ensemble des mesures limites atteignables par automate cellulaire est aussi une mesure de la puissance calculatoire ce de modèle (probabiliste) de calcul.

Dans les travaux ci-dessous, nous caractérisons complètement les mesures limites possibles par des conditions de calculabilité. Plus formellement, nous montrons qu'il s'agit exactement des mesures semi-calculables, la même situation que pour les machines de Turing.

J1 fournit une construction pour la dimension 1. J2, qui étend et généralise C4, introduit une construction plus complexe qui produit le même résultat pour les dimensions supérieures.

J2
Avec Martin Delacourt :
Characterisation of limit measures of higher-dimensional cellular automata.
Publié dans Theory of Computing Systems, 2017.
[publication, arXiv, HAL, bibtex]
C4
Avec Martin Delacourt :
Construction of mu-limit sets of two-dimensional cellular automata.
Publié dans STACS, 2015.
[publication, manuscrit, bibtex]
J1
Avec Mathieu Sablik :
Characterization of sets of limit measures of a cellular automaton iterated on a random configuration.
Publié dans Ergodic Theory and Dynamical Systems, 2018.
[publication, arXiv, HAL, bibtex]

Graphes Complexité paramétrée Comptage

Union de couplages maximaux dans la construction d'un graphe à largeur de clique bornée.

Compter les couplages ou les couplages parfaits d'un graphe est un problème difficile : #P-complet dans le cas général. Cette difficulté demeure dans beaucoup de sous-classes, mais on dispose de quelques algorithmes en temps polynomial en bornant un paramètre appelé largeur de clique.

Dans C1, nous enrichissons les méthodes existantes pour pouvoir compter les couplages maximaux, et quelques autres extensions. L'algorithme obtenu est en O(n^poly(k)) où k est la largeur de clique.

Il s'agit d'un travail issu d'un stage de M1.

C1
Avec Takeaki Uno :
Maximal matching and path matching counting in polynomial time for graphs of bounded clique width.
Publié dans TAMC, 2011.
[publication, arXiv, bibtex]

Thèse

J'ai effectué ma thèse, intitulée Comportement asymptotique des automates cellulaires : Aléa et Calcul, sous la direction de Xavier Bressaud et Mathieu Sablik à l'université d'Aix-Marseille. La défense a eu lieu le 26 septembre 2014 à Marseille. Voici le manuscrit.


CV

Version pdf en français ou en anglais.


Divers & Recommandations

Je suis un fervent joueur de go. Vous pouvez me croiser au club d'Orsay, dans un tournoi parisien, ou sur Internet (Jhyn sur tous les serveurs, surtout OGS).

Venez me parler japonais si vous voulez m'entendre bafouiller et parler d'Ishikawa Takuboku. Camarades de souffrance en langues, je recommande Anki, un système flexible multi-plateformes de flashcards.

Je dois à Emmanuel Jeandel de m'avoir, entre autres, fait réécouter de la musique et fait découvrir l'excellent site rateyourmusic.

Vous me trouverez parfois en train de faire de l'escalade de bloc à Arkoze.

Quelques webcomics moins connus: SSSS si vous aimez les langues et les cartes, Subnormality si vous aimez les pavés, A softer world pour des mots sur des images.