\documentclass{rtaloop}


\begin{document}
\begin{solvedproblem}{Hans Zantema}{}{July 2005}

\begin{abstract}
  Termination of replacing two successive occurrences of the same
  symbol in a string
\end{abstract}
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
\begin{itemize}
\item $aa$ may be replaced by $bc$, 
\item $bb$ may be replaced by $ac$, and 
\item $cc$ may be replaced by $ab$. 
\end{itemize}
Can this go on forever?

This problem coincides with establishing termination of the string
rewrite system
consisting of the three rules 
\begin{eqnarray*}
  aa & \rightarrow & bc\\
  bb & \rightarrow & ac\\
  cc & \rightarrow & ab
\end{eqnarray*}
Up to renaming it coincides with problem
\ahref{http://www.lri.fr/\home{marche}/tpdb/tpdb-2.0/SRS/Zantema/z086.srs}{SRS/Zantema/z086}
in the termination problem data base
\ahref{http://www.lri.fr/\home{marche}/tpdb/}{TPDB}, on which all tools failed
in the
\ahref{http://www.lri.fr/\home{marche}/termination-competition/2005/}{Termination
Competition 2005}. A variant of this problem on multisets, the
\ahref{http://www.lri.fr/\home{marche}/cameleon.html}{Chamelon Problem}, is
known to be non-terminating.

\begin{remark}
  Termination of this system has been shown by Hofbauer and
  Waldmann~\cite{HofbauerWaldmann05termination}. The derivational 
  complexity of this system is open, see \rtaproblem{105}.
\end{remark}

\end{solvedproblem}

\end{document}