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

**Assaf J. Kfoury Joe 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 = {Assaf J. Kfoury and Joe 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 Symposium on Logic in Computer Science (LICS 1995)}, year = {1995}, month = {June}, pages = {311--321}, location = {San Diego, CA, USA}, publisher = {IEEE Computer Society Press} }