A sprouting tree model for random boolean functions

Brigitte Chauvin, Danièle Gardy, Cécile Mailler

Research output: Contribution to journalArticle

3 Citations (Scopus)
122 Downloads (Pure)

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 languageEnglish
Pages (from-to)635-662
Number of pages28
JournalRandom Structures and Algorithms
Volume47
Issue number4
Early online date31 Jul 2014
DOIs
Publication statusPublished - 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