Author name cluster

Erika De Benedetti

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

I&C Journal 2018 Journal Article

Characterizing polynomial and exponential complexity classes in elementary lambda-calculus

Patrick Baillot
Erika De Benedetti
Simona Ronchi Della Rocca

In this paper an implicit characterization of the complexity classes k - EXP and k - FEXP, for k ≥ 0, is given, by a type assignment system for a stratified λ-calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic (ELL), and the hierarchy of complexity classes k - EXP is characterized by a hierarchy of types.

Details DOI

I&C Journal 2016 Journal Article

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

Erika De Benedetti
Simona Ronchi Della Rocca

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.

Details DOI