Site personnel de Benjamin Hellouin

drapeau Orcid
Me

Depuis septembre 2017, je suis maître de conférences dans l'équipe GaLAC (Graphes, Algorithmes, Combinatoire) au Laboratoire de Recherche en Informatique (LRI), université Paris-Sud. 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.

Je suis responsable (depuis 2017) du cours CODIN, ou « Conception de documents et d'interfaces numériques » (code PPN : M1105) en première année.

Matériel de cours utilisé en 2019-2020 :

J'interviens régulièrement dans les cours de bases de données et le projet de première année. 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 :


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

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

Ce que devient cette structure et toutes ces autres questions restent ouvertes en dimension 3 et plus.

C5
Avec Anaël Grandjean et Pascal Vanier :
Aperiodic points in Z^2-subshifts.
Publié à ICALP, 2018.
[publication, arXiv, HAL, bibtex]

Sous-décalages / Pavages 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 S, 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 ».

S
Avec Yvan Le Borgne :
Asymptotic behaviour of the one-dimensional "Rock-Paper-Scissors" cyclic cellular automaton.
Soumis à Annals of Applied Probability, 2019.
[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]

GraphesComplexité paramétréeComptage
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.


Encadrement

Voici une liste d'étudiants que j'ai encadré en stage. Ceux dont le mail est indiqué ont donné leur accord pour être contactés, par exemple si vous voulez leur poser des questions sur leur expérience.

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.