Structural properties of large random maps and lambda-terms may be gleaned by studying the limit distributions of various parameters of interest. In our work we focus on restricted classes of maps and their counterparts in the lambda-calculus, building on recent bijective connections between these two domains. In such cases, parameters in maps naturally correspond to parameters in lambda-terms and vice versa. By an interplay between lambda-terms and maps, we obtain various combinatorial specifications which allow us to access the distributions of pairs of related parameters such as: the number of bridges in rooted trivalent maps and of subterms in closed linear lambda-terms, the number of vertices of degree 1 in (1,3)-valent maps and of free variables in open linear lambda-terms etc. To analyse asymptotically these distributions, we introduce appropriate tools: a moment-pumping schema for differential equations and a composition schema inspired by Bender's theorem.
翻译:大型随机地图和羊羔术语的结构属性可以通过研究各种相关参数的有限分布来采集。 在我们的工作中,我们侧重于限制的地图类别及其在羊羔-计算学中的对应方,以这两个区域之间最近的双向联系为基础。 在这种情况下,地图中的参数自然符合羊羔-术语中的参数,反之亦然。通过羊羔-术语和地图之间的相互作用,我们获得了各种组合性规格,使我们能够获取相关参数的分布,例如:根基三价地图中的桥梁数量和封闭线性羊羔-术语中的子术语数量、1级(1,3)价地图中的顶点数量以及开放线性羊驼-术语中的自由变量数量。为了进行随机分析,我们引入了适当的工具:用于不同方程的瞬间抽动模型和由Bender理论启发的构成模型。