[Submit a comment] [RTALooP home] [Index] [Previous] [Next]  [Postscript] [PDF] [BibTeX Source] [LaTeX Source] 
Originator: Johannes Waldmann (Talk at RTA’06)
Date: August 2006
Summary: Derivational complexity of replacing two successive occurrences of the same symbol in a string
The following string rewrite system is known to be terminating [HW05], see Problem 104.

Is the derivational complexity polynomially bounded? (It is at least quadratic.).
There is a quadratic bound on the length of derivation sequences [Adi09].
[Submit a comment] [RTALooP home] [Index] [Previous] [Next]  [Postscript] [PDF] [BibTeX Source] [LaTeX Source] 