HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

The Light Lexicographic path Ordering

Adam Cichon 1 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 introduce syntactic restrictions of the lexicographic path ordering to obtain the Light Lexicographic Path Ordering. We show that the light lexicographic path ordering leads to a characterisation of the functions computable in space bounded by a polynomial in the size of the inputs.
Document type :
Conference papers
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:52:04 AM
Last modification on : Friday, February 4, 2022 - 3:22:35 AM


  • HAL Id : inria-00099238, version 1



Adam Cichon, Jean-Yves Marion. The Light Lexicographic path Ordering. Workshop RULE'2000, Sep 2000, Montréal, Canada, 17 p. ⟨inria-00099238⟩



Record views