And/or trees: a local limit point of view

Nicolas Broutin, Cecile Mailler

Research output: Contribution to journalArticle

Abstract

We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shapes. Fix an integer k, take a sequence of random (rooted) trees of increasing size, say (tn)n≥1, and label each of these random trees uniformly at random in order to get a random Boolean expression on k variables. We prove that, under rather weak local conditions on the sequence of random trees (tn)n≥1, the distribution induced on Boolean functions by this procedure converges as n tends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of (tn)n≥1 : a degenerate case when the local limit has no leaves; and a non‐degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton–Watson trees).
LanguageEnglish
Pages15–58
JournalRandom Structures and Algorithms
Volume53
Issue number1
Early online date11 Jan 2018
DOIs
StatusPublished - 2018

Fingerprint

Boolean functions
Random Trees
Boolean Functions
Labels
Galton-Watson Tree
Binary Search Tree
Rooted Trees
Limit Distribution
Square root
Logarithmic
Leaves
Interpolate
Infinity
Tend
Converge
Integer
Model
Framework

Cite this

And/or trees : a local limit point of view. / Broutin, Nicolas; Mailler, Cecile.

In: Random Structures and Algorithms, Vol. 53, No. 1, 2018, p. 15–58.

Research output: Contribution to journalArticle

Broutin, Nicolas ; Mailler, Cecile. / And/or trees : a local limit point of view. In: Random Structures and Algorithms. 2018 ; Vol. 53, No. 1. pp. 15–58
@article{12438f58cc75431794956900b69794d3,
title = "And/or trees: a local limit point of view",
abstract = "We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shapes. Fix an integer k, take a sequence of random (rooted) trees of increasing size, say (tn)n≥1, and label each of these random trees uniformly at random in order to get a random Boolean expression on k variables. We prove that, under rather weak local conditions on the sequence of random trees (tn)n≥1, the distribution induced on Boolean functions by this procedure converges as n tends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of (tn)n≥1 : a degenerate case when the local limit has no leaves; and a non‐degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton–Watson trees).",
author = "Nicolas Broutin and Cecile Mailler",
year = "2018",
doi = "10.1002/rsa.20758",
language = "English",
volume = "53",
pages = "15–58",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "John Wiley and Sons Inc.",
number = "1",

}

TY - JOUR

T1 - And/or trees

T2 - Random Structures and Algorithms

AU - Broutin,Nicolas

AU - Mailler,Cecile

PY - 2018

Y1 - 2018

N2 - We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shapes. Fix an integer k, take a sequence of random (rooted) trees of increasing size, say (tn)n≥1, and label each of these random trees uniformly at random in order to get a random Boolean expression on k variables. We prove that, under rather weak local conditions on the sequence of random trees (tn)n≥1, the distribution induced on Boolean functions by this procedure converges as n tends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of (tn)n≥1 : a degenerate case when the local limit has no leaves; and a non‐degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton–Watson trees).

AB - We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shapes. Fix an integer k, take a sequence of random (rooted) trees of increasing size, say (tn)n≥1, and label each of these random trees uniformly at random in order to get a random Boolean expression on k variables. We prove that, under rather weak local conditions on the sequence of random trees (tn)n≥1, the distribution induced on Boolean functions by this procedure converges as n tends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of (tn)n≥1 : a degenerate case when the local limit has no leaves; and a non‐degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton–Watson trees).

U2 - 10.1002/rsa.20758

DO - 10.1002/rsa.20758

M3 - Article

VL - 53

SP - 15

EP - 58

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 1

ER -