Complexity classes and rewrite systems with polynomial interpretation

Guillaume Bonfante 1 Adam Cichon Jean-Yves Marion Hélène Touzet
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Résumé : Les systèmes de réécriture munis d'une interprétation polynomiale ont la propriété de terminaison forte. En fait, et a priori, ainsi que le font remarquer Huet et Oppen, on peut supposer que de telles interprétations sont un bon candidat pour l'étude des fonctions dont la complexité est faible. Ainsi, Cichon et Lescanne ont calculé des bornes de complexité de fonctions unaires selon le type d'interpétation du successeur. Nous nous intéressons plus particulièrement aux fonctions sur les mots qui sont calculables par des systèmes de réécriture munis d'une interprétation polynomiale. Nous les classifions selon un critère basé sur la forme de l'interprétation des constructeurs. Ceci nous conduit à la définition de trois classes qui s'avèrent être exactement : la classe des fonctions calculables en temps polynomial, en temps linéairement exponentiel et en temps doublement exponentiel. d'autre part, nous donnons une caractérisation de l'espace linéaire.
Mots-clés : Réécriture Rewriting systems Polynomial interpretation PTIME LINSPACE EXP-TIME Interprétation polynomiale DEXP-TIME
Type de document :
Communication dans un congrès
Gottlob, Georg and Etienne, Grand and katrin, Seyr. CSl'98, 1998, Brno, République Tchèque, Springer, 1584, pp.372-384, 1998, Lecture Notes in Computer Science
Liste complète des métadonnées
https://hal.inria.fr/inria-00098689
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:16:58
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : mercredi 29 mars 2017 - 12:30:16

Fichiers

98-R-060.pdf

Identifiants

  • HAL Id : inria-00098689, version 1

Collections

INRIA | LORIA | UNIV-LORRAINE

Citation

Guillaume Bonfante, Adam Cichon, Jean-Yves Marion, Hélène Touzet. Complexity classes and rewrite systems with polynomial interpretation. Gottlob, Georg and Etienne, Grand and katrin, Seyr. CSl'98, 1998, Brno, République Tchèque, Springer, 1584, pp.372-384, 1998, Lecture Notes in Computer Science. 〈inria-00098689〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

67

Contact


archive-ouverte@inria.fr