A COMPREHENSIVE ALTERNATIVE PROOF OF THE EQUIVALENCE OF DERSHOWITZ-MANNA AND HUET-OPPEN ORDERINGS
Keywords:
Dershowitz-Manna, Huet-Oppen, Multiset, Partial ordering, Operations on multisetsAbstract
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
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
Published
2023-03-12
How to Cite
Peter, C., & Singh, D. (2023). A COMPREHENSIVE ALTERNATIVE PROOF OF THE EQUIVALENCE OF DERSHOWITZ-MANNA AND HUET-OPPEN ORDERINGS. FUDMA JOURNAL OF SCIENCES, 1(1), 19 - 22. Retrieved from https://fjs.fudutsinma.edu.ng/index.php/fjs/article/view/1214
Issue
Section
Research Articles
FUDMA Journal of Sciences
