Quasi-interpretation: a way to control ressources - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2005

Quasi-interpretation: a way to control ressources

Résumé

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.
Fichier non déposé

Dates et versions

inria-00001257 , version 1 (18-04-2006)

Identifiants

  • HAL Id : inria-00001257 , version 1

Citer

Guillaume Bonfante, Jean-Yves Marion, Jean-Yves Moyen. Quasi-interpretation: a way to control ressources. [Intern report] 2005, pp.35. ⟨inria-00001257⟩
91 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More