Переписывание

Переписывание — широкий спектр техник, методов и теоретических результатов, связанных с процедурами последовательной замены частей формул или термов формального языка по заданной схеме — системе переписывающих правил. В наиболее общей форме речь идёт о совокупности некоторого набора объектов и правил — отношений между этими объектами, которые указывают как преобразовать этот набор.

Переписывание может быть недетерминированным. Например, система переписывающих правил может включать в себя правило, которое может быть применено к одному и тому же терму несколькими разными способами, но не содержать, при этом, указания на то, какой конкретно способ нужно применить в том или ином случае. Если система переписывания, всё же, оформлена в качестве однозначно понимаемого алгоритма, она может рассматриваться как компьютерная программа. На техниках переписывания основан ряд систем интерактивного доказательства теорем и декларативных языков программирования.

Основные понятия и примеры

Основные свойства систем переписывания можно сформулировать, не прибегая к конкретной реализации их в виде операций над термами. Для этого часто используется понятие Абстрактной Системы Редукций или ARS (от англ. Abstract Reduction Systems). ARS состоит из некоторого множества A и набора бинарных отношений $(\to _{\alpha })_{\alpha \in I}$ на нём, которые называются редукциями. Говорят, что a редуцируется или переписывается в b в один шаг относительно данной ARS, если пара (a,b) принадлежит некоторому $\to _{\alpha }$. Важнейшими свойствами редукционных систем являются:

• Конфлюентность  — если a может за некоторое число шагов редуцироваться как в b, так и в c, то существует элемент d, в который могут редуцироваться оба b и c.
• Остановочность — любая цепочка одношаговых редукций всегда конечна, то есть, достигается элемент, который не может больше быть редуцирован.
• Локальная (или слабая) конфлюентность — то же, что и конфлюентность, но при условии, что a переписывается в b и c ровно за один шаг.
• Слабая остановочность — для каждого элемента существует обрывающаяся цепочка его последовательных редукций.
• Каноничность или свойство Чёрча-Россера — конфлюентность плюс остановочность.

Очевидно, конфлюентность влечёт слабую конфлюенцию, а остановочность, соответственно, слабую остановочность. Однако, конфлюентность и остановочность между собой не связаны. Например, система, состоящая из одного правила a•b → b•a конфлюентна, но не остановочна. Система, состоящая из двух правил a → b и a → c остановочна, но не конфлюентна, а все три правила вместе образуют систему, которая и не остановочна и не конфлюентна.

Остановочность редукционной системы позволяет сопоставить каждому элементу его нормальную форму — элемент, в который его можно редуцировать, но который сам уже больше не редуцируется. Если вдобавок соблюдается конфлюентность, то такая нормальная форма всегда будет единственной, или канонической. В связи с этим, особо ценным является свойство Чёрча-Россера, так как позволяет быстро и эффективно решать проблему равенства двух элементов a и b относительно системы равенств, соответствующей множеству редукций без учёта направления. Для этого достаточно вычислить нормальные формы обоих элементов. Поскольку в этом случае нормальная форма будет также канонической, элементы будут равны, тогда и только тогда, когда результаты совпадут.

Классическая теория переписывания

Несмотря на то, что изначально понятие переписывания было введено для лямбда-исчисления, основной массив результатов и приложений в настоящее время касается переписывания первого порядка. Переписывающие системы такого рода называют Системами Переписывания Термов или TRS (от англ. Term rewriting systems).

Переписывание высших порядков

Системы переписывания высших порядков являются обобщением систем переписывания термов первого порядка на лямбда-термы, позволяя функции высших порядков и связанные переменные. Различные результаты о системах переписывания термов первого порядка также могут быть переформулированы для высших порядков.

См. также

• Алгоритм Кнута — Бендикса
• Лямбда-исчисление
• Переписывающая система
• Представление группы
• L-система
• Рефал

Литература

• Term Rewriting Systems, Terese, Cambridge Tracts in Theoretical Computer Science, 2003
• Term Rewriting and All That, Franz Baader and Tobias Nipkow, Cambridge University Press, 1998

Ссылки

• nLab authors rewriting  (неопр.). nLab (July 2023).