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.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.inria.fr/inria-00098689
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:16:58 AM
Last modification on : Thursday, January 11, 2018 - 6:19:48 AM
Document(s) archivé(s) le : Wednesday, March 29, 2017 - 12:30:16 PM

Identifiers

  • HAL Id : inria-00098689, version 1

Collections

Citation

Guillaume Bonfante, Adam Cichon, Jean-Yves Marion, Hélène Touzet. Complexity classes and rewrite systems with polynomial interpretation. CSl'98, 1998, Brno, République Tchèque, pp.372-384. ⟨inria-00098689⟩

Share

Metrics

Record views

123

Files downloads

80