Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

On Strong Normalization in the Intersection Type Discipline
Extended Abstract

Gérard Boudol5

(5)  INRIA Sophia Antipolis, BP 93, 06902 Sophia Antipolis Cedex, France
Abstract
We give a proof for the strong normalization result in the intersection type discipline, which we obtain by putting together some well-known results and proof techniques. Our proof uses a variant of Klop’s extended λ-calculus, for which it is shown that strong normalization is equivalent to weak normalization. This is proved here by means of a finiteness of developments theorem, obtained following de Vrijer’s combinatory technique. Then we use the standard argument, formalized by Lévy as “the creation of redexes is decreasing” and implemented in proofs of weak normalization by Turing, and Coppo and Dezani for the intersection type discipline, to show that a typable expression of the extended calculus is normalizing.

Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb07
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)