Intensional semantics, abstract interpretation and complexity estimates

Eugenio Moggi
Università degli Studi di Genova

We address the issue of analyzing the complexity of programs written in a (higher order) programming language. The category Cpo2 is proposed as the appropriate setting for an intensional semantics, capturing the exact complexity of programs. Complexity estimates, either in the form of lower or upper bounds, are obtained via abstract interpretation in a category A of complete lattices. The abstract and intensional interpretations are related through logical relations.

This is joint work with Daniela Archieri. For the full paper see: ftp://ftp.disi.unige.it/person/MoggiE/papers/int-sem.dvi.gz


Eugenio Moggi

Dipartimento di Informatica e Scienze dell'Informazione
Università degli Studi di Genova
via Dodecaneso 35
16146 Genova
Italy
Email: moggi@venus.disi.unige.it
Home page: http://www.disi.unige.it/person/MoggiE

Back to the list of talks