Carine Pivoteau (LIGM, Paris-Est)

Le livre “Analytic Combinatorics” de Flajolet et Sedgewick propose un cadre agréable – la Méthode Symbolique – pour définir des classes d’objets combinatoires à partir de grammaires (systèmes combinatoires) semblables à celles de la théorie des langages. En se plaçant dans ce cadre, il est possible d’effectuer un certain nombre de traitements quasi-automatiques sur ces objets: manipulation de séries génératrices, génération aléatoire, analyse asymptotique, … Cependant, lorsqu’il s’agit d’implanter de telles méthodes, il est nécessaire de se poser la question: comment savoir si un système combinatoire donné est “bien formé”? Cette question nous a amenés à considérer une autre approche permettant de décrire des objets combinatoires: la Théorie des Espèces de Structures. Bien qu’étudiées à des fins très différentes, ces deux approches présentent de nombreux points communs et permettent, lorsqu’elles sont associées, de fournir une base de travail solide pour l’automatisation d’un certain nombre de traitements combinatoires.

Dans cet exposé, nous présenterons ces deux approches et nous décrirons les passerelles menant de l’une à l’autre, dans le but de caractériser les systèmes qui décrivent effectivement des structures combinatoires.

Cette présentation est basée sur un travail en commun avec B. Salvy et M. Soria.