In this paper the BCD intersection type discipline 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 two. 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 BCD'83. 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 three. Its major feature is the absence of the type omega. We will show that this system gives rise to a filter lambda I-model and that type assignment without omega is complete for the lambda I-calculus. Finally we will prove that a lambda term is typeable in this system if and only if it is strongly normalizable.
pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.