Séminaire Lotharingien de Combinatoire, 86B.3 (2022), 12 pp.
Samuele Giraudo
Mockingbird Lattices
Abstract.
We study combinatorial and order theoretic structures arising from the fragment of
combinatory logic spanned by the basic combinator M. This basic combinator, named as
the Mockingbird by Smullyan, is defined by the rewrite rule
Mx1 -> x1x1.
We prove that the reflexive and transitive closure of this rewrite relation is
a partial order on terms on 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.
Received: November 25, 2021.
Accepted: March 4, 2022.
Final version: April 1, 2022.
The following versions are available: