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

详细信息    查看全文

• 作者：Erika De Benedetti ^{debenede@di.unito.it" class="auth_mail" title="E-mail the corresponding author} ; Simona Ronchi Della Rocca ; ^{ronchi@di.unito.it" class="auth_mail" title="E-mail the corresponding author}
• 刊名：Information and Computation
• 出版年：2016
• 出版时间：June 2016
• 年：2016
• 卷：248
• 期：Complete
• 页码：195-214
• 全文大小：497 K

文摘

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.