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 :

\hbox{minimal size of a tree computing } f . \end{displaymath}

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 :
\begin{displaymath}\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). \end{displaymath} (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)$.


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

Please send comments and corrections to Thomas Klausner.