A sprouting tree model for random boolean functions

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

doi:10.1002/rsa.20567

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)

130 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 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	https://doi.org/10.1002/rsa.20567
Publication status	Published - 1 Dec 2015

Keywords

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

Access to Document

10.1002/rsa.20567

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

Cite this

@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 = dec,

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

AN - SCOPUS:84945478875

VL - 47

SP - 635

EP - 662

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 4

ER -

A sprouting tree model for random boolean functions

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this