A sprouting tree model for random boolean functions

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

Research output: Contribution to journalArticle

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

Fingerprint

Boolean functions
Random Function
Boolean Functions
Galton-Watson Tree
Binary Search Tree
Random Trees
Random process
Random processes
Probability distributions
Asymptotic distribution
Labels
Leaves
Probability Distribution
Infinity
Model
Tend
Internal
Vertex of a graph

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 journalArticle

Chauvin, Brigitte ; Gardy, Danièle ; Mailler, Cécile. / A sprouting tree model for random boolean functions. In: Random Structures and Algorithms. 2015 ; Vol. 47, No. 4. pp. 635-662.
@article{eb9984009b4e42949a33d512d70178ee,
title = "A sprouting tree model for random boolean functions",
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.",
keywords = "Binary search tree model of growth, Binary trees, Boolean expressions, Boolean formulas, Boolean functions, Yule tree",
author = "Brigitte Chauvin and Dani{\`e}le Gardy and C{\'e}cile Mailler",
year = "2015",
month = "12",
day = "1",
doi = "10.1002/rsa.20567",
language = "English",
volume = "47",
pages = "635--662",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "John Wiley and Sons Inc.",
number = "4",

}

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 -