Non-idempotent intersection types and strong normalisation

DOI10.2168/LMCS-9(4:3)2013zbMATH Open1297.03010arXiv1310.1622OpenAlexW2001822718MaRDI QIDQ2851671FDOQ2851671

Alexis Bernadet, Stéphane Lengrand

Publication date: 16 October 2013

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: We present a typing system with non-idempotent intersection types, typing a term syntax covering three different calculi: the pure {lambda}-calculus, the calculus with explicit substitutions {lambda}S, and the calculus with explicit substitutions, contractions and weakenings {lambda}lxr. In each of the three calculi, a term is typable if and only if it is strongly normalising, as it is the case in (many) systems with idempotent intersections. Non-idempotency brings extra information into typing trees, such as simple bounds on the longest reduction sequence reducing a term to its normal form. Strong normalisation follows, without requiring reducibility techniques. Using this, we revisit models of the {lambda}-calculus based on filters of intersection types, and extend them to {lambda}S and {lambda}lxr. Non-idempotency simplifies a methodology, based on such filter models, that produces modular proofs of strong normalisation for well-known typing systems (e.g. System F). We also present a filter model by means of orthogonality techniques, i.e. as an instance of an abstract notion of orthogonality model formalised in this paper and inspired by classical realisability. Compared to other instances based on terms (one of which rephrases a now standard proof of strong normalisation for the {lambda}-calculus), the instance based on filters is shown to be better at proving strong normalisation results for {lambda}S and {lambda}lxr. Finally, the bounds on the longest reduction sequence, read off our typing trees, are refined into an exact measure, read off a specific typing tree (called principal); in each of the three calculi, a specific reduction sequence of such length is identified. In the case of the {lambda}-calculus, this complexity result is, for longest reduction sequences, the counterpart of de Carvalho's result for linear head-reduction sequences.

Full work available at URL: https://arxiv.org/abs/1310.1622

Recommendations

• Complexity of Strongly Normalising λ-Terms via Non-idempotent Intersection Types
• Filter models: non-idempotent intersection types, orthogonality and polymorphism
• Strong normalization through intersection types and memory
• An elementary proof of strong normalization for intersection types
• Intersection types for explicit substitutions

zbMATH Keywords

complexityfiltersintersection typesstrong normalisationnon-idempotenceorthogonality models

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Semantics in the theory of computing (68Q55)

Cited In (20)

• Tight typings and split bounds, fully developed
• Exact bounds for acyclic higher-order recursion schemes
• Title not available (Why is that?)
• Title not available (Why is that?)
• A semantic account of strong normalization in linear logic
• Strong normalization through intersection types and memory
• Factoring derivation spaces via intersection types
• Complexity of Strongly Normalising λ-Terms via Non-idempotent Intersection Types
• Nominal essential intersection types
• The bang calculus revisited
• The bang calculus revisited
• Reasoning About Call-by-need by Means of Types
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Inhabitation Problem for Non-idempotent Intersection Types
• Title not available (Why is that?)
• A resource aware semantics for a focused intuitionistic calculus
• Title not available (Why is that?)
• Normal-order reduction grammars
• The vectorial \(\lambda\)-calculus

This page was built for publication: Non-idempotent intersection types and strong normalisation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851671)