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 models, not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shape. Fix an integer $k$, take a sequence of random (rooted) trees of increasing sizes, say $(t_n)_{n\ge 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 $(t_n)_{n\ge 1}$, the distribution induced on Boolean functions by this procedure converges as $n\to\infty$. In particular, we characterise two different behaviours of this limit distribution depending on the shape of the local limit of $(t_n)_{n\ge 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 but reasonable conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples we cover include, in a unified way, 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).
Type de document :
Article dans une revue
Random Structures and Algorithms, Wiley, In press
Liste complète des métadonnées

https://hal.inria.fr/hal-01220794
Contributeur : Nicolas Broutin <>
Soumis le : mardi 27 octobre 2015 - 00:13:04
Dernière modification le : vendredi 25 mai 2018 - 12:02:03

Lien texte intégral

Identifiants

  • HAL Id : hal-01220794, version 1
  • ARXIV : 1510.06691

Collections

Citation

Nicolas Broutin, Cécile Mailler. And/or trees: a local limit point of view. Random Structures and Algorithms, Wiley, In press. 〈hal-01220794〉

Partager

Métriques

Consultations de la notice

249