The Light Lexicographic path Ordering

Adam Cichon (1) , Jean-Yves Marion (1)

1 CALLIGRAMME - Linear logic, proof networks and categorial grammars

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.

Mots clés: ordre de terminaison; termination ordering; implicit complexity; complexité implicite; poly-space

Domaines: Autre [cs.OH]

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