\documentclass{rtaloop}
\rtalabel{length-preserving}

\begin{document}
\begin{solvedproblem}{Yves M\'etivier}{\cite{M85:tcs}}{April 1991}

\begin{abstract}
  What is the best bound on the length of a derivation for a one-rule
  length-preserving string-rewriting system?
\end{abstract}

What is the best bound on the length of a derivation for a one-rule
length-preserving string-rewriting (semi-Thue) system?
Is it $O(n^2)$ ($n$ is the size of the initial term) as conjectured
in \cite{M85:tcs}, or $O(n^k)$ ($k$ is the size of the rule) as proved there.

\begin{remark}
  The upper bound is $n^2/4$ where n denotes the length of the initiating
  string \cite{Bertrand-94}. The bound is reached by the derivation from
  $b^{n/2} a^{n/2}$ for the string rewriting system $\{ba \rightarrow ab\}$.

  More about the history of this problem in the context of the question of
  one-rule termination can be found in \cite{Dershowitz05OpenClosed}.
\end{remark}

\end{solvedproblem}
\end{document}