Une version "finite state" du théorème de Kraft McMillan

Marie-Pierre Béal
(Travail en collaboration avec F. Bassino et D. Perrin)

(Institut Gaspard-Monge, Marne-la-Vallée)

Résumé On introduit la notion d'automate des super-états construit à partir d'un autre automate. Cette construction est utilisée pour résoudre un problème ouvert relatif aux suites énumératives des feuilles d'arbres rationnels. On prouve qu'une suite  -rationnelle  d'entiers positif qui satisfait l'inégalité de Kraft :  est la suite énumérative selon la hauteur des feuilles d'un arbre rationnel k-aire. Ce résultat avait été conjecturé, mais n'était connu que dans le cas de l'inégalité stricte. Ce résultat constitue une version "finite state" du théorème de Kraft McMillan.

On utilise ensuite ce résultat pour caractériser les séries qui sont les séries énumératives des noeuds d'un arbre rationnel k-aire. On donne également de nouvelles preuves, basées sur la notion d'automate des super-états, du résultat suivant relatif aux suites énumératives des noeuds dans un arbre : une suite  -rationnelle t ayant une représentation linéaire primitive, telle que  ,  et dont le rayon spectral est strictement supérieur à 1/k est la suite énumérative selon la hauteur des noeuds d'un arbre k-aire rationnel.