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

Замена подтермина в формуле другим термином

В математике , информатике и логике рерайтинг охватывает широкий спектр методов замены подчленов формулы другими терминами . Такие методы могут быть достигнуты с помощью систем перезаписи (также известных как системы перезаписи , механизмы перезаписи , ^{[1] [2]} или системы сокращения ). В своей самой базовой форме они состоят из набора объектов и отношений, позволяющих преобразовать эти объекты.

Переписывание может быть недетерминированным . Одно правило переписывания термина может быть применено к этому термину по-разному, или может быть применимо более одного правила. В этом случае системы переписывания предоставляют не алгоритм замены одного термина на другой, а набор возможных применений правил. Однако в сочетании с соответствующим алгоритмом системы перезаписи можно рассматривать как компьютерные программы , а некоторые средства доказательства теорем ^[3] и языки декларативного программирования основаны на переписывании терминов. ^{[4] [5]}

Примеры случаев

Логика

В логике процедура получения конъюнктивной нормальной формы (КНФ) формулы может быть реализована как система переписывания. ^[6] Правила примера такой системы будут следующими:

${\displaystyle \neg \neg A\to A}$( исключение двойного отрицания )

${\displaystyle \neg (A\land B)\to \neg A\lor \neg B}$( законы де Моргана )

${\displaystyle \neg (A\lor B)\to \neg A\land \neg B}$

${\displaystyle (A\land B)\lor C\to (A\lor C)\land (B\lor C)}$( дистрибутивность )

${\displaystyle A\lor (B\land C)\to (A\lor B)\land (A\lor C),}$^{[примечание 1]}

где символ ( ) указывает, что выражение, соответствующее левой части правила, может быть переписано в выражение, образованное правой частью, а каждый из символов обозначает подвыражение. В такой системе каждое правило выбирается таким образом, чтобы левая часть была эквивалентна правой стороне, и, следовательно, когда левая часть соответствует подвыражению, выполнение перезаписи этого подвыражения слева направо сохраняет логическую согласованность и значение всего выражения. . ${\displaystyle \to }$

Арифметика

Системы переписывания терминов можно использовать для вычисления арифметических операций над натуральными числами . Для этого каждое такое число необходимо закодировать как терм . Самая простая кодировка — та, которая используется в аксиомах Пеано , основанная на константе 0 (нуле) и функции-преемнике S. Например, числа 0, 1, 2 и 3 представлены терминами 0, S(0), S(S(0)) и S(S(S(0))) соответственно. Затем можно использовать следующую систему переписывания терминов для вычисления суммы и произведения заданных натуральных чисел. ^[7]

${\displaystyle {\begin{aligned}A+0&\to A&{\textrm {(1)}},\\A+S(B)&\to S(A+B)&{\textrm {(2)}},\\A\cdot 0&\to 0&{\textrm {(3)}},\\A\cdot S(B)&\to A+(A\cdot B)&{\textrm {(4)}}.\end{aligned}}}$

Например, вычисление 2+2, дающее в результате 4, можно продублировать, переписав термин следующим образом:

${\displaystyle S(S(0))+S(S(0))}$ ${\displaystyle \;\;{\stackrel {(2)}{\to }}\;\;}$ ${\displaystyle S(\;S(S(0))+S(0)\;)}$ ${\displaystyle \;\;{\stackrel {(2)}{\to }}\;\;}$ ${\displaystyle S(S(\;S(S(0))+0\;))}$ ${\displaystyle \;\;{\stackrel {(1)}{\to }}\;\;}$ ${\displaystyle S(S(S(S(0)))),}$

где номера правил указаны над стрелкой перезаписи .

Другой пример: вычисление 2⋅2 выглядит так:

${\displaystyle S(S(0))\cdot S(S(0))}$ ${\displaystyle \;\;{\stackrel {(4)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))\cdot S(0)}$ ${\displaystyle \;\;{\stackrel {(4)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))+S(S(0))\cdot 0}$ ${\displaystyle \;\;{\stackrel {(3)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))+0}$ ${\displaystyle \;\;{\stackrel {(1)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))}$ ${\displaystyle \;\;{\stackrel {\textrm {s.a.}}{\to }}\;\;}$ ${\displaystyle S(S(S(S(0)))),}$

