Switch to: References

Add citations

You must login to add citations.
  1. Upper Bounds for Standardizations and an Application.Hongwei Xi - 1999 - Journal of Symbolic Logic 64 (1):291-303.
    We present a new proof for the standardization theorem in $\lambda$-calculus, which is largely built upon a structural induction on $\lambda$-terms. We then extract some bounds for the number of $\beta$-reduction steps in the standard $\beta$-reduction sequence obtained from transforming a given $\beta$-reduction sequence, sharpening the standardization theorem. As an application, we establish a super exponential bound for the lengths of $\beta$-reduction sequences from any given simply typed $\lambda$-terms.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Analytic proof systems for λ-calculus: the elimination of transitivity, and why it matters. [REVIEW]Pierluigi Minari - 2007 - Archive for Mathematical Logic 46 (5-6):385-424.
    We introduce new proof systems G[β] and G ext[β], which are equivalent to the standard equational calculi of λβ- and λβη- conversion, and which may be qualified as ‘analytic’ because it is possible to establish, by purely proof-theoretical methods, that in both of them the transitivity rule admits effective elimination. This key feature, besides its intrinsic conceptual significance, turns out to provide a common logical background to new and comparatively simple demonstrations—rooted in nice proof-theoretical properties of transitivity-free derivations—of a number (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation