Random Boolean expressions
Random Boolean expressions
复制标题
随机布尔表达式
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Danièle Gardy
中科院分区：
文献类型：
--
作者：
Danièle Gardy
我们研究如何定义几个概率分布的布尔函数的集合上的一个固定数量的变量，从一个表示的布尔表达式的树。分析工具为我们提供了一种系统的方法来证明概率分布的存在，主要的挑战是分布的实际计算。最后讨论了布尔函数的概率与其复杂性之间的关系。
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.