3543 articles – 5273 references  [version française]

hal-00591862, version 1

Quasi-interpretations a way to control resources

Guillaume Bonfante () 1, Jean-Yves Marion () 1, Jean-Yves Moyen () 2

Theoretical Computer Science 412, 25 (2011) 2776-2796

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.

  • 1:  CARTE (INRIA Nancy - Grand Est / LORIA)
  • CNRS : UMR7503 – INRIA – Université de Lorraine
  • 2:  Laboratoire d'informatique de Paris-nord (LIPN)
  • CNRS : UMR7030 – Université Paris XIII - Paris Nord
  • Domain : Computer Science/Logic in Computer Science
  • Keywords : Implicit complexity – Quasi-interpretation – Termination orderings
 
  • hal-00591862, version 1
  • oai:hal.archives-ouvertes.fr:hal-00591862
  • From: 
  • Submitted on: Tuesday, 10 May 2011 21:55:07
  • Updated on: Tuesday, 24 May 2011 10:32:01