Fonctions Booléennes

Depuis Septembre 2009, les travaux de l'équipe sont soutenus par le projet ANR blanc BOOLE (2009-13).

Représentation arborescente des fonctions booléennes  

Un des problèmes centraux en Informatique Fondamentale est la représentation et la manipulation efficace des expressions booléennes. Une bonne compréhension des diverses représentations des fonctions booléennes et de leurs propriétés fondamentales, en particulier des divers types de complexité qui peuvent etre définis sur ces représentations et des distributions de probabilité qui leur sont associées, a un intéret évident dans nombre de domaines: conception de circuits, satisfiabilité de fonctions booléennes, avec les phénomènes de seuil sous-jacents, résolution de contraintes, etc. Par exemple, Lefmann et Savicky ont établi un lien entre un certain type de  représentation arborescente d'une fonction booléenne (les arbres et/ou) et sa complexité: la connaissance de la probabilité d'apparition d'une fonction f  permet de donner des bornes sur la complexité de f.

Les techniques énumératives, analytiques et probabilistes développées pour l'étude des structures arborescentes trouvent ici un nouveau champ d'application. Le travail développé dans l'équipe concerne principalement la définition et l'évaluation des probabilités en arbre sur les fonctions booléennes, ainsi que l'étude des liens entre la probabilité d'une fonction booléenne et sa complexité en arbre (plus petite taille d'un arbre représentant la fonction). Un axe de recherche récent concerne aussi les problèmes de satisfiabilité.

Collaborations

Les travaux sur les fonctions booléennes se font principalement en collaboration avec

  • des chercheurs du laboratoire de Mathématiques de l'UVSQ (B. Chauvin)
  • des chercheurs du département DMG de la Technische Universitat à Vienne, Autriche (B. Gittenberger, M. Kuba)
  • l'équipe de M. Zaionc au Jagiellonian Institute, Cracovie, Pologne

Ils sont partiellement soutenus par l'ANR SADA, par le PHC Amadeus (2006-07) pour la collaboration avec l'Autriche, et par le PHC Polonium (2007-08) pour celle avec la Pologne.

L'équipe  a bénéficié de la visite de J. Kozik (Jagiellonian Institute) sur une bourse de l'ambassade de France en Pologne, d'Octobre à Décembre 2007.

Publications

A. Genitrini, G. Matecki, J. Kozik. On the density and the structure of the Peirce-like formulae. 5è colloque Mathématiques-Informatique (MCS'08), Blaubeuren (Allemagne), Sept. 2008.

H. Fournier, D. Gardy, A. Genitrini, B. Gittenberger. Complexity and limiting ratio of boolean functions over implication. MFCS'08, Torun (Pologne), Août 2008.

D. Gardy. Expressions booléennes aléatoires; application à la probabilité et complexité ­de fonctions booléennes.
Exposé invité, journées du GDR IM, Paris, 24-25 Janvier 2008.

A. Genitrini, J. Kozik, M. Zaionc. Intuitionistic vs. Classical Tautologies, Quantitative Comparison. Types 2007, actes parus dans LNCS 4941, pp. 100-109, 2008.

H. Fournier, D. Gardy, A. Genitrini, M. Zaionc. Classical and intuitionnistic logics are asymptotically identical. Computer Science Logic'07, proceedings in LNCS 4646, pp. 177-193, 2007.

D. Gardy. Random Boolean expressions.
Invited paper, Colloquium on Computational Logic and Applications, Chambéry, Juin 2005.
DMTCS Proceedings AF, pp. 1-36 R. David, D. Gardy, P. Lescanne, M. Zaionc (eds).

D. Gardy, A. Woods. Lower bounds on probabilities for Boolean functions.
First Intern. Conf. on the Analysis of Algorithms, Barcelona, Spain, June 2005.
DMTCS Proceedings, vol. AD(2005), pp. 139-146, C. Martinez (ed.).

B. Chauvin, P. Flajolet, D. Gardy and B. Gittenberger. And/Or trees revisited. Combinatorics, Probability and Computing, Vol. 13 No. 4-5, (2004) 475-487.

Imprimer

Our website is protected by DMC Firewall!