Un accessit du prix Gilles Kahn pour Florent Koechlin (Gamble)
14 mars 2023
Bravo à Florent Koechlin, post-doctorant Inria dans l’équipe Gamble, qui a décroché un accessit du prix de thèse Gilles Kahn – Société Informatique de France !Florent a réalisé sa thèse au Laboratoire d’Informatique Gaspard-Monge (LIGM – CNRS/Université Gustave Eiffel).
Découvrez son parcours sur cette interview !
Pourrais-tu te présenter ? Quel a été ton parcours ?
Je m’appelle Florent Koechlin, et je suis actuellement en postdoc au LORIA, dans l’équipe Gamble. J’ai fait mes études en informatique à l’ENS Paris Saclay (ancienne ENS Cachan), puis j’ai effectué ma thèse au LIGM, à l’université Gustave Eiffel, sous la direction d’Arnaud Carayol et Cyril Nicaud.
Quel était ton sujet de thèse ? En quoi ont consisté tes recherches ? Quels résultats as-tu obtenu ?
Ma thèse s’intitule « Systèmes de fonctions holonomes, application à la théorie des automates ». Le fil conducteur de la thèse est d’étudier plusieurs problèmes issus de différents domaines, dont la théorie des automates, à l’aide des outils de la combinatoire analytique.
Plus précisément, je me suis intéressé dans une première partie aux arbres d’expressions aléatoires que l’on utilise en informatique pour tester des algorithmes ou pour étudier leur complexité moyenne.
En général, ces arbres d’expressions sont produits de façon purement syntaxique, sans tenir compte de leur signification. Or, pour de nombreuses familles d’expressions (arithmétiques, régulières, logiques, etc.), on observe des phénomènes de redondance : plusieurs expressions différentes représentent la même chose. Par exemple, 0 et 0*(x+y) représentent tous les deux zéro.
De très grandes expressions peuvent ainsi être équivalentes à des expressions en réalité très petites. Si ce phénomène se produit souvent sur des expressions aléatoires, cela peut remettre en question leur utilité pour tester ou analyser le comportement des algorithmes sur des entrées de grande taille.
J’ai montré dans ma thèse que la redondance induite par la seule présence d’un élément absorbant (comme 0 pour la multiplication, « vrai » pour le « ou » en logique, etc.) suffit à rendre les expressions aléatoires uniformes complètement dégénérées : elles sont équivalentes à des expressions petites en moyenne. Cela questionne notamment la pertinence de la distribution uniforme pour étudier la complexité moyenne d’un algorithme travaillant sur ces expressions : une des conséquences de ma thèse est que, sous certaines conditions naturelles, tout algorithme s’exécutant en temps polynomial au pire cas sur des arbres d’expressions présentant un élément absorbant, s’exécute en temps moyen constant (pour la distribution uniforme), si on simplifie d’abord l’expression en prenant en compte ses éléments absorbants.
Dans la deuxième partie de ma thèse, je me suis intéressé au lien entre la non-ambiguïté en théorie des automates et les séries génératrices en combinatoire. Il y a depuis les années 60 une correspondance bien connue entre ces deux domaines : les séries génératrices des langages réguliers sont rationnelles, celles des langages algébriques non ambigus sont algébriques (c’est le théorème des Chomsky-Schützenberger). Dans ma thèse je me suis appliqué à étendre ce lien, à la lumière des avancées en combinatoire et en théorie des langages formels qui ont été faites depuis les années 60. Plus précisément, la classe des séries holonomes est une généralisation des séries algébriques très courante en combinatoire. Après avoir proposé un modèle d’automate pertinent (les automates de Parikh (faiblement) non ambigus) qui soit associé à ces classes de séries, j’ai étudié dans ma thèse certaines conséquences de ce lien, que ce soit pour mieux comprendre la non-ambiguïté sur ces modèles d’automates, ou pour exploiter l’algorithmique des séries holonomes afin de répondre à certaines questions algorithmiques sur les automates.
Qu’as-tu préféré pendant cette période ?
Bizarrement (car on m’avait dit que c’était le pire moment de la thèse, et je l’appréhendais vraiment), j’ai bien aimé rédiger. Bien sûr, pas à la toute fin quand on doit rendre le manuscrit pour la semaine prochaine, et qu’on ne dort presque plus pour finir dans les temps… Mais si on oublie la toute dernière ligne droite, j’ai vraiment trouvé cela très agréable de pouvoir prendre le temps de revenir tranquillement sur un travail de 3 ans, sans avoir de limite de pages, avec une totale liberté sur la façon de présenter les choses. Même si j’y ai passé tout mon été, j’en garde un bon souvenir.
Sinon, mais ce n’est pas vraiment spécifique à la période de la thèse, j’ai aussi beaucoup aimé les interactions avec les chercheurs, que ce soit à l’occasion d’événements scientifiques (séminaires, réunion de travail, etc.), ou simplement dans la vie de tous les jours au labo. Je trouve la communauté scientifique très accueillante et bienveillante, cela donne vraiment envie de continuer dans la recherche.
