Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2015-12-18  10:45-11:45
TitreArbres et/ou : une approche par limite locale 
RésuméUn arbre et/ou est un arbre dont les nœuds internes sont étiquetés soit par le connecteur logique ET, soit par le connecteur logique OU, et dont les feuilles sont étiquetées par des littéraux choisis parmi k variables booléennes {x_1, ..., x_k} et leurs négations. Un tel arbre calcule une fonction booléenne à k variables, i.e. une fonction de {0,1}^k dans {0,1}. Je m'intéresse dans cet exposé à décrire la fonction booléenne aléatoire calculée par un arbre et/ou aléatoire, en fonction des propriétés de l'arbre aléatoire choisi. Les résultats que je présente, obtenus en collaboration avec N. Broutin (Inria-Rocquencourt), concernent les arbres et/ou obtenus en étiquetant aléatoirement des arbres aléatoires standards : arbre de Catalan, arbre de Galton-Watson, arbre binaire de recherche aléatoire, etc. Notre résultat principal décrit le comportement de la distribution induite sur l'ensemble des fonctions booléennes en fonction de la limite locale de l'arbre aléatoire sous-jacent.  
Lieu076 
OrateurCécile Mailler 
Emailc.mailler@bath.ac.uk 
Urluniversité de Bath (Angleterre), Prob-L@B 



Aucun document lié à cet événement.

Retour
Retour à l'index