Заказ Дершовица – Манна - Dershowitz–Manna ordering

В математике Заказ Дершовица – Манна это обоснованный заказ на мультимножества названный в честь Нахум Дершовиц и Зохар Манна. Часто используется в контексте завершения программ или системы переписывания терминов.

Предположим, что ${ displaystyle (S, <_ {S})}$ это частичный заказ, и разреши ${ Displaystyle { mathcal {M}} (S)}$ - множество всех конечных мультимножеств на ${ displaystyle S}$ . Для мультимножеств ${ displaystyle M, N in { mathcal {M}} (S)}$ определим порядок Дершовица – Манна ${ displaystyle M <_ {DM} N}$ следующее:

${ displaystyle M <_ {DM} N}$ если существует два мультимножества ${ Displaystyle X, Y in { mathcal {M}} (S)}$ со следующими свойствами:

${ displaystyle X neq varnothing}$ ,
${ Displaystyle X substeq N}$ ,
${ Displaystyle M = (N-X) + Y}$ , и
${ displaystyle X}$ доминирует ${ displaystyle Y}$ , то есть для всех ${ displaystyle y in Y}$ , существует некоторое ${ displaystyle x in X}$ такой, что ${ displaystyle y <_ {S} x}$ .

Эквивалентное определение было дано Хуэтом и Оппеном следующим образом:

${ displaystyle M <_ {DM} N}$ если и только если

${ Displaystyle M neq N}$ , и
для всех ${ displaystyle y}$ в ${ displaystyle S}$ , если ${ Displaystyle М (у)> N (у)}$ тогда есть некоторые ${ displaystyle x}$ в ${ displaystyle S}$ такой, что ${ displaystyle y <_ {S} x}$ и ${ Displaystyle М (х)$ .

Заказ Дершовица – Манна - Dershowitz–Manna ordering

Рекомендации