Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Reductions of residuals are finite

Author: R. Hindley
Journal: Trans. Amer. Math. Soc. 240 (1978), 345-361
MSC: Primary 03B40
MathSciNet review: 489603
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An important theorem of the $ \lambda \beta K$-calculus which has not been fully appreciated up to now is D. E. Schroer's finiteness theorem (1963), which states that all reductions of residuals are finite.

The present paper gives a new proof of this theorem and extends it from $ \lambda \beta $-reduction to $ \lambda \beta \eta $-reduction and reductions with certain extra operators added, for example the pairing, iteration and recursion operators. Combinatory weak reduction, with or without extra operators, is also included.

References [Enhancements On Off] (What's this?)

  • [1] H. P. Barendregt, J. Bergstra, J. W. Klop and H. Volken, Degrees, reductions and representability in the lambda calculus, Math. Instituut, Budapestlaan 6, Utrecht, preprint 22, 1976. MR 0398760 (53:2611)
  • [2] A. Church and J. B. Rosser, Some properties of conversion, Trans. Amer. Math. Soc. 39 (1936), 472-482. MR 1501858
  • [3] H. B. Curry, A study of generalized standardization in combinatory logic, Lecture Notes in Math., vol. 500, Springer-Verlag, Berlin and New York, 1974, pp. 44-55. MR 0409128 (53:12890)
  • [4] H. B. Curry and R. Feys, Combinatory logic. I, North-Holland, Amsterdam, 1958. MR 20 #817. MR 0094298 (20:817)
  • [5] H. B. Curry, R. Hindley and J. P. Seldin, Combinatory logic. II, North-Holland, Amsterdam, 1972.
  • [6] R. Hindley, An abstract form of the Church-Rosser theorem. I, J. Symbolic Logic 34 (1969), 545-560. MR 46 #1578. MR 0302434 (46:1578)
  • [7] -, An abstract Church-Rosser theorem. II: Applications, J. Symbolic Logic 39 (1974), 1-21. MR 50 #61. MR 0347558 (50:61)
  • [8] -, The equivalence of complete reductions, Trans. Amer. Math. Soc. 229 (1977), 227-248. MR 0444445 (56:2798)
  • [9] -, Standard and normal reductions, Trans. Amer. Math. Soc. (to appear). MR 492300 (80a:03018)
  • [10] R. Hindley, B. Lercher and J. P. Seldin, Introduction to combinatory logic, Cambridge Univ. Press, London and New York, 1972. MR 49 #25. MR 0335242 (49:25)
  • [11] J. M. E. Hyland, A simple proof of the Church-Rosser theorem, unpublished manuscript available from J. Hyland, Math. Inst., 24-29 St. Giles, Oxford, England.
  • [12] D. E. Schroer, The Church-Rosser theorem, Doctoral thesis, Cornell University, Ithaca, N. Y., 1965.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03B40

Retrieve articles in all journals with MSC: 03B40

Additional Information

Keywords: Reduction, residuals, relative reduction, development, lambda-calculus, combinators, finiteness-of-developments theorem
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society