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

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 Connect in order to contact the contributor
Submitted on : Monday, September 25, 2006 - 5:03:37 PM
Last modification on : Friday, February 4, 2022 - 3:32:28 AM


  • 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