Next: Théorie des semigroupes Up: Home Page Previous: Topologie profinie

Théorie des codes

J'ai étudié, en collaboration avec I. Simon, une conjecture de Perrin et Schützenberger connue sous le nom de conjecture des triangles. Nous n'avons pu démontrer que certains cas particuliers de cette conjecture [23,27]. Ces résultats étaient cependant presque optimaux puisque P. Shor a finalement trouvé un contre exemple à la conjecture à partir d'un cas légèrement plus général que ceux que nous avions envisagés.

J'ai surtout étudié les codes au travers des propriétés de leurs semigroupes syntactiques. J'ai montré tout d'abord que tout semigroupe fini divise le semigroupe syntactique d'un code préfixe fini [5]. Ce résultat a des conséquences intéressantes. En premier lieu, il intervient de façon cruciale pour montrer que les reconnaissables forment la seule variété fermée par étoile (Perrot) [12,9]. En second lieu, il donne des renseignements précieux sur le problème de la hauteur d'étoile évoqué plus haut. Par la suite, j'ai affiné ce résultat (avec S.W. Margolis) et j'ai montré que toute variété de langages fermée par produit pouvait être décrite par ses codes préfixes finis [21,15,44]. Ces résultats interviennent également dans l'étude des opérations sur les langages. J'ai pu ainsi résoudre une conjecture de Straubing et donner la première description des langages sans étoile qui n'utilise pas le produit de concaténation [11,12].

Les codes jouent un grand rôle dans les problèmes de compression de données et de théorie de l'information [3] et mes connaissances dans ce domaine ont été très utiles lors de diverses expertises menées auprès du CNES sur les problèmes de compression de données [72].