And/or trees: a local limit point of view
| Autor: | Nicolas Broutin, Cécile Mailler |
|---|---|
| Přispěvatelé: | Networks, Algorithms and Probabilities (RAP), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Networks, Algorithms and Probabilities (RAP2), Inria de Paris, Department of Mathematical Sciences [Bath], University of Bath [Bath], ANR-14-CE25-0014,GRAAL,GRaphes et Arbres ALéatoires(2014), Laboratoire de Probabilités, Statistique et Modélisation (LPSM (UMR_8001)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité) |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Mathematics(all)
General Mathematics 0102 computer and information sciences 01 natural sciences Combinatorics random Boolean functions Random tree Boolean function FOS: Mathematics Boolean expression Limit (mathematics) and/or trees 0101 mathematics Mathematics Applied Mathematics 010102 general mathematics Probability (math.PR) Computer Graphics and Computer-Aided Design local limit [MATH.MATH-PR]Mathematics [math]/Probability [math.PR] Cover (topology) 010201 computation theory & mathematics Binary search tree Limit point Tree (set theory) complexity random trees Software Mathematics - Probability random tree |
| Zdroj: | Random Structures and Algorithms Random Structures and Algorithms, Wiley, In press Broutin, N & Mailler, C 2018, ' And/or trees : a local limit point of view ', Random Structures and Algorithms, vol. 53, no. 1, pp. 15–58 . https://doi.org/10.1002/rsa.20758 Random Structures and Algorithms, 2018, 53 (1), pp.15--58. ⟨10.1002/rsa.20758⟩ |
| ISSN: | 1042-9832 1098-2418 |
| Popis: | 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). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text