What are the complexities of various term ordering decision problems?

The source page states the original problem together with its recorded qualifications and progress updates as follows.

What are the complexities of the various term ordering decision problems in the literature (see [Snyder, 1991])? Determining if a precedence exists that makes two ground terms comparable in the recursive path ordering is NP-complete [Snyder, 1991], but an inequality can be decided in $O(n^2)$, using a dynamic programming algorithm. Snyder [Snyder, 1991] 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.