### 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

*Random Structures and Algorithms*,

*47*(4), 635-662. https://doi.org/10.1002/rsa.20567

**A sprouting tree model for random boolean functions.** / Chauvin, Brigitte; Gardy, Danièle; Mailler, Cécile.

Research output: Contribution to journal › Article

*Random Structures and Algorithms*, vol. 47, no. 4, pp. 635-662. https://doi.org/10.1002/rsa.20567

}

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 -