Affordable Access

Random Boolean expressions

Authors
  • Gardy, Danièle
Publication Date
Jan 01, 2005
Source
HAL-UPMC
Keywords
Language
English
License
Unknown
External links

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.

Report this publication

Statistics

Seen <100 times