Skip to Main content Skip to Navigation
Conference papers

The Inhabitation Problem for Non-idempotent Intersection Types

Abstract : The inhabitation problem for intersection types is known to be undecidable. We study the problem in the case of non-idempotent intersection, and we prove decidability through a sound and complete algorithm. We then consider the inhabitation problem for an extended system typing the λ-calculus with pairs, and we prove the decidability in this case too. The extended system is interesting in its own, since it allows to characterize solvable terms in the λ-calculus with pairs.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-01402082
Contributor : Hal Ifip <>
Submitted on : Thursday, November 24, 2016 - 11:09:54 AM
Last modification on : Friday, March 27, 2020 - 3:01:31 AM
Long-term archiving on: : Tuesday, March 21, 2017 - 5:37:37 AM

File

978-3-662-44602-7_26_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Antonio Bucciarelli, Delia Kesner, Simona Ronchi Della Rocca. The Inhabitation Problem for Non-idempotent Intersection Types. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.341-354, ⟨10.1007/978-3-662-44602-7_26⟩. ⟨hal-01402082⟩

Share

Metrics

Record views

349

Files downloads

728