The aim of Implicit Computational Complexity is to provide abstract descriptions of time and space complexity classes by means of formal tools which are independent from the interpreter architecture and from explicit time or space constraints.
Recently, the structural approach to implicit computational complexity based on linear logic has received particular attention.
In this talk I overview this approach presenting the main motivations and the relations with resource usage analysis.
I summarize the main results obtained so far in this area with a focus on the new methodologies. I show how to use these results in order to design type systems for functional languages and I conclude by suggesting some research directions for developing resource usage analysis procedures for functional programs.
Prof. Matteo Pradella
Area di ricerca:
Metodologie e architetture software avanzate