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

Complexity characterisation of restrictions of KBO

Guillaume Bonfante 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Termination proofs of rewrite systems using the Knuth-Bendix ordering, {\sckbo}, imply multiply-recursive bounds on the lengths of derivations. Hofbauer has studied two restrictions of {\sc kbo}. The first is a restriction to the use of positive weights, the second is a restriction on the signature which is only allowed to contain at most unary symbols. In both cases, Hofbauer proves the derivation lengths to be bounded exponentially. We prove that it correspond exactly to computations in {\sc Linspace}. Under some further considerations, we give a caracterisation of {\sc Etime} with the help of the second type of computations.
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:51:41 AM
Last modification on : Friday, February 4, 2022 - 3:21:40 AM


  • HAL Id : inria-00099196, version 1



Guillaume Bonfante. Complexity characterisation of restrictions of KBO. Implicit computational complexity, J.Y. Marion, May 2000, Santa Barbara, US, pp.12. ⟨inria-00099196⟩



Record views