HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Contributor : Agnès Vidard Connect in order to contact the contributor
Submitted on : Tuesday, April 18, 2006 - 9:41:44 AM
Last modification on : Friday, February 4, 2022 - 3:30:21 AM


  • 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⟩



Record views