Quasi-interpretation: a way to control ressources

Guillaume Bonfante 1 Jean-Yves Marion 1 Jean-Yves Moyen 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : This paper presents in a reasoned way our works on resource analysis by quasi-interpretations. The controlled resources are typically the runtime, the runspace or the size of a result in a program execution. Quasi-interpretations assign to each program symbol a numerical function which is compatible with the computational semantics. The quasi-interpretation method offers several advantages. It allows to predict system complexity, may provide hints in order to optimize the execution, it gives resource certificates, and finally, can be automated. We propose a method to determine if a program admits or not a quasi-interpretation in a broad class which is relevant for feasible computations. By combining the quasi-interpretation method with termination tools (here term orderings), we have obtained several characterizations of complexity classes starting from Ptime and Pspace.
Type de document :
[Intern report] 2005, pp.35
Liste complète des métadonnées

Contributeur : Agnès Vidard <>
Soumis le : mardi 18 avril 2006 - 09:41:44
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48


  • HAL Id : inria-00001257, version 1



Guillaume Bonfante, Jean-Yves Marion, Jean-Yves Moyen. Quasi-interpretation: a way to control ressources. [Intern report] 2005, pp.35. 〈inria-00001257〉



Consultations de la notice