Quasi-interpretations and small space bounds

Guillaume Bonfante 1 Jean-Yves Marion 1 Jean-Yves Moyen 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Quasi-interpretations are an useful tool to control resource usage of term rewriting systems, either time or space. They not only combine well with path orderings and provide characterizations of usual complexity classes but also give hints in order to optimize the program. Moreover, the existence of a quasi-interpretation is decidable. In this paper, we present some more characterizations of complexity classes using quasi-interpretations. We mainly focus on small space-bounded complexity classes. On one hand, by restricting quasi-interpretations to sums (that is allowing only affine quasi-interpretations), we obtain a characterization of LINSpace.On the other hand, with a strong tiering discipline on programs, quasi-interpretations yields a characterization of LOGSpace. Lastly, we give two new characterizations of Pspace: in the first, the quasi-interpretation has to be strictly decreasing on each rule and in the second, some linearity constrains are added to the system but no assumption concerning the termination proof is made.
Type de document :
Rapport
[Research Report] 2005, pp.19
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00001234
Contributeur : Agnès Vidard <>
Soumis le : mardi 11 avril 2006 - 11:47:23
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 10:39:07

Fichiers

 Accès restreint
Fichier visible le : jamais

Connectez-vous pour demander l'accès au fichier

Identifiants

  • HAL Id : inria-00001234, version 1

Collections

Citation

Guillaume Bonfante, Jean-Yves Marion, Jean-Yves Moyen. Quasi-interpretations and small space bounds. [Research Report] 2005, pp.19. 〈inria-00001234〉

Partager

Métriques

Consultations de la notice

181