A sprouting tree model for random boolean functions1. Issue 4 (31st July 2014)

• Record Type: Journal Article
• Authors: Chauvin, Brigitte; Gardy, Danièle; Mailler, Cécile
• Is Part Of: Random structures & algorithms. Volume 47:Issue 4(2015)
• Page Start: 635
• Page End: 662
• Publication Date: 2014-07-31
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20567
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>ABSTRACT</title> <p>We define a new probability distribution for Boolean functions of <italic>k</italic> variables. Consider the random Binary Search Tree of size <italic>n</italic>, 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 <italic>n</italic> tend to infinity: the asymptotic distribution on Boolean functions exists; we call it the <italic>sprouting tree</italic> 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. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 635–662, 2015</p> </abstract>