Church’s Semigroup Is Sq-Universal

Author Rick Statman



PDF
Thumbnail PDF

File

LIPIcs.FSCD.2021.6.pdf
  • Filesize: 434 kB
  • 6 pages

Document Identifiers

Author Details

Rick Statman
  • Carnegie Mellon University, Pittsburgh, PA, USA

Cite AsGet BibTex

Rick Statman. Church’s Semigroup Is Sq-Universal. In 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 195, pp. 6:1-6:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSCD.2021.6

Abstract

We prove Church’s lambda calculus semigroup is sq-universal.

Subject Classification

ACM Subject Classification
  • Theory of computation → Lambda calculus
Keywords
  • lambda calculus
  • Church’s semigroup
  • sq-universal

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Hendrik Pieter Barendregt. The Lambda Calculus - Its Syntax and Semantics, volume 103 of Studies in logic and the foundations of mathematics. North-Holland, 1985. Google Scholar
  2. Alonzo Church. The Calculi of Lambda Conversion. Princeton University Press, 1941. Google Scholar
  3. Haskell B. Curry and Robert Feys. Combinatory Logic, volume 1. North Holland, 1958. Google Scholar
  4. Mariangiola Dezani-Ciancaglini. Characterization of Normal Forms Possessing Inverse in the lambda-beta-eta-Calculus. Theor. Comput. Sci., 2(3):323-337, 1976. URL: https://doi.org/10.1016/0304-3975(76)90085-2.
  5. Giuseppe Jacopini. A condition for identifying two elements of whatever model of combinatory logic. In Corrado Böhm, editor, Lambda-Calculus and Computer Science Theory, Proceedings of the Symposium Held in Rome, Italy, March 25-27, 1975, volume 37 of Lecture Notes in Computer Science, pages 213-219. Springer, 1975. URL: https://doi.org/10.1007/BFb0029527.
  6. P. Neumann. The SQ-universality of some finitely presented groups. J. Austral. Math. Soc., 16:1-6, 1973. Google Scholar
  7. Richard Statman. Morphisms and Partitions of V-Sets. In Georg Gottlob, Etienne Grandjean, and Katrin Seyr, editors, Computer Science Logic, 12th International Workshop, CSL '98, Annual Conference of the EACSL, Brno, Czech Republic, August 24-28, 1998, Proceedings, volume 1584 of Lecture Notes in Computer Science, pages 313-322. Springer, 1998. URL: https://doi.org/10.1007/10703163_21.
  8. Richard Statman. Consequences of Jacopini’s Theorem: Consistent Equalities and Equations. In Jean-Yves Girard, editor, Typed Lambda Calculi and Applications, 4th International Conference, TLCA'99, L'Aquila, Italy, April 7-9, 1999, Proceedings, volume 1581 of Lecture Notes in Computer Science, pages 355-364. Springer, 1999. URL: https://doi.org/10.1007/3-540-48959-2_25.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail