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
DOI: https://doi.org/10.1090/S0002-9947-1978-0489603-9
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

DOI: https://doi.org/10.1090/S0002-9947-1978-0489603-9
Keywords: Reduction, residuals, relative reduction, development, lambda-calculus, combinators, finiteness-of-developments theorem
Article copyright: © Copyright 1978 American Mathematical Society