Light Multiset path ordering and Ptime - Two is better than one

Jean-Yves Marion 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We consider term rewriting systems as a general setting for studying algorithms. We construct a termination ordering, called light multiset path ordering (LMPO), which is a restriction of the multiset path ordering. We establish that the class of programs on words which is terminating by LMPO, characterises exactly the functions computable in polynomial time.
Type de document :
Rapport
[Intern report] 99-R-106 || marion99b, 1999, 19 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00098750
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:32:57
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 11:49:13

Fichiers

Identifiants

  • HAL Id : inria-00098750, version 1

Collections

Citation

Jean-Yves Marion. Light Multiset path ordering and Ptime - Two is better than one. [Intern report] 99-R-106 || marion99b, 1999, 19 p. 〈inria-00098750〉

Partager

Métriques

Consultations de la notice

146

Téléchargements de fichiers

41