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

### Keywords

- Binary search tree model of growth
- Binary trees
- Boolean expressions
- Boolean formulas
- Boolean functions
- Yule tree

## Fingerprint Dive into the research topics of 'A sprouting tree model for random boolean functions'. Together they form a unique fingerprint.

## Cite this

Chauvin, B., Gardy, D., & Mailler, C. (2015). A sprouting tree model for random boolean functions.

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