где последний шаг включает в себя вычисление предыдущего примера.

Лингвистика

В лингвистике правила структуры фраз , также называемые правилами перезаписи , используются в некоторых системах порождающей грамматики ^[8] как средство создания грамматически правильных предложений языка. Такое правило обычно принимает форму , где A — синтаксическая метка категории , такая как именное словосочетание или предложение , а X — последовательность таких меток или морфем , выражающая тот факт, что A можно заменить на X при создании составной структуры предложение. Например, правило означает, что предложение может состоять из именной группы (NP), за которой следует глагольная группа (VP); дальнейшие правила будут определять, из каких субкомпонентов могут состоять именной и глагольный обороты, и так далее. ${\displaystyle {\rm {A\rightarrow X}}}$ ${\displaystyle {\rm {S\rightarrow NP\ VP}}}$

Абстрактные системы переписывания

Из приведенных выше примеров ясно, что мы можем думать о переписывании систем абстрактным образом. Нам нужно указать набор объектов и правила, которые можно применить для их преобразования. Наиболее общая (одномерная) постановка этого понятия называется абстрактной системой редукции ^[9] или абстрактной системой переписывания (сокращенно ARS ). ^[10] ARS — это просто набор A объектов вместе с бинарным отношением → на A , называемым отношением редукции , отношением перезаписи ^[11] или просто редукцией . ^[9]

Многие понятия и обозначения могут быть определены в общих условиях АРС. является рефлексивным транзитивным замыканием . является симметричным замыканием . является рефлексивным транзитивным симметричным замыканием . Словесная проблема для ARS заключается в том, чтобы определить по заданным x и y , является ли . Объект x в A называется приводимым, если существует другой y в A такой, что ; в противном случае она называется неприводимой или нормальной формой . Объект y называется «нормальной формой x », если , и y неприводим. Если нормальная форма x уникальна, то это обычно обозначается . Если каждый объект имеет хотя бы одну нормальную форму, ARS называется нормализацией . или x и y называются соединяемыми , если существует некоторый z со свойством, что . Говорят, что ARS обладает свойством Чёрча-Россера, если это подразумевает . ARS является конфлюэнтным, если для всех w , x и y в A следует . ARS является локально конфлюэнтным тогда и только тогда , когда для всех w , x и y в A следует . ARS называется завершающей или нетеровой , если не существует бесконечной цепи . Сливающаяся и завершающаяся ARS называется конвергентной или канонической . ${\displaystyle {\overset {*}{\rightarrow }}}$ ${\displaystyle \rightarrow }$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \rightarrow }$ ${\displaystyle {\overset {*}{\leftrightarrow }}}$ ${\displaystyle \rightarrow }$ ${\displaystyle x{\overset {*}{\leftrightarrow }}y}$ ${\displaystyle x\rightarrow y}$ ${\displaystyle x{\stackrel {*}{\rightarrow }}y}$ ${\displaystyle x{\downarrow }}$ ${\displaystyle x\downarrow y}$ ${\displaystyle x{\overset {*}{\rightarrow }}z{\overset {*}{\leftarrow }}y}$ ${\displaystyle x{\overset {*}{\leftrightarrow }}y}$ ${\displaystyle x\downarrow y}$ ${\displaystyle x{\overset {*}{\leftarrow }}w{\overset {*}{\rightarrow }}y}$ ${\displaystyle x\downarrow y}$ ${\displaystyle x\leftarrow w\rightarrow y}$ ${\displaystyle x{\mathbin {\downarrow }}y}$ ${\displaystyle x_{0}\rightarrow x_{1}\rightarrow x_{2}\rightarrow \cdots }$

Важные теоремы для абстрактных систем переписывания заключаются в том, что ARS конфлюэнна тогда и только тогда, когда она обладает свойством Черча-Россера, леммой Ньюмана (завершающая ARS конфлюэнна тогда и только тогда, когда она локально конфлюэнна), и что проблема слов для ARS неразрешима в общий.

Системы перезаписи строк

