A COMPREHENSIVE ALTERNATIVE PROOF OF THE EQUIVALENCE OF DERSHOWITZ-MANNA AND HUET-OPPEN ORDERINGS
Abstract
The research note outlines an alternative proof of the equivalence of the Dershowitz-Manna
ordering and the Huet-Oppen ordering which was originally presented by Jouannaud and Lescanne.
First, some algebraic foundations of multiset orderings are laid which directly or indirectly leads to
the result obtained by means of the Huet-Open ordering.
References
Dershowitz, N. and Manna, Z, (1979), Ordering for term rewriting systems, Proc. 20th Symp. on Foundations of Computer Science, 123-131.
Dershowitz, N. and Manna, Z, (1979), Proving Termination with Multiset Ordering, Comm. ACM, Vol. 22, 465-476.
Dornhoff, L. L. and Hohn, F. E. Applied Modern Algebra, Macmillan Publishing Co, 1978.
Huet, G. and Oppen, D. C. (1980). Equations and rewrite rules. Formal language theory: perspectives and open problems, 349-405.
Jouannaud, J. and Lescanne (1982), P., On multiset ordering, Information processing letters, Volume 15, Number 2, 57-63.
Singh, D., Ibrahim, A., Yohanna, T., and Singh, J. (2007). An overview of the applications of multisets. Novi Sad Journal of Mathematics, 37(3), 73- 92.
Tella, Y., Singh, D. and Singh, J. N. (2014). A Comparative Study of Multiset Orderings. International Journal of Mathematics and Statistics Invention (IJMSI), 2(5), 59-70
Copyright (c) 2023 FUDMA JOURNAL OF SCIENCES
This work is licensed under a Creative Commons Attribution 4.0 International License.
FUDMA Journal of Sciences
