Заказ охвата - Encompassment ordering

Треугольная диаграмма двух членов s ≤ т связаны предзаказом охвата.

В теоретическая информатика, в частности в автоматическое доказательство теорем и переписывание терминов, то сдерживание,^[1] или же охват, Предварительный заказ (≤) на множестве термины, определяется^[2]

s ≤ т если субтерм из т это подстановочный экземпляр из s.

Он используется, например, в Алгоритм завершения Кнута – Бендикса.

Характеристики

• Охват - это Предварительный заказ, т.е. рефлексивный и переходный, но нет антисимметричный,^{[примечание 1]} ни общий^{[заметка 2]}
• В соответствующее отношение эквивалентности, определяется s ~ т если s ≤ т ≤ s, является равенство по модулю переименования.
• s ≤ т в любое время s это субтерм из т.
• s ≤ т в любое время т это подстановочный экземпляр из s.
• Союз любого обоснованного переписать заказ р^{[заметка 3]} с (<) есть обоснованный, где (<) обозначает иррефлексивное ядро из (≤).^[3] В частности, хорошо обосновано само (<).

Примечания

1. поскольку оба ж(Икс) ≤ ж(у) и ж(у) ≤ ж(Икс) за переменные символы Икс, у и символ функции ж
2. так как ни а ≤ б ни б ≤ а для различных постоянные символы а, б
3. т.е. иррефлексивное, транзитивное и хорошо обоснованное бинарное отношение р такой, что sRt подразумевает ты[sσ ]_п р ты[тσ]_п на все сроки s, т, ты, каждый путь п из ты, и каждый замена  σ

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

1. Жерар Хуэ (1981). «Полное доказательство правильности алгоритма завершения Кнута – Бендикса». J. Comput. Syst. Наука. 23 (1): 11–21. Дои:10.1016/0022-0000(81)90002-7.
2. Н. Дершовиц, Ж.-П. Jouannaud (1990). Ян ван Леувен (ред.). Системы перезаписи. Справочник по теоретической информатике. B. Эльзевир. С. 243–320. Здесь: раздел 2.1, с. 250
3. Дершовиц, Жуанно (1990), раздел 5.4, стр. 278; несколько небрежно, р там должно быть "завершающее отношение перезаписи".