A COMPREHENSIVE ALTERNATIVE PROOF OF THE EQUIVALENCE OF DERSHOWITZ-MANNA AND HUET-OPPEN ORDERINGS

Authors

Keywords:

Dershowitz-Manna, Huet-Oppen, Multiset, Partial ordering, Operations on multisets

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.

Dimensions

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

Published

12-03-2023

How to Cite

A COMPREHENSIVE ALTERNATIVE PROOF OF THE EQUIVALENCE OF DERSHOWITZ-MANNA AND HUET-OPPEN ORDERINGS. (2023). FUDMA JOURNAL OF SCIENCES, 1(1), 19-22. https://fjs.fudutsinma.edu.ng/index.php/fjs/article/view/1214

Issue

Vol. 1 No. 1 (2017): FUDMA Journal of Sciences - Vol. 1 No. 1

Section

Research Articles
Copyright & Licensing

How to Cite

A COMPREHENSIVE ALTERNATIVE PROOF OF THE EQUIVALENCE OF DERSHOWITZ-MANNA AND HUET-OPPEN ORDERINGS. (2023). FUDMA JOURNAL OF SCIENCES, 1(1), 19-22. https://fjs.fudutsinma.edu.ng/index.php/fjs/article/view/1214

Most read articles by the same author(s)