Система переписывания строк (SRS), также известная как система полу-Туэ , использует свободную моноидную структуру строк ( слов) в алфавите для расширения отношения переписывания на все строки в алфавите, которые содержат левые и, соответственно, правые строки. -стороны некоторых правил как подстроки . Формально система полу-Туэ — это кортеж , где — (обычно конечный) алфавит и бинарное отношение между некоторыми (фиксированными) строками в алфавите, называемое набором правил перезаписи . Отношение одношаговой перезаписи, индуцированное on, определяется как: если есть какие-либо строки, то если существуют такие , что , и . Поскольку является отношением к , пара соответствует определению абстрактной системы переписывания. Поскольку пустая строка находится в , она является подмножеством . Если отношение симметрично , то система называется системой Туэ . ${\displaystyle R}$ ${\displaystyle (\Sigma ,R)}$ ${\displaystyle \Sigma }$ ${\displaystyle R}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle R}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle s,t\in \Sigma ^{*}}$ ${\displaystyle s{\underset {R}{\rightarrow }}t}$ ${\displaystyle x,y,u,v\in \Sigma ^{*}}$ ${\displaystyle s=xuy}$ ${\displaystyle t=xvy}$ ${\displaystyle uRv}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle (\Sigma ^{*},{\underset {R}{\rightarrow }})}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle R}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle R}$

В SRS отношение приведения совместимо с операцией моноида, то есть это подразумевает для всех строк . Точно так же рефлексивное транзитивное симметричное замыкание , обозначаемое , является конгруэнцией , что означает, что это отношение эквивалентности (по определению), а также совместимо с конкатенацией строк. Отношение называется сравнением Туэ , порожденным . В системе Туэ, т.е. если она симметрична, отношение перезаписи совпадает с конгруэнцией Туэ . ${\displaystyle {\overset {*}{\underset {R}{\rightarrow }}}}$ ${\displaystyle x{\overset {*}{\underset {R}{\rightarrow }}}y}$ ${\displaystyle uxv{\overset {*}{\underset {R}{\rightarrow }}}uyv}$ ${\displaystyle x,y,u,v\in \Sigma ^{*}}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle {\overset {*}{\underset {R}{\rightarrow }}}}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$

Понятие о системе полуТуэ по существу совпадает с представлением о моноиде . Поскольку это сравнение, мы можем определить фактор-моноид свободного моноида с помощью сравнения Туэ. Если моноид изоморфен , то полусистема Туэ называется моноидным представлением . ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle {\mathcal {M}}_{R}=\Sigma ^{*}/{\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}_{R}}$ ${\displaystyle (\Sigma ,R)}$ ${\displaystyle {\mathcal {M}}}$

Мы сразу получаем очень полезные связи с другими областями алгебры. Например, алфавит с правилами , где пустая строка , представляет собой представление свободной группы на одном генераторе. Если вместо этого правила справедливы , то мы получаем представление бициклического моноида . Таким образом, системы полуТуэ представляют собой естественную основу для решения проблемы слов для моноидов и групп. Фактически, каждый моноид имеет представление формы , т.е. он всегда может быть представлен системой полу-Туэ, возможно, над бесконечным алфавитом. ${\displaystyle \{a,b\}}$ ${\displaystyle \{ab\rightarrow \varepsilon ,ba\rightarrow \varepsilon \}}$ ${\displaystyle \varepsilon }$ ${\displaystyle \{ab\rightarrow \varepsilon \}}$ ${\displaystyle (\Sigma ,R)}$

Проблема слов для системы полуТуэ, вообще говоря, неразрешима; этот результат иногда называют теоремой Поста-Маркова . ^[12]

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

Рис.1: Схематическая треугольная диаграмма применения правила перезаписи в позиции термина с соответствующей заменой. ${\displaystyle l\longrightarrow r}$ ${\displaystyle p}$ ${\displaystyle \sigma }$

Рис.2: Сопоставление терминов по правилу lhs в термине ${\displaystyle x*(y*z)}$ ${\displaystyle {\frac {a*((a+1)*(a+2))}{1*(2*3)}}}$

