\documentclass{rtaloop}
\rtalabel{rpo-complexity}

\begin{document}
\begin{problem}{Wayne Snyder}{}{April 1991} 

\begin{abstract}
What are the complexities of various term ordering decision problems?
\end{abstract}

What are the complexities of the various term ordering decision problems in
the literature (see \cite{D87:jsc})? Determining if a precedence exists that
makes two ground terms comparable in the recursive path ordering is
NP-complete \cite{KrN85:tcs}, but an inequality can be decided in $O(n^2)$,
using a dynamic programming algorithm. Snyder \cite{S91:bu} has shown that the
lexicographic path ordering can be done in $O(n \log n)$ in the ground case
with a total precedence, but the technique doesn't extend to non-total
precedences or to terms with variables.

\end{problem}
\end{document}