Abstract
We define a new probability distribution for Boolean functions of k variables. Consider the random Binary Search Tree of size n, and label its internal nodes by connectives and its leaves by variables or their negations. This random process defines a random Boolean expression which represents a random Boolean function. Finally, let n tend to infinity: the asymptotic distribution on Boolean functions exists; we call it the sprouting tree distribution. We study this model and compare it with two previously-known distributions induced by two other random trees: the Catalan tree and the Galton-Watson tree.
| Original language | English |
|---|---|
| Pages (from-to) | 635-662 |
| Number of pages | 28 |
| Journal | Random Structures and Algorithms |
| Volume | 47 |
| Issue number | 4 |
| Early online date | 31 Jul 2014 |
| DOIs | |
| Publication status | Published - 1 Dec 2015 |
Fingerprint
Keywords
- Binary search tree model of growth
- Binary trees
- Boolean expressions
- Boolean formulas
- Boolean functions
- Yule tree
Cite this
A sprouting tree model for random boolean functions. / Chauvin, Brigitte; Gardy, Danièle; Mailler, Cécile.
In: Random Structures and Algorithms, Vol. 47, No. 4, 01.12.2015, p. 635-662.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - A sprouting tree model for random boolean functions
AU - Chauvin, Brigitte
AU - Gardy, Danièle
AU - Mailler, Cécile
PY - 2015/12/1
Y1 - 2015/12/1
N2 - We define a new probability distribution for Boolean functions of k variables. Consider the random Binary Search Tree of size n, and label its internal nodes by connectives and its leaves by variables or their negations. This random process defines a random Boolean expression which represents a random Boolean function. Finally, let n tend to infinity: the asymptotic distribution on Boolean functions exists; we call it the sprouting tree distribution. We study this model and compare it with two previously-known distributions induced by two other random trees: the Catalan tree and the Galton-Watson tree.
AB - We define a new probability distribution for Boolean functions of k variables. Consider the random Binary Search Tree of size n, and label its internal nodes by connectives and its leaves by variables or their negations. This random process defines a random Boolean expression which represents a random Boolean function. Finally, let n tend to infinity: the asymptotic distribution on Boolean functions exists; we call it the sprouting tree distribution. We study this model and compare it with two previously-known distributions induced by two other random trees: the Catalan tree and the Galton-Watson tree.
KW - Binary search tree model of growth
KW - Binary trees
KW - Boolean expressions
KW - Boolean formulas
KW - Boolean functions
KW - Yule tree
UR - http://www.scopus.com/inward/record.url?scp=84945478875&partnerID=8YFLogxK
UR - http://dx.doi.org/10.1002/rsa.20567
U2 - 10.1002/rsa.20567
DO - 10.1002/rsa.20567
M3 - Article
VL - 47
SP - 635
EP - 662
JO - Random Structures and Algorithms
JF - Random Structures and Algorithms
SN - 1042-9832
IS - 4
ER -