A sprouting tree model for random boolean functions

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

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)
173 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

Access to Document

  • ABR-version-longue

    This is the pre-peer reviewed version of the following article:Chauvin, B, Gardy, D & Mailler, C 2015, 'A sprouting tree model for random boolean functions' Random Structures and Algorithms, vol 47, no. 4, pp. 635-662., , which has been published in final form at http://dx.doi.org/10.1002/rsa.20567. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving.

    Submitted manuscript, 581 KB

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

    Cite this