Danièle Gardy - Random Boolean expressions

dmtcs:3475 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05) - https://doi.org/10.46298/dmtcs.3475
Random Boolean expressions

Authors: Danièle Gardy ORCID-iD1

  • 1 Parallélisme, Réseaux, Systèmes, Modélisation

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.

Volume: DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: Boolean function,complexity,probability distribution for Boolean functions,probability of tautologies,[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO],[INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]

9 Documents citing this article

Consultation statistics

This page has been seen 175 times.
This article's PDF has been downloaded 800 times.