hal-00591862, version 1
Quasi-interpretations a way to control resources
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:
- CNRS : UMR7503 – INRIA – Université de Lorraine
- 2:
- 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
- http://hal.archives-ouvertes.fr/hal-00591862
- 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


Associated documents
Export