论文标题
模仿鸟晶格
Mockingbird lattices
论文作者
论文摘要
我们研究由基本组合剂$ {\ bf m} $跨越的组合逻辑片段产生的组合理论结构和秩序理论结构。这个基本的组合器，由Smullyan命名为Mockingbird，由重写规则$ {\ bf m} x_1 \定义为x_1 x_1 $。我们证明，此重写关系的反身和及时封闭是$ {\ bf m} $上的条款的部分顺序，并且其重写图的所有连接组件都是晶格的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 diagrams of lattices. This last result is based on the introduction of lattices on some forests. We enumerate the elements, the edges of the Hasse diagrams, and the intervals of these lattices with the help of formal power series on terms and on forests.
