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 Linspace. Under some further considerations, we give a caracterisation of Etime with the help of the second type of computations.
Type de document :
Communication dans un congrès
Implicit computational complexity, May 1999, none, 12 p, 1999
Liste complète des métadonnées

https://hal.inria.fr/inria-00098950
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:40:43
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00098950, version 1

Collections

Citation

Guillaume Bonfante. Complexity characterisation of restrictions of KBO. Implicit computational complexity, May 1999, none, 12 p, 1999. 〈inria-00098950〉

Partager

Métriques

Consultations de la notice

79