Random Boolean expressions

Abstract : We examine how we can define several probability distributions on the set of Boolean functions on a fixed number of variables, starting from a representation of Boolean expressions by trees. Analytic tools give us a systematic way to prove the existence of probability distributions, the main challenge being the actual computation of the distributions. We finally consider the relations between the probability of a Boolean function and its complexity.
Type de document :
Communication dans un congrès
David, René and Gardy, Danièle and Lescanne, Pierre and Zaionc, Marek. Computational Logic and Applications, CLA '05, 2005, Chambéry, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05), pp.1-36, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01183339
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 10:11:09
Dernière modification le : jeudi 11 janvier 2018 - 06:21:31
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 14:52:06

Fichier

dmAF0101.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01183339, version 1

Collections

Citation

Danièle Gardy. Random Boolean expressions. David, René and Gardy, Danièle and Lescanne, Pierre and Zaionc, Marek. Computational Logic and Applications, CLA '05, 2005, Chambéry, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05), pp.1-36, 2005, DMTCS Proceedings. 〈hal-01183339〉

Partager

Métriques

Consultations de la notice

92

Téléchargements de fichiers

178