Система переписывания терминов ( TRS ) — это система переписывания, объектами которой являются термины , которые представляют собой выражения со вложенными подвыражениями. Например, система, показанная выше в разделе «Логика», представляет собой систему переписывания терминов. Термины в этой системе состоят из бинарных операторов и унарного оператора . В правилах также присутствуют переменные, которые представляют любой возможный термин (хотя одна переменная всегда представляет один и тот же термин в одном правиле). ${\displaystyle (\vee )}$ ${\displaystyle (\wedge )}$ ${\displaystyle (\neg )}$

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

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

Правило перезаписи — это пара терминов , обычно записываемых как , обозначающих, что левая часть l может быть заменена правой частью r . Система переписывания терминов представляет собой набор R таких правил. Правило может быть применено к терму s , если левый терм l соответствует некоторому подтерму s , то есть если существует некоторая замена, такая, что подтерм с корнем в некоторой позиции p является результатом применения замены к терму l . Подтерм, соответствующий левой части правила, называется редексом или сокращаемым выражением . ^[13] Результатом применения этого правила является результат замены подтерма в позиции p в s термином с примененной заменой , см. рисунок 1. В этом случае говорят, что он переписан за один шаг , или переписан непосредственно , в системой , формально обозначенной как , , или как у некоторых авторов. ${\displaystyle l\rightarrow r}$ ${\displaystyle l\rightarrow r}$ ${\displaystyle \sigma }$ ${\displaystyle s}$ ${\displaystyle \sigma }$ ${\displaystyle r}$ ${\displaystyle \sigma }$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle R}$ ${\displaystyle s\rightarrow _{R}t}$ ${\displaystyle s{\underset {R}{\rightarrow }}t}$ ${\displaystyle s{\overset {R}{\rightarrow }}t}$

Если терм можно переписать в несколько шагов в терм , то есть если , говорят, что терм переписан в , формально обозначаемый как . Другими словами, отношение является транзитивным замыканием отношения ; часто также обозначение используется для обозначения рефлексивно-транзитивного замыкания , то есть if или . ^[14] Переписывание терминов, заданное набором правил, можно рассматривать как абстрактную систему переписывания, как она определена выше, с терминами в качестве ее объектов и отношения перезаписи. ${\displaystyle t_{1}}$ ${\displaystyle t_{n}}$ ${\displaystyle t_{1}{\underset {R}{\rightarrow }}t_{2}{\underset {R}{\rightarrow }}\cdots {\underset {R}{\rightarrow }}t_{n}}$ ${\displaystyle t_{1}}$ ${\displaystyle t_{n}}$ ${\displaystyle t_{1}{\overset {+}{\underset {R}{\rightarrow }}}t_{n}}$ ${\displaystyle {\overset {+}{\underset {R}{\rightarrow }}}}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle {\overset {*}{\underset {R}{\rightarrow }}}}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle s{\overset {*}{\underset {R}{\rightarrow }}}t}$ ${\displaystyle s=t}$ ${\displaystyle s{\overset {+}{\underset {R}{\rightarrow }}}t}$ ${\displaystyle R}$ ${\displaystyle {\underset {R}{\rightarrow }}}$

Например, это правило перезаписи, обычно используемое для установления нормальной формы относительно ассоциативности . Это правило можно применить к числителю термина с соответствующей заменой , см. рисунок 2. ^{[примечание 2]} Применение этой замены к правой части правила дает термин , а замена числителя этим термином дает , что является результат срока применения правила перезаписи. В целом, применение правила перезаписи привело к тому, что в элементарной алгебре называется «применением закона ассоциативности для к ». В качестве альтернативы правило можно было применить к знаменателю исходного члена, получив . ${\displaystyle x*(y*z)\rightarrow (x*y)*z}$ ${\displaystyle *}$ ${\displaystyle {\frac {a*((a+1)*(a+2))}{1*(2*3)}}}$ ${\displaystyle \{x\mapsto a,\;y\mapsto a+1,\;z\mapsto a+2\}}$ ${\displaystyle (a*(a+1))*(a+2)}$ ${\displaystyle {\frac {(a*(a+1))*(a+2)}{1*(2*3)}}}$ ${\displaystyle *}$ ${\displaystyle {\frac {a*((a+1)*(a+2))}{1*(2*3)}}}$ ${\displaystyle {\frac {a*((a+1)*(a+2))}{(1*2)*3}}}$

