Logic in Computer Science (LICS 1995)

Paper: New Notions of Reduction and Non-Semantic Proofs of Strong Beta- Normalization in Typed Lambda Calculi (at LICS 1995)

Authors: A.J. Kfoury J.B. Wells

Abstract

Two notions of reduction for terms of the lambda calculus are introduced and the question of whether a lambda term is strongly beta-normalizing is reduced to the question of whether a lambda term is merely normalizing under one of the notions of reduction. This gives a method to prove strong beta-normalization for typed lambda calculi. Instead of the usual semantic proof style based on Tait's realizability or Girard's ``candidats de r\'eductibilit\'e'', termination can be proved using a decreasing metric over a well-founded ordering. This proof method is applied to the simply-typed lambda calculus and the system of intersection types, giving the first non-semantic proof for a polymorphic extension of the lambda calculus.

BibTeX

  @InProceedings{KfouryWells-NewNotionsofReducti,
    author = 	 {A.J. Kfoury and J.B. Wells},
    title = 	 {New Notions of Reduction and Non-Semantic Proofs of Strong Beta- Normalization in Typed Lambda Calculi},
    booktitle =  {Proceedings of the Tenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1995},
    year =	 1995,
    editor =	 {Dexter Kozen},
    month =	 {June}, 
    pages =      {311-321},
    location =   {San Diego, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }