Hostname: page-component-77c89778f8-rkxrd Total loading time: 0 Render date: 2024-07-16T15:13:58.214Z Has data issue: false hasContentIssue false
  • English
  • Français

The combinator M and the Mockingbird lattice

Published online by Cambridge University Press:  13 October 2022

Samuele Giraudo Open the ORCID record for Samuele Giraudo [Opens in a new window]
Samuele Giraudo*
Affiliation:
LIGM, Université Gustave Eiffel, CNRS, ESIEE Paris, F-77454 Marne-la-Vallée, France
*
Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study combinatorial and order theoretic structures arising from the fragment of combinatory logic spanned by the basic combinator ${{\mathbf{M}}}$ . This basic combinator, named as the Mockingbird by Smullyan, is defined by the rewrite rule ${{\mathbf{M}}} \mathsf{x}_1 \to \mathsf{x}_1 \mathsf{x}_1$ . We prove that the reflexive and transitive closure of this rewrite relation is a partial order on terms on ${{\mathbf{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 semi-distributive. 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.

Keywords

Partial orderslatticescombinatory logicrewrite systemstreelike structuresformal power series
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 32 , Issue 3 , March 2022 , pp. 271 - 299
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This research has been partially supported by the projects CARPLO (ANR-20-CE40-0007) and LambdaComb (ANR-21-CE48-0017) of the Agence nationale de la recherche.

References

Barendregt, H. P. (1981). The Lambda Calculus, its Syntax and Semantics , Studies in Logic and the Foundations of Mathematics, vol. 103, Elsevier. Revised edition.Google Scholar
Barendregt, H., Endrullis, J., Klop, J. W. and Waldmann, J. (2017). Dance of the starlings. In: Raymond Smullyan on Self Reference, Outstanding Contributions to Logic, vol. 14, Cham, Springer, 67–111.CrossRefGoogle Scholar
Bendkowski, M., Grygiel, K. and Zaionc, M. (2017). On the likelihood of normalization in combinatory logic. Journal of Logic and Computation 27 (7) 2251–2269.CrossRefGoogle Scholar
Bimbó, K. (2011). Combinatory Logic: Pure, Applied and Typed , Discrete Mathematics and Its Applications, New York, Taylor & Francis.Google Scholar
Bezem, M., Klop, J. W., de Vrijer, R. and Terese. (2003). Term Rewriting Systems , Cambridge Tracts in Theoretical Computer Science, Cambridge, Cambridge University Press.Google Scholar
Berry, G. and Lévy, J.-J. (1979). Minimal and optimal computations of recursive programs. Journal of the ACM 26 (1) 148–175.CrossRefGoogle Scholar
Baader, F. and Nipkow, T. (1998). Term Rewriting and All That, Cambridge, Cambridge University Press.CrossRefGoogle Scholar
Baril, J. L. and Pallo, J. M. (2006). The phagocyte lattice of Dyck words. Order 23 (2–3) 97–107.Google Scholar
Baril, J. L. and Pallo, J. M. (2008). The pruning-grafting lattice of binary trees. Theoretical Computer Science 409 (3) 382–393.CrossRefGoogle Scholar
Curry, H. B. and Feys, R. (1958). Combinatory Logic, vol. 1, Amsterdam, North-Holland Publishing Company.Google Scholar
Curry, H. B. (1930). Grundlagen der Kombinatorischen Logik. American Journal of Mathematics 52 (4) 789–834.CrossRefGoogle Scholar
David, R., Grygiel, K., Kozik, J., Raffalli, C., Theyssier, G. and Zaionc, M. (2013). Asymptotically almost all $\lambda$ -terms are strongly normalizing. Logical Methods in Computer Science 9 (1) 1.CrossRefGoogle Scholar
Dulucq, S. and Penaud, J.-G. (2002). Interprétation bijective d’une récurrence des nombres de Motzkin. Discrete Mathematics 256 (3) 671–676.CrossRefGoogle Scholar
Giraudo, S. (2020). Tree series and pattern avoidance in syntax trees. Journal of Combinatorial Theory A 176.CrossRefGoogle Scholar
Giraudo, S. (2022). Mockingbird lattices. Formal Power Series and Algebraic Combinatorics 86B (3).Google Scholar
Hindley, J. R. and Seldin, J. P. (2008). Lambda-Calculus and Combinators, an Introduction, Cambridge, Cambridge University Press.CrossRefGoogle Scholar
Khoroshkin, A. and Piontkovski, D. (2015). On generating series of finitely presented operads. Journal of Algebra 426 377–429.Google Scholar
Kreweras, G. (1972). Sur les partitions non croisées d’un cycle. Discrete Mathematics 1 (4) 333–350.CrossRefGoogle Scholar
Probst, D. and Studer, T. (2001). How to normalize the Jay. Theoretical Computer Science 254 (1–2) 677–681.CrossRefGoogle Scholar
Rosen, B. K. (1973). Tree-manipulating systems and Church-Rosser theorems. Journal of the Association for Computing Machinery 20 160–187.CrossRefGoogle Scholar
Schönfinkel, M. (1924). Über die Bausteine der mathematischen Logik. Mathematische Annalen 92 305–316.CrossRefGoogle Scholar
Slo Sloane, N. J. A. The On-Line Encyclopedia of Integer Sequences. https://oeis.org/.Google Scholar
Smullyan, R. (1985). To Mock a Mockingbird, New York, Alfred A. Knopf, Inc.Google Scholar
Stanley, R. P. (1975). The Fibonacci lattice. Fibonacci Quarterly 13 (3) 215–232.Google Scholar
Statman, R. (1989). The word problem for Smullyan’s lark combinator is decidable. Journal of Symbolic Computation 7 (2) 103–112.CrossRefGoogle Scholar
Statman, R. (2000). On the word problem for combinators. In: 11th International Conference on Rewriting Techniques and Applications, Lecture Notes in Computer Science, vol. 1833, 203–213.CrossRefGoogle Scholar
Stanley, R. P. (2011). Enumerative Combinatorics, 2nd ed., vol. 1, Cambridge, Cambridge University Press.CrossRefGoogle Scholar
Statman, R. (2011). To type a Mockingbird. Unpublished. Draft available at http://tlca.di.unito.it/PAPER/TypeMock.pdf.Google Scholar
Statman, R. (2017). Some tweets about Mockingbirds. In: Raymond Smullyan on Self Reference, Outstanding Contributions to Logic, vol. 14, Cham, Springer, 113–122.CrossRefGoogle Scholar
Sprenger, M. and Wymann-Böni, M. (1993). How to decide the lark. Theoretical Computer Science 110 (2) 419–432.CrossRefGoogle Scholar
Tamari, D. (1962). The algebra of bracketings and their enumeration. Nieuw Archief voor Wiskunde 10 (3) 131–146.Google Scholar
Taylor, W. (1993). Abstract clone theory. In: Algebras and Orders, NATO Advanced Science Institutes, Series C: Mathematical, vol. 389, Dordrecht, Kluwer Academic Publishers, 507–530.CrossRefGoogle Scholar
Venturini Zilli, M. (1984). Reduction graphs in the lambda calculus. Theoretical Computer Science 29 (3) 251–275.CrossRefGoogle Scholar
Waldmann, J. (2000). The combinator S. Information and Computation 159 (1–2) 2–21.CrossRefGoogle Scholar
Wolfram, S. (2021). Combinators: A Centennial View, Champaign, Wolfram Media Inc.Google Scholar