A classification of intersection type systems

Journal of Symbolic Logic 67 (1):353-368 (2002)
The first system of intersection types, Coppo and Dezani [3], extended simple types to include intersections and added intersection introduction and elimination rules (( $\wedge$ I) and ( $\wedge$ E)) to the type assignment system. The major advantage of these new types was that they were invariant under β-equality, later work by Barendregt, Coppo and Dezani [1], extended this to include an (η) rule which gave types invariant under βη-reduction. Urzyczyn proved in [6] that for both these systems it is undecidable whether a given intersection type is empty. Kurata and Takahashi however have shown in [5] that this emptiness problem is decidable for the sytem including (η), but without ( $\wedge$ I). The aim of this paper is to classify intersection type systems lacking some of ( $\wedge$ I), ( $\wedge$ E) and (η), into equivalence classes according to their strength in typing λ-terms and also according to their strength in possessing inhabitants. This classification is used in a later paper to extend the above (un)decidability results to two of the five inhabitation-equivalence classes. This later paper also shows that the systems in two more of these classes have decidable inhabitation problems and develops algorithms to find such inhabitants
Keywords No keywords specified (fix it)
Categories (categorize this paper)
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 9,357
External links
  •   Try with proxy.
  •   Try with proxy.
  • Through your library Configure
    References found in this work BETA

    No references found.

    Citations of this work BETA

    No citations found.

    Similar books and articles

    Monthly downloads

    Sorry, there are not enough data points to plot this chart.

    Added to index


    Total downloads

    1 ( #306,128 of 1,088,623 )

    Recent downloads (6 months)


    How can I increase my downloads?

    My notes
    Sign in to use this feature

    Start a new thread
    There  are no threads in this forum
    Nothing in this forum yet.