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 Free Access

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?)

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