Séminaire SPACE Tours

Formules booléennes aléatoires construites sur un ensemble infini de variables
Cécile Mailler
Friday 16 November 2012 11:00 -  Tours -  Salle 1180 (Bât E2)

Résumé :
Dans cet exposé, je présenterai des travaux en cours, en collaboration avec Antoine Genitrini (LIP6). Dans ces travaux, nous définissons et étudions une distribution de probabilité sur l'ensemble des fonctions booléennes, grâce à leur représentation sous forme d'arbres et/ou. Un arbre et/ou est un arbre binaire planaire dont les nœuds internes sont étiquetés par des connecteurs logiques (ici, 'et' et 'ou') et dont les feuilles sont étiquetées par des littéraux (un littéral étant une variable ou sa négation). Plus précisément, choisissons un arbre et/ou uniformément au hasard parmi les arbres et/ou ayant n feuilles, et dans lequel les littéraux étiquetant les feuilles sont choisies parmi k(n) variables et leurs négations : quelle est la distribution induite par ce tirage sur l'ensemble des fonctions booléennes ? Cette question est déjà largement étudiée dans la littérature quand k(n) = k est constante. Je donnerai dans cet exposé des éléments de réponses concernant le cas général, k(n) non constante.

Liens :