[Submit a comment] [RTALooP home] [Index] [Previous] [Next]  [Postscript] [PDF] [BibTeX Source] [LaTeX Source] 
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

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 nonterminating.
Termination of this system has been shown by Hofbauer and Waldmann [HW05]. The derivational complexity of this system is open, see Problem 105.
[Submit a comment] [RTALooP home] [Index] [Previous] [Next]  [Postscript] [PDF] [BibTeX Source] [LaTeX Source] 