Combinatoire des mots infinis
A. Description d'une nouvelle classe de mots infinis. Nous avons défini une nouvelle classe de mots infinis, à savoir la classe des mots lisses. Il existe plusieurs familles de mots infinis remarquables, parmi lesquelles celle des mots Sturmiens et son prototype le mot de Fibonacci, et celle des mots sans chevauchements ou le mot de Morse joue un role fondamental. A l'aide d'un outil de calcul formel développé par Annie Ladouceur, nous avons produit des résultats expérimentaux suggérant de nombreuses conjectures sur les mots lisses. Il s'avère que les palindromes y sont caracterisés à l'aide de la clôture palindromique gauche des facteurs préfixes du mot de Kolakoski K, rappelant en cela une propriété analogue du mot de Fibonacci. L'étude du mot K est réputée difficile, et par l'étude de cette classe nous avons introduit un cadre beaucoup plus riche pour en comprendre la structure: nous avons d'une part établi un lien entre l'existence de certains palindromes et la récurrence de K; d'autre part, nous avons généralisé un résultat de A. Carpi, en décrivant complètement les facteurs carrés et les chevauchements (qui sont, de manière surprenante en nombre fini) ce qui implique que les mots lisses sont sans cube. Les résultats expérimentaux suggèrent également que tous les mots de cette classe possèdent la même complexité que celle de K (en fait les mêmes facteurs). Et nous avons obtenu quelques résultats partiels dans cette direction. Le fait que tous les mots de cette classe possèdent les mêmes facteurs implique qu'ils ne sont pas localement distinguables, et de ce fait, ils présentent un intérêt pour la cryptographie, un aspect qui est étudié en collaboration avec J. Mullins (Ecole Polytechnique de Montréal). Finalement, à ces mots sont naturellement associés des pavages du plan qui demandent une analyse plus poussée. Actuellement, ces objets font l' objet de discussions et de collaboration avec L. Vuillon et V. Berthé.
B. Complexité des mots infinis. Dans un travail antérieur (datant de 1987, publié en 1989 et souvent cité) j'ai établi précisément la complexité de la suite de Thue-Morse
Indépendamment, Aldo de Luca obtint le même résultat de manière élégante par le dénombrement des facteurs spéciaux de M. Plus tard, lors du séjour de A. Aberkane (étudiant de J. Cassaigne à Marseille) dans notre laboratoire en septembre 2000, nous avons obtenu un résultat surprenant, à savoir que, parmi les suites récurrentes, les orbites de la suite de Thue-Morse M ainsi que de son image par le morphisme doublant les lettres,
sont les seules suites ayant cette complexité. La démonstration est obtenue par l' utilisation astucieuse des graphes de de Bruijn (connus également sous le vocable de graphes de Rauzy) et il n'est pas clair qu'une autre approche soit concevable. Actuellement, avec Ali nous regardons comment enlever dans la démonstration l'hypothèse "récurrente".
C. Suites de Tribonacci. Nous avons établi que les 3 suites de Carlitz, Scoville et Hoggatt sont codées par les occurrences des lettres du mot infini
obtenu par itération du morphisme sur 3 lettres
L'intérêt est double: cette caractérisation réalise d'une part une compression, facile à calculer, et d'autre part elle se généralise. Finalement certains résultats expérimentaux, utilisant l'encyclopédie de Sloane, montrent que d'autres y sont liées, qu'elles peuvent être décrites de manière analogue, et suggèrent un résultat plus général. Cette étude fait l'objet d'une collaboration avec Elena Barcucci (Florence)
Langages formels et combinatoire bijective. Dans ces travaux l'influence de la théorie des langages formels (et surtout l'oeuvre de M.P. Schützenberger) est dominante.
D. Sous-ensembles rationnels de 
. Un résultat de Eilenberg et
Schützenberger établit que les sous-ensembles rationnels d'un monoïde commutatif M
sont aussi non-ambigus. Dans ce travail réalisé avec C. Reutenauer, nous
considérons le cas particulier de et associons à chaque sous-ensemble rationnel
non-ambigu une fonction rationnelle. Cette construction permet de dériver une
généralisation multivariée du théorème de Popoviciu et une valuation
classique sur les polyhèdres.
E. Théorie des arbres de génération (méthode ECO). La méthode ECO est une méthode basée sur les systèmes de récritures permettant de construire inductivement et énumérer des objets combinatoires. La structure sous-jacente est un arbre dont le niveau n contient les objets de taille n. Deux systèmes sont équivalents s'ils déterminent la même suite énumératrice. Dans ces travaux, nous avons enrichi la théorie en montrant d'une part que des bijections naturelles permettent de construire des systèmes équivalents ayant des règles identiques. D'autre part, en utilisant la méthode du noyau, nous avons montré que les fonctions génératrices bi-variées associées à deux systèmes définissant les nombres de Catalan et ceux de Schröder sont égales.