[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #30

Originator: Wayne Snyder
Date: April 1991

Summary: What are the complexities of various term ordering decision problems?

What are the complexities of the various term ordering decision problems in the literature (see [Der87])? Determining if a precedence exists that makes two ground terms comparable in the recursive path ordering is NP-complete [KN85], but an inequality can be decided in O(n2), using a dynamic programming algorithm. Snyder [Sny91] has shown that the lexicographic path ordering can be done in O(n logn) in the ground case with a total precedence, but the technique doesn’t extend to non-total precedences or to terms with variables.

References

[Der87]
Nachum Dershowitz. Termination of rewriting. Journal of Symbolic Computation, 3(1&2):69–115, February/April 1987. Corrigendum: 4, 3 (December 1987), 409–410; reprinted in Rewriting Techniques and Applications, J.-P. Jouannaud, ed., pp. 69—115, Academic Press, 1987.
[KN85]
M. S. Krishnamoorthy and P. Narendran. On recursive path ordering. Theoretical Computer Science, 40:323–328, 1985.
[Sny91]
Wayne Snyder. A note on the complexity of simplification orderings. Technical Report TR 90–009, Boston University, Boston, MA, 1991.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]