Synthesis of Quasi-interpretations

Guillaume Bonfante 1 Jean-Yves Marion 1 Jean-Yves Moyen 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 : This paper presents complexity results by showing that the synthesis of MaxPoly quasi-interpretations over reals is decidable in exponential time with fixed polynomial degrees and fixed max-degree and that the synthesis ofMaxPlus quasi-interpretations over reals is NPtime-complete with fixed multiplicative degrees and fixed max-degree. Quasi-interpretations are a tool that allows to control resources like the runtime, the runspace or the size of a result in a program execution. Quasi-interpretations assign to each program symbol a numerical function which is compatible with the computational semantics and roughly speaking provide an upper bound on sizes of intermediate values computed.
Type de document :
Communication dans un congrès
Seventh International Workshop on Logic and Computational Complexity - LCC 2005, Jun 2005, Chicago/USA, 2005
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00000660
Contributeur : Romain Péchoux <>
Soumis le : jeudi 10 novembre 2005 - 23:31:59
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : mardi 7 septembre 2010 - 16:27:50

Fichier

Identifiants

  • HAL Id : inria-00000660, version 1

Collections

Citation

Guillaume Bonfante, Jean-Yves Marion, Jean-Yves Moyen, Romain Péchoux. Synthesis of Quasi-interpretations. Seventh International Workshop on Logic and Computational Complexity - LCC 2005, Jun 2005, Chicago/USA, 2005. 〈inria-00000660〉

Partager

Métriques

Consultations de la notice

226

Téléchargements de fichiers

91