\documentclass{rtaloop}

\begin{document}
\begin{solvedproblem}{Johannes Waldmann}{(Talk at RTA'06)}{August 2006}

  \begin{abstract}
    Derivational complexity of replacing two successive occurrences of the
    same symbol in a string
  \end{abstract}
  
The following string rewrite system is known to be
terminating~\cite{HofbauerWaldmann05termination}, see \rtaproblem{104}.
\begin{eqnarray*}
  aa & \rightarrow & bc\\
  bb & \rightarrow & ac\\
  cc & \rightarrow & ab
\end{eqnarray*}
Is the derivational complexity polynomially bounded?
(It is at least quadratic.).

\begin{remark}
  There is a quadratic bound on the length of derivation sequences
  \cite{adian09doklady}.
\end{remark}


\end{solvedproblem}

\end{document}