Skip to Main content Skip to Navigation
Conference papers

A complex example of a simplifying rewrite system

Hélène Touzet 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : For a string rewriting system, it is known that termination by a simplification ordering implies multiply recursive complexity. This theoretical upper bound is, however, far from having been reached by known examples of rewrite systems. All known methods used to establish termination by simplification yield a primitive recursive bound. Furthermore, the study of the order types of simplification orderings suggests that the recursive path ordering is, in a broad sense, a maximal simplification ordering. This would imply that simplifying string rewrite systems cannot go beyond primitive recursion. Contradicting this intuition, we construct here a simplifying string rewriting system whose complexity is not primitive recursive. This leads to a new lower bound for the complexity of simplifying string rewriting systems
Document type :
Conference papers
Complete list of metadata
Contributor : Publications Loria <>
Submitted on : Monday, September 25, 2006 - 5:03:37 PM
Last modification on : Friday, February 26, 2021 - 3:28:03 PM


  • HAL Id : inria-00098574, version 1



Hélène Touzet. A complex example of a simplifying rewrite system. International Colloquium on Automata, Languages, and Programming - ICALP'98, Jul 1998, Aalborg, Denmark, pp.507-517. ⟨inria-00098574⟩



Record views