Прекращение действия

Проблемы завершения систем перезаписи в целом рассматриваются в разделе Абстрактная система перезаписи#Завершение и конвергенция . В частности, для систем переписывания терминов необходимо учитывать следующие дополнительные тонкости.

Прекращение даже системы, состоящей из одного правила с линейной левой частью, неразрешимо. ^{[15] [16]} Завершение также неразрешимо для систем, использующих только унарные функциональные символы; однако это разрешимо для конечных основных систем. ^[17]

Следующая система перезаписи терминов является нормализующей, ^{[примечание 3]} , но не завершающей, ^{[примечание 4]} и не сливающейся: ^[18]

$${\displaystyle {\begin{aligned}f(x,x)&\rightarrow g(x),\\f(x,g(x))&\rightarrow b,\\h(c,x)&\rightarrow f(h(x,c),h(x,x)).\\\end{aligned}}}$$

Следующие два примера прекращения систем перезаписи терминов принадлежат Тояме: ^[19]

${\displaystyle f(0,1,x)\rightarrow f(x,x,x)}$

и

${\displaystyle g(x,y)\rightarrow x,}$

${\displaystyle g(x,y)\rightarrow y.}$

Их объединение представляет собой незавершающуюся систему, поскольку

$${\displaystyle {\begin{aligned}&f(g(0,1),g(0,1),g(0,1))\\\rightarrow &f(0,g(0,1),g(0,1))\\\rightarrow &f(0,1,g(0,1))\\\rightarrow &f(g(0,1),g(0,1),g(0,1))\\\rightarrow &\cdots \end{aligned}}}$$

Дершовица ^[20],перекрытий ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$

См. Порядок перезаписи и Порядок путей (переписывание терминов) для отношений упорядочивания, используемых в доказательствах завершения для систем переписывания терминов.

Системы перезаписи высшего порядка

Системы переписывания более высокого порядка — это обобщение систем переписывания терминов первого порядка на лямбда-термины , позволяющие использовать функции более высокого порядка и связанные переменные. ^[21] Различные результаты о TRS первого порядка могут быть переформулированы и для HRS. ^[22]

Системы перезаписи графов

Системы перезаписи графов — это еще одно обобщение систем перезаписи терминов, работающее с графами вместо ( основных ) термов / их соответствующего древовидного представления.

Системы перезаписи трассировки

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

Философия

Системы переписывания можно рассматривать как программы, которые выводят конечные эффекты из списка причинно-следственных связей. Таким образом, системы перезаписи можно рассматривать как автоматизированные средства доказательства причинности . ^{[ нужна цитата ]}

Смотрите также

• Критическая пара (логика)
• Компилятор
• Алгоритм завершения Кнута – Бендикса
• L-системы определяют перезапись, выполняемую параллельно.
• Ссылочная прозрачность в информатике
• Регулируемый рерайтинг
• Исчисление Ро
• Сети взаимодействия

Примечания

1. Этот вариант предыдущего правила необходим, поскольку коммутативный закон A ∨ B = B ∨ A нельзя превратить в правило перезаписи. Правило типа A ∨ B → B ∨ A приведет к тому, что система перезаписи будет незавершенной.
2. поскольку применение этой замены к левой части правила дает числитель ${\displaystyle x*(y*z)}$ ${\displaystyle a*((a+1)*(a+2))}$
3. т.е. для каждого термина существует некоторая нормальная форма, например, h ( c , c ) имеет нормальные формы b и g ( b ), поскольку h ( c , c ) → f ( h ( c , c ), h ( c , c )) → ж ( час ( c , c ), ж ( час ( c , c ), час ( c , c ))) → ж ( час ( c , c ), г ( час ( c , c ))) → б , и час ( c , c ) → ж ( час ( c , c ), час ( c , c )) → грамм ( час ( c , c )) → ... → грамм ( б ); ни b , ни g ( b ) не могут быть переписаны дальше, поэтому система не является конфлюэнтной
4. т.е. существуют бесконечные дифференцирования, например час ( c , c ) → f ( h ( c , c ), час ( c , c )) → f ( f ( h ( c , c ), час ( c , c ) ) , час ( c , c )) → ж ( ж ( ж ( час ( c , c ), час ( c , c )) , час ( c , c )) , час ( c , c )) → ...

