Abstract FR:

Ce travail definit, au moyen de la logique monadique du second-ordre et d'homomorphismes de semi-anneaux, des fonctions calculables efficacement, sur les graphes structures en arbres, de largeur arborescente bornee. Nous obtenons, ainsi, des algorithmes polynomiaux et meme lineaires pour plusieurs problemes, dont beaucoup sont np-complets, lorsqu'ils sont restreints aux graphes structures en arbres, de largeur bornee. Cette approche est etendue a d'autres fonctions telles que le diametre, et est appliquee aux grammaires de graphes probabilistes. Nous presentons, en particulier, des methodes pour calculer la valeur moyenne d'une fonction, de la classe consideree, sur une grammaire de graphes probabiliste