Execution time of λ-terms via denotational semantics and intersection types

Daniel de Carvalho

Mathematical Structures in Computer Science · 2017 · 76 citations · 20 references

Concepts

Abstract

The multiset-based relational model of linear logic induces a semantics of the untyped λ-calculus, which corresponds with a non-idempotent intersection type system, System R . We prove that, in System R , the size of type derivations and the size of types are closely related to the execution time of λ-terms in a particular environment machine, Krivine's machine.

References

20