Quasi-interpretations a way to control resources - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles Theoretical Computer Science Year : 2011

Quasi-interpretations a way to control resources

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 allow analyzing system complexity. A quasi-interpretation is a numerical assignment, which provides an upper bound on computed func- tions and which is compatible with the program operational semantics. Quasi- interpretation method offers several advantages: (i) It provides hints in order to optimize an execution, (ii) it gives resource certificates, and (iii) finding quasi- interpretations is decidable for a broad class which is relevant for feasible com- putations. By combining the quasi-interpretation method with termination tools (here term orderings), we obtained several characterizations of complexity classes starting from Ptime and Pspace.
Fichier principal
Vignette du fichier
tcs.pdf (315.79 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-00591862 , version 1 (10-05-2011)

Identifiers

Cite

Guillaume Bonfante, Jean-Yves Marion, Jean-Yves Moyen. Quasi-interpretations a way to control resources. Theoretical Computer Science, 2011, 412 (25), pp.2776-2796. ⟨10.1016/j.tcs.2011.02.007⟩. ⟨hal-00591862⟩
246 View
295 Download

Altmetric

Share

Gmail Facebook X LinkedIn More