[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #104 (Solved !)

Originator: Hans Zantema
Date: July 2005

Summary: Termination of replacing two successive occurrences of the same symbol in a string

Start by a finite string over the alphabet {a,b,c}. As long as two consecutive symbols are the same, they may be replaced by the other two symbols in alphabetic order. So

Can this go on forever?

This problem coincides with establishing termination of the string rewrite system consisting of the three rules

  aa→bc
  bb→ac
  cc→ab

Up to renaming it coincides with problem SRS/Zantema/z086 in the termination problem data base TPDB, on which all tools failed in the Termination Competition 2005. A variant of this problem on multisets, the Chamelon Problem, is known to be non-terminating.

Remark

Termination of this system has been shown by Hofbauer and Waldmann [HW05]. The derivational complexity of this system is open, see Problem 105.

References

[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]