A type assignment for λ-calculus complete both for FPTIME and strong normalization

One of the aims of Implicit Computational Complexity is the design of programming languages with bounded computational complexity. One of the most promising approaches to this aim is based on the use of lambda-calculus as paradigmatic programming language and the design of type assignment systems for lambda-terms, where types guarantee both the functional correctness and the complexity bound. Along this line, we propose a system of stratified types, inspired by intersection types, where intersection is a non-associative operator. This system is correct and complete for polynomial time when a uniform coding scheme is considered; moreover, all the strongly normalizing terms are typed in it, thus increasing the typing power with respect to the previous proposals, based on Light Logics.

Authors

• Erika De Benedetti
• Simona Ronchi Della Rocca

Keywords

No keywords are indexed for this paper.