And/or trees: A local limit point of view
And/or trees: A local limit point of view
复制标题
和/或树木：局部极限的观点
DOI：
10.1002/rsa.20758
复制
发表时间：
2018
影响因子：
1
通讯作者：
Broutin N
中科院分区：
文献类型：
--
作者：
Broutin N
我们在这里提出了一个新的和普遍的方法，随机和/或树的研究，统一在一个框架中许多不同的模型，包括一些新的尚未了解的文献。一个和/或树是一个布尔表达式，表示在（一个）它的树形状。固定一个整数k，取一个随机的（有根的）树序列，比如说，随机地给每个随机树均匀地标记，以得到k个变量的随机布尔表达式。我们证明了在随机树序列上相当弱的局部条件下，由这一过程在布尔函数上导出的分布趋于无穷大。特别是，我们根据局部极限的形状来描述这个极限分布的两种不同行为：当局部极限没有叶子时的退化情况;和非退化情况，我们能够在更强的条件下更详细地描述。在后一种情况下，我们提供了一个给定的布尔函数的概率和它的复杂性之间的关系。这个统一框架所涵盖的例子包括在具有对数典型距离的模型（如随机二叉搜索树）和具有平方根典型距离的其他模型（如条件Galton-Watson树）之间插值的树。
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 integerk, take a sequence of random (rooted) trees of increasing size, say , and label each of these random trees uniformly at random in order to get a random Boolean expression onkvariables. We prove that, under rather weak local conditions on the sequence of random trees , the distribution induced on Boolean functions by this procedure converges asntends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of : adegeneratecase 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 itscomplexity. 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).
登录
查看更多内容
和/或树的亚临界模式语言
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
J. Kozik
通讯作者：
J. Kozik
有限树的着色规则和一元二阶句子的概率
DOI：
--
发表时间：
1997
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
Alan R. Woods
通讯作者：
Alan R. Woods
CRT是无序二叉树的缩放限制
DOI：
--
发表时间：
2009
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
J. Marckert;G. Miermont
通讯作者：
G. Miermont
DOI：
10.1017/s1446788700016517
发表时间：
1980-12
期刊：
Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics
影响因子：
--
作者：
G. Grimmett
通讯作者：
G. Grimmett
大型 AND/OR 布尔公式的一些典型属性
DOI：
--
发表时间：
1995
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
H. Lefmann;P. Savický
通讯作者：
P. Savický