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.
https://hal.inria.fr/inria-00098689
Contributor : Publications Loria
<>
Submitted on : Tuesday, September 26, 2006 - 8:16:58 AM
Last modification on : Monday, September 30, 2019 - 3:36:04 PM
Long-term archiving on : Wednesday, March 29, 2017 - 12:30:16 PM
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⟩
