Ce n’est pas une surprise au vu du titre de ma thèse que je m’intéresse aux beaux préordres et leurs applications en informatique, plus particulièrement en théorie des modèles finis. Dans ma recherche, je me suis assez rapidement tourné vers la notion topologique associée, celle d’espace Noethérien plus adaptée à mes travaux. C’est peut-être aussi parce que Jean Goubault-Larrecq, un de mes directeurs de thèse, a fait son cheval de bataille de transposer les résultats sur les beaux préordres aux espaces Noethériens que ce soit pour en mimer les constructions ou identifier les similarités d’applications.
La topologie sous mot
Une des constructions fondamentales dans la théorie des beaux préordres est la construction du préordre sous-mot qui se trouve être un beau préordre grâce au Lemme de Higman. Dans ce billet de blog nous explorons avec Jean une manière originale d’aborder la construction d’une topologie sur les mots finis, et généralisons l’approche au cas des mots infinis.
Avant de lire cet article, quelques points à garder en tête
- Lorsqu’on veut généraliser une construction de préordre à une construction topologique, un critère de correction est que le préordre de spécalisation coincide. Néanmoins, c’est une condition extrêmement faible, et il existe un grand nombre de topologies possibles.
- Il existe un grand nombre de topologies Noethériennes possibles sur un ensemble, et a priori, il n’y en a pas une unique plus fine que toutes les autres.
- La construction en utilisant des pré-ordres ne fonctionne pas sur les mots infinis. C’est donc un résultat surprenant lorsque la généralisation aux espaces topologiques permet de capturer le cas des mots finis.
Ce billet de blog sert donc à donner une manière systématique de définir uniquement une topologie sur des mots qui coincide avec toutes les constructions qui nous intéressent, et qui donne systématiquement un espace Noethérien.
Un petit mot sur la méthodologie
Le billet de blog reste factuel et propose la solution technique toute prête, mais on peut se demander comment et pourquoi une telle approche a pu émerger. De mon côté, cela commence par la lecture d’un article sur le gap embedding. Sans rentrer dans des détails peu intéressants, l’article étant particulièrement technique, l’idée est de retrouver naturellement les constructions de Higman, Kruskal et Friedman. L’idée simple étant de remarquer que l’ensemble des mots est construit de manière inductive à partir d’un simple produit, et que l’ensemble des arbres est défini de manière inductive à partir des mots… Alors pourquoi ne pas construire dans le même temps leurs topologies ?
Cette idée pose de nombreux problèmes, et une manière d’éviter les problèmes de définitions cycliques est de s’inspirer de ce qui est fait tous les jours dans les langages de programmation: ce n’est pas parce que notre représentation concrète possède une certaine forme que notre interface présentée au monde extérieur doit permettre d’accéder à toute l’information. Ainsi, on peut construire l’espace des mots de manière classique, mais décider des moyens d’interaction avec ces mots.
Plus concrètement, alors que l’article qui a inspiré cette recherche s’efforce d’intégrer dans la construction de l’espace les contraintes sur la manipulation des mots, on peut s’affranchir de cette construction en posant a posteriori une topologie en utilisant certains destructeurs. Cette méthode est particulièrement efficace pour deux raisons
- La forme même des destructeurs fait que l’on peut construire la topologie la plus grossière qui rend ces destructeurs continus. Cela donne une notion de canonicité.
- Ces destructeurs apparaissent naturellement dans les preuves par mauvaise séquence minimale.
Pour moins de blabla et plus de résultats, il ne vous reste plus qu’à lire l’article.