дальнейшее чтение

• Баадер, Франц ; Нипков, Тобиас (1999). Переписывание сроков и все такое . Издательство Кембриджского университета. ISBN 978-0-521-77920-3.316 страниц.
• Марк Безем, Ян Виллем Клоп , Роэль де Вриер («Тереза»), Term Rewriting Systems («TeReSe»), Cambridge University Press, 2003, ISBN 0-521-39115-6 . Это самая последняя всеобъемлющая монография. Однако он использует немало еще нестандартных обозначений и определений. Например, свойство Чёрча-Россера определяется как идентичное свойству слияния. 
• Нахум Дершовиц и Жан-Пьер Жуанно «Переписать системы», глава 6 в книге Яна ван Леувена (ред.), Справочник по теоретической информатике, том B: Формальные модели и семантика. , Elsevier и MIT Press, 1990, ISBN 0-444-88074-7 , стр. 243–320. Препринт этой главы находится в свободном доступе у авторов, но в нем отсутствуют рисунки. 
• Нахум Дершовиц и Дэвид Плейстед . «Переписывание», глава 9 в книге Джона Алана Робинсона и Андрея Воронкова (ред.), «Справочник по автоматизированному рассуждению» , том 1 .
• Жерар Юэ и Дерек Оппен, Уравнения и правила перезаписи, Исследование (1980), Стэнфордская группа проверки, Отчет № 15, Отчет Департамента компьютерных наук № STAN-CS-80-785
• Ян Виллем Клоп . «Системы переписывания терминов», глава 1 в книге «Самсон Абрамски» , Дов М. Габбай и Том Майбаум (ред.), «Справочник по логике в информатике», том 2: Предыстория: вычислительные структуры .
• Дэвид Плейстед. «Системы уравнений и переписывания терминов», в Дов М. Габбай , С. Дж. Хоггер и Джон Алан Робинсон (ред.), Справочник по логике в искусственном интеллекте и логическом программировании, Том 1 .
• Юрген Авенхаус и Клаус Мадленер. «Переписывание терминов и эквациональные рассуждения». В Ранан Б. Банерджи (ред.), Формальные методы искусственного интеллекта: справочник , Elsevier (1990).

Перезапись строк

• Рональд В. Бук и Фридрих Отто, Системы переписывания строк , Springer (1993).
• Бенджамин Беннингхофен, Сюзанна Кеммерих и Майкл М. Рихтер , Системы редукций . LNCS 277 , Springer-Verlag (1987).

Другой

• Мартин Дэвис , Рон Сигал, Элейн Дж. Вейкер , (1994) Вычислимость, сложность и языки: основы теоретической информатики – 2-е издание , Academic Press, ISBN 0-12-206382-1 . 

Внешние ссылки

• Домашняя страница переписывания
• Рабочая группа ИФИП 1.6
• Исследователи переписывания, Аарт Миддельдорп, Инсбрукский университет
• Портал прекращения
• Maude System — программная реализация универсальной системы переписывания терминов. ^[5]

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

