Soutenance de thèse Alexandre Durand lundi 17 novembre 2025 - Amphi D - UFR Sciences et techniques

Alexandre Durand soutient sa thèse intitulée :

- Marie-Pierre Béal, Université Gustave Eiffel, rapporteuse
- Pascal Caron Université de Rouen Normandie, directeur
- Émilie Charlier Université de Liège, examinatrice (visio)
- Sylvain Lombardy Institut polytechnique de Bordeau, rapporteur
- Jean-Gabriel Luque Université de Rouen Normandie, examinateur
- Bruno Patrou Université de Rouen Normandie, co-encadrant
- Rogério Reis Faculdade de Ciências da Universidade do Porto, rapporteur (visio)

Résumé :
"Cette thèse porte sur l’étude des opérations unaires appliquées aux langages formels. Elle examine à la fois les structures algébriques engendrées par la composition de ces opérations, appelées monoïdes opérationnels, et leur influence sur la complexité des machines reconnaissant les langages. Nous structurons notre analyse autour de trois grandes catégories : (1) les monoïdes finis, (2) les monoïdes infinis dont chaque langage a une orbite finie, et (3) les monoïdes infinis admettant des orbites infinies.
Dans le premier cas, nous généralisons le théorème de Kuratowski en identifiant de nouvelles contraintes sur les opérations de fermeture qui assurent la finitude du monoïde, même lorsqu’un nombre arbitraire de fermetures sont combinées. Cela permet d’étendre la compréhension classique à des familles d’opérations plus larges.
Dans la seconde catégorie, nous montrons que certains couples d’opérations, comme la paire Trognon-Préfixe, engendrent des monoïdes infinis, mais dont l’action sur un langage donné produit toujours un nombre fini de langages (orbites finies).
Cette propriété rend ces structures particulièrement intéressantes, car elles peuvent servir à définir des métriques sur les langages.
Dans le dernier cas, nous identifions des configurations, telles que la paire Permutation circulaire–Préfixe, pour lesquelles certains langages induisent une orbite infinie, ce qui met en évidence la variété des comportements possibles au sein des monoïdes opérationnels.
En parallèle, nous examinons l’effet de ces opérations sur la taille minimale des automates reconnaissant les langages, c’est-à-dire la complexité en états. Nous nous appuyons sur des résultats existants concernant des opérations classiques comme l’étoile de Kleene, le miroir ou la racine, afin d’en étudier certaines combinaisons.
Une attention particulière est portée à l’opération Racine appliquée à des automates non déterministes, pour laquelle nous proposons de nouvelles constructions qui permettent d’aborder efficacement son interaction avec d’autres opérations. Nous obtenons notamment la borne exacte pour la combinaison Racine-Miroir, illustrant le fait que dans certains cas, la complexité peut être significativement inférieure à la borne naïve."