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.
Type de document :
Communication dans un congrès
8th International Workshop on Logic and Computational Complexity - LCC 2006 - LICS affiliated Workshop, Aug 2006, Seattle/Etats-Unis, 2006
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00110245
Contributeur : Romain Péchoux <>
Soumis le : jeudi 26 octobre 2006 - 21:29:57
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : mardi 6 avril 2010 - 18:13:16

Fichier

Identifiants

  • HAL Id : inria-00110245, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

163

Téléchargements de fichiers

74