Mockingbird lattices
S Giraudo - arXiv preprint arXiv:2204.02616, 2022 - arxiv.org
arXiv preprint arXiv:2204.02616, 2022•arxiv.org
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 …
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 study combinatorial and order theoretic structures arising from the fragment of combinatory logic spanned by the basic combinator . This basic combinator, named as the Mockingbird by Smullyan, is defined by the rewrite rule . We prove that the reflexive and transitive closure of this rewrite relation is a partial order on terms on 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.
arxiv.org