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
Conference papers

Quasi-friendly sup-interpretations

Jean-Yves Marion 1 Romain Péchoux 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In a previous paper, the sup-interpretation method was proposed as a new tool to control memory resources of first order functional programs with pattern matching by static analysis. Basically, a sup-interpretation provides an upper bound on the size of function outputs. In this former work, a criterion, which can be applied to terminating as well as non-terminating programs, was developed in order to bound polynomially the stack frame size. In this paper, we suggest a new criterion which captures more algorithms computing values polynomially bounded in the size of the inputs. Since this work is related to quasi-interpretations, we compare the two notions obtaining two main features. The first one is that, given a program, we have heuristics for finding a sup-interpretation when we consider polynomials of bounded degree. The other one consists in the characterizations of the set of function computable in polynomial time and in polynomial space.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

Contributor : Romain Péchoux Connect in order to contact the contributor
Submitted on : Thursday, October 26, 2006 - 9:29:57 PM
Last modification on : Friday, February 4, 2022 - 3:30:23 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 6:13:16 PM


  • HAL Id : inria-00110245, version 1



Jean-Yves Marion, Romain Péchoux. Quasi-friendly sup-interpretations. 8th International Workshop on Logic and Computational Complexity - LCC 2006 - LICS affiliated Workshop, James Royer, Aug 2006, Seattle/Etats-Unis. ⟨inria-00110245⟩



Record views


Files downloads