Characterisation of normalisation properties for λμ using Strict negated intersection types
File(s)Lmu-Strict.pdf (2.17 MB)
Accepted version
Author(s)
van Bakel, Steffen
Type
Journal Article
Abstract
We show characterisation results for normalisation, head-normalisation, and strong normalisation for λ μ using intersection types. We reach these results for a strict notion of type assignment for λ μ that is the natural restriction of the domain-based system of van Bakel et al. (2011) for λ μ by limiting the type inclusion relation to just intersection elimination. We show that this system respects β μ-equality, by showing both soundness and completeness results. We then define a notion of reduction on derivations that corresponds to cut-elimination, and show that this is strongly normalisable.
We use this strong normalisation result to show an approximation result, and through that a characterisation of head-normalisation. Using the approximation result, we show that there is a very strong relation between the system of van Bakel et al. (2011) and ours.
We then introduce a notion of type assignment that eliminates ω as an assignable type, and show, using the strong normalisation result for derivation reduction, that all terms typeable in this system are strongly normalisable as well, and show that all strongly normalisable terms are typeable.
We conclude by adding type variables to our system, and show that system essentially is that of van Bakel (2010b).
We use this strong normalisation result to show an approximation result, and through that a characterisation of head-normalisation. Using the approximation result, we show that there is a very strong relation between the system of van Bakel et al. (2011) and ours.
We then introduce a notion of type assignment that eliminates ω as an assignable type, and show, using the strong normalisation result for derivation reduction, that all terms typeable in this system are strongly normalisable as well, and show that all strongly normalisable terms are typeable.
We conclude by adding type variables to our system, and show that system essentially is that of van Bakel (2010b).
Date Issued
2018-02-15
Date Acceptance
2017-09-01
Citation
ACM Transactions on Computational Logic, 2018, 19 (1), pp.1-47
ISSN
1529-3785
Publisher
Association for Computing Machinery (ACM)
Start Page
1
End Page
47
Journal / Book Title
ACM Transactions on Computational Logic
Volume
19
Issue
1
Copyright Statement
© 2018 ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Computational Logic, 19, (15 Feb 2018) https://dl.acm.org/doi/10.1145/3149823
Subjects
Computation Theory & Mathematics
0101 Pure Mathematics
0801 Artificial Intelligence and Image Processing
0802 Computation Theory and Mathematics
Publication Status
Published
Article Number
ARTN 3