Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [43 references]  Display  Hide  Download

https://hal.inria.fr/hal-01183339
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 12, 2015 - 10:11:09 AM
Last modification on : Friday, January 10, 2020 - 3:42:21 PM
Long-term archiving on: : Friday, November 13, 2015 - 2:52:06 PM

File

dmAF0101.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01183339, version 1

Collections

Citation

Danièle Gardy. Random Boolean expressions. Computational Logic and Applications, CLA '05, 2005, Chambéry, France. pp.1-36. ⟨hal-01183339⟩

Share

Metrics

Record views

152

Files downloads

2051