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

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

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

ж(...) > грамм(s1,...,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,...,тп }

куда

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

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

  • Если (>) равно переходный, то так О(>).
  • Если (>) равно иррефлексивный, то так О(>).
  • Если s > т, тогда ж(...,s,...) О(>) ж(...,т,...).
  • О является непрерывный на отношения, т.е. если р0, р1, р2, р3, ... - бесконечная последовательность отношений, то О(∪∞
    я=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