Упорядочивание путей (переписывание терминов) - Path ordering (term rewriting)

"Лексикографический порядок путей" перенаправляется сюда. Порядок словаря см. Лексикографический порядок.

В теоретическая информатика, в частности в переписывание терминов, а порядок следования это обоснованный строгий общий порядок (>) на множестве всех термины такой, что

ж(...) > грамм(s₁,...,s_п) если ж ^.> грамм и ж(...) > s_я за я=1,...,п,

куда (^.>) - это пользовательский общий порядок приоритета на множестве всех функциональные символы.

Интуитивно термин ж(...) больше любого термина грамм(...) построены на терминах s_я меньше чем ж(...) с использованием корневого символа более низкого приоритета грамм. В частности, структурная индукция, термин ж(...) больше, чем любой термин, содержащий только символы, меньшие, чем ж.

Порядок пути часто используется как заказ на сокращение в переписывании терминов, в частности в Алгоритм завершения Кнута – Бендикса. Как пример, система переписывания терминов для "умножение "математические выражения могут содержать правило Икс*(у+z) → (Икс*у) + (Икс*z). Чтобы доказать прекращение, а заказ на сокращение (>) необходимо найти, относительно которого термин Икс*(у+z) больше члена (Икс*у)+(Икс*z). Это нетривиально, поскольку первый член содержит меньше функциональных символов и меньше переменных, чем второй. Однако установка приоритета (*) ^.> (+), можно использовать порядок путей, поскольку оба Икс*(у+z) > Икс*у и Икс*(у+z) > Икс*z легко достичь.

Учитывая два условия s и т, с корневым символом ж и граммсоответственно, чтобы определить их отношение, сначала сравниваются их корневые символы.

• Если ж <^. грамм, тогда s может доминировать т только если один из s 's subterms делает.
• Если ж ^.> грамм, тогда s доминирует т если s доминирует над каждым из т 's подтермы.
• Если ж = грамм, то немедленное подтермы из s и т нужно сравнивать рекурсивно. В зависимости от конкретного метода существуют разные варианты упорядочения путей.^[1][2]

Последние варианты включают:

• то порядок мультимножества путей (МПО), первоначально назывался рекурсивный порядок путей (рпо)^[3]
• то лексикографический порядок путей (LPO)^[4]
• комбинация mpo и lpo, называемая рекурсивный порядок путей Дершовиц, Жуанно (1990)^[5][6][7]

Дершовиц, Окада (1988) перечисляют больше вариантов и соотносят их с Аккерманн система порядковые.

Формальные определения

В упорядочение путей мультимножества (>) можно определить следующим образом:^[8]

s = ж(s1,...,sм) > т = грамм(т1,...,тп)									если
ж	^.>	грамм	и	s	>	тj	для каждого	j∈{1,...,п},	или же
				sя	≥	т	для некоторых	я∈{1,...,м},	или же
ж	=	грамм	и	{ s1,...,sм } >> { т1,...,тп }

куда

• (≥) обозначает рефлексивное закрытие МПо (>),
• { s₁,...,s_м } обозначает мультимножество из sПодтермы, похожие на т, и
• (>>) обозначает расширение мультимножества (>), определяемое { s₁,...,s_м } >> { т₁,...,т_п } если { т₁,...,т_п } можно получить из { s₁,...,s_м }
  • удалив хотя бы один элемент, или
  • путем замены элемента мультимножеством строго меньших (по сравнению с mpo) элементов.^[9]

В более общем плане порядок функциональный это функция О отображение одного порядка в другой и удовлетворение следующих свойств:^[10]

• Если (>) равно переходный, то так О(>).
• Если (>) равно иррефлексивный, то так О(>).
• Если s > т, тогда ж(...,s,...) О(>) ж(...,т,...).
• О является непрерывный на отношения, т.е. если р₀, р₁, р₂, р₃, ... - бесконечная последовательность отношений, то О(∪^∞
  _я=0 р_я) = ∪^∞
  _я=0 О(р_я).

Расширение мультимножества, отображение (>) выше на (>>) выше, является одним из примеров функционала порядка: (>>) =О(>). Другой функционал порядка - это лексикографический расширение, ведущее к лексикографический порядок путей.

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

1. Нахум Дершовиц, Жан-Пьер Жуанно (1990). Ян ван Леувен (ред.). Системы перезаписи. Справочник по теоретической информатике. B. Эльзевир. С. 243–320. Здесь: раздел 5.3, с.275
2. Жерар Хуэ (май 1986). Формальные структуры для вычислений и дедукции. Международная летняя школа по логике программирования и исчислениям дискретного проектирования. Архивировано из оригинал на 2014-07-14. Здесь: глава 4, с.55-64
3. Н. Дершовиц (1982). "Заказы на системы перезаписи терминов" (PDF). Теорет. Comput. Наука. 17 (3): 279–301.
4. С. Камин, Ж.-Ж. Леви (1980). Два обобщения рекурсивного упорядочивания путей (Технический отчет). Univ. Иллинойс, Урбана / Иллинойс.
5. Камин, Леви (1980)
6. Н. Дершовиц, М. Окада (1988). "Теоретико-доказательные методы теории перезаписи терминов". Proc. 3-й симпозиум IEEE. по логике в компьютерных науках (PDF). С. 104–111.
7. Мицухиро Окада, Адам Стил (1988). "Структуры упорядочения и алгоритм завершения Кнута – Бендикса". Proc. конференции Allerton Conf. по связи, управлению и вычислениям.
8. Huet (1986), раздел 4.3, определение 1, стр.57
9. Huet (1986), раздел 4.1.3, стр.56
10. Huet (1986), раздел 4.3, стр. 58