Порядок перезаписи - Rewrite order
В теоретическая информатика, в частности в автоматическое рассуждение о формальных уравнениях, порядок сокращения используются для предотвращения бесконечные петли. Переписать заказы, и, в свою очередь, переписать отношения, являются обобщениями этой концепции, которые оказались полезными в теоретических исследованиях.
Мотивация
Интуитивно понятно, что порядок приведения р связывает два официальных выражения s и т если т правильно "проще", чем s в каком-то смысле.
Например, упрощение терминов может быть частью компьютерная алгебра программа, и может использовать набор правил { Икс+0 → Икс , 0+Икс → Икс , Икс*0 → 0, 0*Икс → 0, Икс*1 → Икс , 1*Икс → Икс }. Чтобы доказать невозможность бесконечных циклов при упрощении термина, порядок редукции определяется формулой "sRt если выражение т правильно короче выражения s"можно использовать; применение любого правила из набора всегда правильно сокращает срок.
Напротив, для установления прекращения «раздачи» с помощью правила Икс*(у+z) → Икс*у+Икс*z, потребуется более сложный порядок сокращения, поскольку это правило может увеличить размер термина из-за дублирования Икс. Теория заказов на перезапись направлена на то, чтобы помочь обеспечить соответствующий порядок в таких случаях.
Формальные определения
Формально бинарное отношение (→) на множестве термины называется переписать отношение если это закрыто под контекстное встраивание и под реализация; формально: если л→р подразумевает ты[лσ ]п→ты[рσ]п на все сроки л, р, ты, каждый путь п из ты, и каждый замена σ. Если (→) также иррефлексивный и переходный, то он называется переписать заказ,[1] или же переписать Предварительный заказ. Если последний (→) к тому же обоснованный, это называется заказ на сокращение,[2] или предварительный заказ на сокращение.Данная бинарная связь р, это переписать закрытие наименьшее отношение перезаписи, содержащее р.[3] Транзитивное и рефлексивное отношение перезаписи, которое содержит субтерм заказ называется упрощение заказа.[4]
| переписать связь | переписать порядок | снижение порядок | упрощение порядок | |
|---|---|---|---|---|
| закрыт под контекст x R y подразумевает ты[Икс]п р ты[у]п | да | да | да | да |
| закрыт под реализация x R y подразумевает Иксσ р уσ | да | да | да | да |
| содержит субтерм связь у субтерм из Икс подразумевает x R y | да | |||
| рефлексивный всегда x R x | (Нет) | (Нет) | да | |
| иррефлексивный никогда x R x | да | да | (Нет) | |
| переходный x R y и y R z подразумевает х R z | да | да | да | |
| обоснованный нет бесконечной цепочки Икс1 р Икс2 р Икс3 р ...[заметка 2] | да | (Да) |
Характеристики
- В разговаривать, то симметричное закрытие, то рефлексивное закрытие, а переходное закрытие отношения перезаписи снова является отношением перезаписи, как и объединение и пересечение двух отношений перезаписи.[1]
- Обратным порядком перезаписи снова является порядок перезаписи.
- Хотя существуют заказы на перезапись, общее количество которых составляет основные условия (для краткости "общий итог"), порядок перезаписи не может быть полным для набора все условия.[заметка 3][5]
- А система переписывания терминов {л1::=р1,...,лп::=рп, ...} является прекращение если его правила являются подмножеством редукционного порядка.[примечание 4][2]
- И наоборот, для каждой системы перезаписи завершающего термина переходное закрытие of (:: =) - порядок редукции,[2] который, однако, не обязательно должен быть расширен до общего. Например, система переписывания основных терминов { ж(а)::=ж(б), грамм(б)::=грамм(а)} завершается, но может быть показано таким образом, используя порядок сокращения, только если константы а и б несравненные.[примечание 5][6]
- Полноценный и обоснованный заказ перезаписи[примечание 6] обязательно содержит правильный подтерм отношение на земельных условиях.[примечание 7]
- И наоборот, порядок перезаписи, содержащий отношение подтермина[примечание 8] обязательно является обоснованным, когда набор функциональных символов конечен.[5][примечание 9]
- Система переписывания конечных терминов {л1::=р1,...,лп::=рп, ...} завершается, если его правила являются подмножеством строгой части упорядочивания упрощения.[4][8]
Примечания
- ^ Записи в скобках указывают на предполагаемые свойства, которые не являются частью определения. Например, иррефлексивное отношение не может быть рефлексивным (на непустом множестве областей).
- ^ кроме всех Икся равны для всех я за пределами некоторых п, для рефлексивного отношения
- ^ С Икс<у подразумевает у<Икс, поскольку последний является примером первого, для переменных Икс, у.
- ^ т.е. если ля > ря для всех я, где (>) - порядок редукции; система не обязательно должна иметь конечное количество правил
- ^ Так как, например, а>б подразумевается грамм(а)>грамм(б), что означает, что второе правило перезаписи не уменьшалось.
- ^ то есть заказ на общее сокращение
- ^ Еще, т|п > т на какой-то срок т и положение п, подразумевая бесконечную убывающую цепочку т > т[т]п > т[т[т]п]п > ...[6][7]
- ^ т.е. упорядочение упрощения
- ^ Доказательство этого свойства основано на Лемма хигмана, или, в более общем смысле, Теорема Крускала о дереве.
Рекомендации
Нахум Дершовиц; Жан-Пьер Жуанно (1990). «Системы перезаписи». В Ян ван Леувен (ред.). Формальные модели и семантика. Справочник по теоретической информатике. B. Эльзевир. С. 243–320. Дои:10.1016 / B978-0-444-88074-1.50011-1. ISBN 9780444880741.
- ^ а б Дершовиц, Жуанно (1990), раздел 2.1, с.251
- ^ а б c Дершовиц, Жуанно (1990), раздел 5.1, стр.270
- ^ Дершовиц, Жуанно (1990), раздел 2.2, стр.252
- ^ а б Дершовиц, Жуанно (1990), раздел 5.2, стр.274
- ^ а б Дершовиц, Жуанно (1990), раздел 5.1, стр.272
- ^ а б Дершовиц, Жуанно (1990), раздел 5.1, стр.271.
- ^ Дэвид А. Плейстед (1978). Рекурсивно определенный порядок для доказательства прекращения системы перезаписи терминов (Технический отчет). Univ. Иллинойса, Департамент Comp. Sc. п. 52. Р-78-943.
- ^ Н. Дершовиц (1982). "Заказы на системы перезаписи терминов" (PDF). Теорет. Comput. Наука. 17 (3): 279–301. Дои:10.1016/0304-3975(82)90026-3. Здесь: с.287; понятия названы несколько иначе.