Exact Bounds for lengths of reductions in typed λ-calculus

Journal of Symbolic Logic 66 (3):1277-1285 (2001)
  Copy   BIBTEX

Abstract

We determine the exact bounds for the length of an arbitrary reduction sequence of a term in the typed λ-calculus with β-, ξ- and η-conversion. There will be two essentially different classifications, one depending on the height and the degree of the term and the other depending on the length and the degree of the term

Categories

Keywords

Reprint years

DOI

10.2307/2695106

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 106,951

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

A proof-theoretic treatment of λ-reduction with cut-elimination: λ-calculus as a logic programming language.Michael Gabbay - 2011 - Journal of Symbolic Logic 76 (2):673 - 699.
Term-Space Semantics of Typed Lambda Calculus.Ryo Kashima, Naosuke Matsuda & Takao Yuyama - 2020 - Notre Dame Journal of Formal Logic 61 (4):591-600.
Upper Bounds for Standardizations and an Application.Hongwei Xi - 1999 - Journal of Symbolic Logic 64 (1):291-303.
An upper bound for reduction sequences in the typed λ-calculus.Helmut Schwichtenberg - 1991 - Archive for Mathematical Logic 30 (5-6):405-408.
Minimal forms in λ-calculus computations.Corrado Böhm & Silvio Micali - 1980 - Journal of Symbolic Logic 45 (1):165-171.
The Weak Normalization of the Simply Typed λse-calculus.Ariel Arbiser, Fairouz Kamareddine & Alejandro Rios - 2007 - Logic Journal of the IGPL 15 (2):121-147.
The interpretation of unsolvable λ-terms in models of untyped λ-calculus.Rainer Kerth - 1998 - Journal of Symbolic Logic 63 (4):1529-1548.
Analyzing Godel's T Via Expanded Head Reduction Trees.Arnold Beckmann & Andreas Weiermann - 2000 - Mathematical Logic Quarterly 46 (4):517-536.
The range property fails for H.Andrew Polonsky - 2012 - Journal of Symbolic Logic 77 (4):1195-1210.
Continuous normalization for the lambda-calculus and Gödel’s T.Klaus Aehlig & Felix Joachimski - 2005 - Annals of Pure and Applied Logic 133 (1-3):39-71.

Analytics

Added to PP
2009-01-28

Downloads
101 (#224,880)

6 months
13 (#267,579)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Elementary Proof of Strong Normalization for Atomic F.Fernando Ferreira & Gilda Ferreira - 2016 - Bulletin of the Section of Logic 45 (1):1-15.
Herbrand's theorem as higher order recursion.Bahareh Afshari, Stefan Hetzl & Graham E. Leigh - 2020 - Annals of Pure and Applied Logic 171 (6):102792.

View all 8 citations / Add more citations

References found in this work

An upper bound for reduction sequences in the typed λ-calculus.Helmut Schwichtenberg - 1991 - Archive for Mathematical Logic 30 (5-6):405-408.

Add more references