Brigitte Chauvin: AND/OR Trees Revisited

This is a joint work with Philippe Flajolet, Daniele Gardy, and Bernhard Gittenberger.

We consider large boolean functions over $n$ variables $X_1$, $X_2$,...,$X_n$. Any such function can be represented (or computed) by a complete binary tree with and or or in the internal nodes and a literal in the external nodes. Many different trees can represent the same function, so that a fundamental question is related to the so-called ``complexity'' of a boolean function :

$$L(f):= \hbox{minimal size of a tree computing } f .$$

The existence of a limiting probability distribution $P(.)$ on the set of (finite or infinite) and/or trees was shown by Lefmann and Savicky [LS97]. We give here an alternative proof of the existence of this distribution, which leads to effective computation in simple cases. We also consider the relationship between the probability $P(f)$ and the complexity $L(f)$ of a boolean function $f$. The approach by Lefmann and Savicky leads to the following inequalities :

$$\frac{1}{4} .\big( \frac{1}{8n}\big) ^{L(f)-1}\leq P(f) \leq (1+O(1/n))\exp\big({-c\frac{L(f)}{n^3}}\big).$$ (1)

A detailed analysis of the functions enumerating some sub-families of trees, and of their radius of convergence, allows us to improve the upper bound, from $exp(- c L(f)/n^3)$ to $exp(-c L(f) /n^2)$.

Bibliography

LS97

Hanno Lefmann and Petr Savický.
Some typical properties of large AND/OR Boolean formulas.
Random Structures Algorithms, 10(3):337-351, 1997.

Back to the Index