No Shannon Effect Induced by And/Or Trees
No Shannon Effect Induced by And/Or Trees
复制标题
和/或树不会引起香农效应
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Cécile Mailler
中科院分区：
文献类型：
--
作者：
Antoine Genitrini;Bernhard Gittenberger;Cécile Mailler
自从 Chauvin 等人发表开创性论文以来，定量逻辑一直受到越来越多的关注。 2004 年，提出了该主题的第一个分析组合方法。从那时起，即使香农效应的问题对于大多数模型来说仍然存在，对随机布尔树的理解已经深入拓宽了。我们在本文中重点关注加泰罗尼亚与/或树的原始情况，并提出了这些对象的新规范，这意味着描述大树族的更简单方法。配备此规范，我们证明了 Catalan And/Or 二叉树模型不表现出香农效应，即存在一系列复杂度较小、概率为正的函数。
Quantitative logic has been the subject of an increasing interest since a seminal paper by Chauvin et al. in 2004, which presented the first Analytic Combinatorics approach of the subject. Since then, the understanding of random Boolean trees has been deeply widened, even if the question of Shannon effect remains open for the majority of the models. We focus in this paper on the original case of Catalan And/Or trees and propose a new specification of those objects that implies easier ways to describe large families of trees. Equipped with this specification, we prove that the model of Catalan And/Or binary trees do not exhibit Shannon effect, i.e. there exists a family of functions with small complexities, that have a positive probability.