Dershowitz–Manna ordering

In mathematics, the Dershowitz–Manna ordering is a well-founded ordering on multisets named after Nachum Dershowitz and Zohar Manna. It is often used in context of termination of programs or term rewriting systems.

Suppose that ${\displaystyle (S,<_{S})}$ is a partial order, and let ${\displaystyle {\mathcal {M}}(S)}$ be the set of all finite multisets on ${\displaystyle S}$. For multisets ${\displaystyle M,N\in {\mathcal {M}}(S)}$ we define the Dershowitz–Manna ordering ${\displaystyle M<_{DM}N}$ as follows:

...
Wikipedia