A characterization of polynomial complexity classes using dependency pairs

Jean-Yves Marion 1 Romain Péchoux 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : The dependency pair method has already shown its power in proving termination of term rewriting systems. We adapt this framework using polynomial assignments in order to characterize with two distinct criteria the set of the functions computable in polynomial time and the set of the functions computable in polynomial space. To our knowledge, this is a first attempt to capture complexity classes using of the dependency pair method. The characterizations presented are inspired by previous works on implicit computational complexity, and, particularly, by the notions of quasi-interpretation and sup-interpretation. Both criteria are decidable so that we can synthesize resource upper-bounds.
Type de document :
Rapport
[Research Report] 2007, pp.12
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00155287
Contributeur : Romain Péchoux <>
Soumis le : dimanche 17 juin 2007 - 18:39:24
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : jeudi 8 avril 2010 - 20:32:17

Fichier

dependency.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00155287, version 1

Collections

Citation

Jean-Yves Marion, Romain Péchoux. A characterization of polynomial complexity classes using dependency pairs. [Research Report] 2007, pp.12. 〈inria-00155287〉

Partager

Métriques

Consultations de la notice

201

Téléchargements de fichiers

86