1. Жозеф Гоген «Доказательство и переписывание», Международная конференция по алгебраическому и логическому программированию, 1990 г., Нэнси, Франция, стр. 1-24.
2. Скалторп, Нил; Фрисби, Николас; Гилл, Энди (2014). «Машина переписывания Канзасского университета» (PDF) . Журнал функционального программирования . 24 (4): 434–473. дои : 10.1017/S0956796814000185. ISSN  0956-7968. S2CID  16807490. Архивировано (PDF) из оригинала 22 сентября 2017 г. Проверено 12 февраля 2019 г.
3. Сян, Цзе; Киршнер, Элен; Лесканн, Пьер; Русинович, Майкл (1992). «Подход к переписыванию терминов для автоматического доказательства теорем». Журнал логического программирования . 14 (1–2): 71–99. дои : 10.1016/0743-1066(92)90047-7 .
4. Фрювирт, Том (1998). «Теория и практика правил обработки ограничений». Журнал логического программирования . 37 (1–3): 95–138. дои : 10.1016/S0743-1066(98)10005-5 .
5. Клавель, М.; Дуран, Ф.; Экер, С.; Линкольн, П.; Марти-Олиет, Н.; Месегер, Дж.; Кесада, Дж. Ф. (2002). «Мод: Спецификация и программирование в логике переписывания». Теоретическая информатика . 285 (2): 187–243. дои : 10.1016/S0304-3975(01)00359-0 .
6. Ким Марриотт; Питер Дж. Стаки (1998). Программирование с ограничениями: Введение. МТИ Пресс. стр. 436–. ISBN 978-0-262-13341-8.
7. Юрген Авенхаус; Клаус Мадленер (1990). «Переписывание терминов и уравнение». В РБ Банерджи (ред.). Формальные методы искусственного интеллекта . Справочник. Эльзевир. стр. 1–43.Здесь: Пример в разд.4.1, стр.24.
8. Роберт Фрейдин (1992). Основы генеративного синтаксиса. МТИ Пресс. ISBN 978-0-262-06144-5.
9. Книга ab и Отто, с. 10
10. Безем и др., с. 7,
11. Безем и др., с. 7
12. Мартин Дэвис и др. 1994, с. 178
13. Клоп, JW «Системы переписывания терминов» (PDF) . Статьи Нахума Дершовица и его студентов . Тель-Авивский университет. п. 12. Архивировано (PDF) из оригинала 15 августа 2021 года . Проверено 14 августа 2021 г.
14. Н. Дершовиц, Ж.-П. Жуанно (1990). Ян ван Леувен (ред.). Переписать системы . Справочник по теоретической информатике. Том. Б. Эльзевир. стр. 243–320.; здесь: Разд. 2.3
15. Макс Доше (1989). «Моделирование машин Тьюринга с помощью правила леволинейной перезаписи». Учеб. 3-й Межд. Конф. по методам и приложениям переписывания . ЛНКС. Том. 355. Спрингер. стр. 109–120.
16. Макс Доше (сентябрь 1992 г.). «Моделирование машин Тьюринга с помощью обычного правила перезаписи». Теоретическая информатика . 103 (2): 409–420. дои : 10.1016/0304-3975(92)90022-8 .
17. Жерар Юэ, DS Lankford (март 1978 г.). О единой проблеме остановки для систем переписывания терминов (PDF) (Технический отчет). ИРИА. п. 8. 283 . Проверено 16 июня 2013 г.
18. Бернхард Грамлих (июнь 1993 г.). «Относительно самого внутреннего, слабого, единообразного и модульного завершения систем переписывания терминов». Воронков, Андрей (ред.). Учеб. Международная конференция по логическому программированию и автоматическому рассуждению (LPAR) . ЛНАИ. Том. 624. Спрингер. стр. 285–296. Архивировано из оригинала 4 марта 2016 г. Проверено 19 июня 2014 г.Здесь: Пример 3.3
19. Ёсихито Тояма (1987). «Противоположные примеры прекращения действия систем переписывания терминов прямой суммы» (PDF) . Инф. Процесс. Летт . 25 (3): 141–143. дои : 10.1016/0020-0190(87)90122-0. hdl : 2433/99946 . Архивировано (PDF) из оригинала 13 ноября 2019 г. Проверено 13 ноября 2019 г.
20. Н. Дершовиц (1985). «Прекращение» (PDF) . В Жан-Пьере Жуанно (ред.). Учеб. РТА . ЛНКС. Том. 220. Спрингер. стр. 180–224. Архивировано (PDF) из оригинала 12 ноября 2013 г. Проверено 16 июня 2013 г.; здесь: стр.210
21. Вольфрам, Д.А. (1993). Клаузальная теория типов . Издательство Кембриджского университета. стр. 47–50. дои : 10.1017/CBO9780511569906. ISBN 9780521395380. S2CID  42331173.
22. Нипков, Тобиас; Прехофер, Кристиан (1998). «Переписывание высшего порядка и уравнение». В Бибеле, В.; Шмитт, П. (ред.). Автоматизированный вычет – основа для приложений. Том I: Основы . Клювер. стр. 399–430. Архивировано из оригинала 16 августа 2021 г. Проверено 16 августа 2021 г.