Titre : Arbres enrichis
Exposant : Daniele Gardy

Prenons une expression logique du calcul des propositions: elle peut être 
représentée sous forme arborescente. Suivant les règles de construction de la
formule, l'arbre sera binaire ou non, planaire ou non, et étiqueté avec
différents connecteurs ou littéraux. L'énumération de tels arbres, et
l'étude de leurs propriétés statistiques, sont un domaine classique
d'application de la combinatoire analytique. Prenons maintenant une formule du
calcul des prédicats: l'existence de quantificateurs fait que nous ne pouvons
plus a priori utiliser une représentation arborescente. L'énumération de
telles formules ne peut alors plus se faire suivant les techniques classiques
d'énumération d'arbres, et requiert de nouvelles approches.

Une formule du calcul des prédicats est un cas particulier de ce que nous
nommons "arbre enrichi": c'est un arbre auquel on ajoute des arcs partant de
certains noeuds (ici ceux correspondant aux quantificateurs) et allant vers des
feuilles. De manière équivalente, cela revient à colorer des arbres selon
certaines règles; on peut aussi voir ces structures comme une classe
particulière de graphes orientés acycliques.

Je présenterai les résultats (déjà obtenus ou en cours de finalisation) sur
certaines familles d'arbres enrichis, relatifs à leur énumération et à
certains paramètres, puis les possibilités d'extension à des modèles plus
généraux.