|
Evènement pour le groupe Combinatoire Énumérative et Algébrique
Date | 2015-12-18 10:45-11:45 |
Titre | Arbres 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. |
Lieu | 076 |
Orateur | Cécile Mailler |
Email | c.mailler@bath.ac.uk |
Url | université de Bath (Angleterre), Prob-L@B |
Aucun document lié à cet événement. RetourRetour à l'index
| |