Complete restrictions of the intersection type discipline

AbstractIn this paper the intersection type discipline as defined in Barendregt (1983) is studied. We will present two different and independent complete restrictions of the intersection type discipline.The first restricted system, the strict type assignment system, is presented in Section 2. Its major feature is the absence of the derivation rule (⩽) and it is based on a set of strict types. We will show that these together give rise to a strict filter lambda model that is essentially different from the one presented in Barendregt. We will show that the strict type assignment system is the nucleus of the full system, i.e. for every derivation in the intersection type discipline there is a derivation in which (⩽) is used only at the very end. Finally we will prove that strict type assignment is complete for inference semantics.The second restricted system is presented in Section 3. Its major feature is the absence of the type ω. We will show that this system gives rise to a filter λ I-model and that type assignment without ω is complete for the λ I-calculus. Finally we will prove that a lambda term is typeable in this system if and only if it is strongly normalizable