Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00098750
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:32:57 AM
Last modification on : Friday, February 4, 2022 - 3:30:50 AM
Long-term archiving on: : Friday, November 25, 2016 - 11:49:13 AM

Identifiers

  • 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⟩

Share

Metrics

Record views

120

Files downloads

45