The emptiness problem for intersection types
- 1 September 1999
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 64 (3) , 1195-1215
Abstract
We study the intersection type assignment system as defined by Barendregt, Coppo and Dezani. For the four essential variants of the system (with and without a universal type and with and without subtyping) we show that the emptiness (inhabitation) problem is recursively unsolvable. That is, there is no effective algorithm to decide if there is a closed term of a given type. It follows that provability in the logic of “strong conjunction” of Mints and Lopez-Escobar is also undecidable.Keywords
This publication has 12 references indexed in Scilit:
- The "Relevance" of Intersection and Union TypesNotre Dame Journal of Formal Logic, 1997
- Inhabitation in typed lambda-calculi (a syntactic approach)1997
- Decidable properties of intersection type systems1995
- Type reconstruction in finite rank fragments of the second-order λ-calculusInformation and Computation, 1992
- The completeness of provable realizability.Notre Dame Journal of Formal Logic, 1989
- Functional Characters of Solvable TermsMathematical Logic Quarterly, 1981
- Semantical Investigations in Heyting’s Intuitionistic Logic1981
- Intuitionistic propositional logic is polynomial-space completeTheoretical Computer Science, 1979
- A theory of type polymorphism in programmingJournal of Computer and System Sciences, 1978
- The Principal Type-Scheme of an Object in Combinatory LogicTransactions of the American Mathematical Society, 1969