Seminar on: "Light logics for implicit computational complexity and resource analysis"
Marco Gaboardi
UniversitÓ di Torino

DEI-Seminar Room
February 17th, 2010


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

Research area:
Advanced software architectures and methodologies