Projects per year
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).
Original language | English |
---|---|
Pages (from-to) | 15–58 |
Number of pages | 44 |
Journal | Random Structures and Algorithms |
Volume | 53 |
Issue number | 1 |
Early online date | 11 Jan 2018 |
DOIs | |
Publication status | Published - 1 Aug 2018 |
Keywords
- and/or trees
- local limit
- random Boolean functions
- random trees
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics
Fingerprint
Dive into the research topics of 'And/or trees: a local limit point of view'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Emergence of Condensation in Stochastic Systems
Morters, P. (PI)
Engineering and Physical Sciences Research Council
1/08/13 → 31/08/16
Project: Research council
Profiles
-
Cecile Mailler
- Department of Mathematical Sciences - Reader
- Probability Laboratory at Bath
- EPSRC Centre for Doctoral Training in Statistical Applied Mathematics (SAMBa)
Person: Research & Teaching, Researcher