[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #105 (Solved !)

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.).

Remark

There is a quadratic bound on the length of derivation sequences [Adi09].

References

[Adi09]

Sergei Adian. Upper bound on the derivational complexity in some word rewriting system. Doklady Mathematics, 80(2):679–683, October 2009.

[HW05]

Dieter Hofbauer and Johannes Waldmann. Termination of {aa → bc, bb → ac, cc → ab}. Preprint, 2005.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]