Abstract FR:

L'index rationnel d'un langage non vide est une fonction croissante, qui a tout entier naturel strictement positif, associe un entier naturel. Le comportement asymptotique de cette fonction permet de caracteriser la complexite du langage. En effet, si un langage domine rationnellement un autre langage (c'est-a-dire qu'il existe une transduction rationnelle qui transforme le premier langage en le second), alors l'ordre de croissance de l'index rationnel du second langage n'est pas plus eleve que celui du premier. L'index rationnel est donc un outil qui permet dans certains cas de demontrer qu'un langage n'en domine pas un autre. Par exemple un langage dont l'index rationnel croit polynomialement ne peut pas dominer un langage dont l'index rationnel croit exponentiellement. Plus generalement, a toute fonction croissante, on peut associer le cone rationnel (c'est-a-dire une famille de langages stable par transduction rationnelle) des langages dont l'index rationnel croit moins vite que cette fonction. En fait cette these etudie les differents sous-cones du cone des langages algebriques, que l'index rationnel permet de distinguer, ce qui revient a chercher les ordres de croissance possibles pour l'index rationnel d'un langage algebrique. Cela conduit a l'etude de quatre grandes familles de langages algebriques: d'abord des langages algebriques dont l'index rationnel est majore par au moins un polynome, puis ceux dont l'index rationnel est exponentiel. Entre ces deux familles de langages on peut trouver aussi des langages algebriques dont l'index rationnel croit plus vite que tout polynome, mais moins vite que toute exponentielle. Enfin les seuls langages algebriques connus ayant un index rationnel croissant plus vite que toute exponentielle, sont les generateurs (c'est-a-dire des langages algebriques qui dominent tout langage algebrique)