Les mots engendrés par une grammaire avec un alphabet infini et un ensemble infini de productions peuvent être vus comme les traces d'une marche dans un automate infini.
C'est un problème qui équivaut à regarder les puissances itérées d'une matrice ; c'est aussi, et c'est ce point de vue que nous retiendrons, équivalent à l'étude de marches (aléatoires) sur un réseau discret.
Nous nous intéresserons plus particulièrement aux séries génératrices de ces "marches aléatoires sur les entiers" qui décomptent les chemins de longueur n (les mots de longueur n) ou les excursions (les mots qui commencent et finissent par la même lettre).
À titre d'illustration, un cas bien connu est le langage de Dyck qui peut être vu comme une marche pour laquelle on part de (0) et on finit en (0) en ne faisant que des pas +1 ou -1, tout en restant positif (la série génératrice donne les nombres de Catalan).
On donnera toute une classe de grammaires infinies donnant des séries rationnelles, algébriques ou transcendantes. Nous montrerons comment expliciter ces séries génératrices.
Nous illustrerons nos propos par quelques exemples ludiques :
Si le temps ne nous fait pas défaut, nous nous attaquerons également à des propriétés en moyenne et surtout à l'asymptotique du nombre de mots de longueur n. L'inversion de Lagrange marche pour des équations u=z phi(u), nous devrons étudier l'équation plus générale u^c=z phi(u), ce qui se fait via la méthode du point col.
Une partie de ces résultats (dont la résolution de la conjecture de Pinzani) est présentée dans l'article On Generating Functions of Generating Trees (C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy et D. Gouyou-Beauchamps).
Coordonnées du conférencier :
Cyril Banderier
Projet Algorithmes
INRIA Rocquencourt
78153 Le Chesnay
"http://algo.inria.fr/banderier/
Cyril.Banderier at inria.fr