论文标题
组合$ {\ bf m} $和模仿鸟格
The combinator ${\bf M}$ and the Mockingbird lattice
论文作者
论文摘要
我们研究由基本组合剂$ {\ bf m} $跨越的组合逻辑片段产生的组合理论结构和秩序理论结构。这个基本的组合器，由Smullyan命名为Mockingbird，由重写规则$ {\ bf m} x_1 \定义为x_1 x_1 $。我们证明，此重写关系的反射性和传递性关闭是$ {\ bf m} $上的条款的部分顺序，并且其重写图的所有连接组件都是晶格的Hasse图。最后的结果是基于引入有关重复森林的新晶格，这些森林是多种树状结构。这些晶格不是分级的，不是自动划分的，也不是半分布的。我们介绍了这些晶格的一些枚举特性，例如其元素的列举，其Hasse图的边缘及其间隔。这些结果来自术语和具有特定操作的重复森林的正式功率系列。
We study combinatorial and order theoretic structures arising from the fragment of combinatory logic spanned by the basic combinator ${\bf M}$. This basic combinator, named as the Mockingbird by Smullyan, is defined by the rewrite rule ${\bf M} x_1 \to x_1 x_1$. We prove that the reflexive and transitive closure of this rewrite relation is a partial order on terms on ${\bf M}$ and that all connected components of its rewrite graph are Hasse diagram of lattices. This last result is based on the introduction of new lattices on duplicative forests, which are sorts of treelike structures. These lattices are not graded, not self-dual, and not semidistributive. We present some enumerative properties of these lattices like the enumeration of their elements, of the edges of their Hasse diagrams, and of their intervals. These results are derived from formal power series on terms and on duplicative forests endowed with particular operations.
