Jump to content

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

(Перенаправлено с Term-rewriting )

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

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

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

[ редактировать ]

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

( исключение двойного отрицания )
( законы де Моргана )
( дистрибутивность )
[примечание 1]

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

Арифметика

[ редактировать ]

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

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

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

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

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

Лингвистика

[ редактировать ]

В лингвистике , правила структуры фраз , также называемые правилами перезаписи используются в некоторых системах порождающей грамматики . [8] как средство создания грамматически правильных предложений языка. Такое правило обычно имеет форму , где A — метка синтаксической категории , такая как именное словосочетание или предложение , а X — последовательность таких меток или морфем , выражающая тот факт, что A можно заменить на X при создании составной структуры предложения. Например, правило означает, что предложение может состоять из именной группы (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 называется конвергентной или канонической .

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

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

[ редактировать ]

Система переписывания строк (SRS), также известная как система полу-Туэ , использует свободную моноидную структуру строк ( слов) в алфавите для расширения отношения переписывания. , ко всем строкам алфавита, которые содержат левые и соответственно правые части некоторых правил в качестве подстрок . Формально система полуТуэ представляет собой кортеж где является (обычно конечным) алфавитом, и — это бинарное отношение между некоторыми (фиксированными) строками в алфавите, называемое набором правил перезаписи . Отношение одношаговой перезаписи вызванный на определяется как: если любые строки, то если существуют такой, что , , и . С это отношение к , пара соответствует определению абстрактной системы переписывания. Поскольку пустая строка находится в , является подмножеством . Если отношение симметрична . то система называется системой Туэ ,

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

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

Мы сразу получаем очень полезные связи с другими областями алгебры. Например, алфавит с правилами , где пустая строка — представление свободной группы на одном генераторе. Если вместо этого правила просто , то получим представление бициклического моноида . Таким образом, системы полуТуэ представляют собой естественную основу для решения проблемы слов для моноидов и групп. Фактически, каждый моноид имеет представление вида , т. е. он всегда может быть представлен системой полу-Туэ, возможно, над бесконечным алфавитом.

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

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

[ редактировать ]
Рис.1: Схематический треугольник применения правила перезаписи на позиции в термине с соответствующей заменой
Рис.2: Правило левого термина соответствие по сроку

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

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

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

[ редактировать ]

Правило перезаписи — это пара терминов , обычно записываемая как , чтобы указать, что левая часть l может быть заменена правой частью r . Система переписывания терминов представляет собой набор R таких правил. Правило может быть применено к термину s, если левый термин l соответствует некоторому подтерму s , то есть если существует некоторая замена такой, что подчлен с корнем в некоторой позиции p является результатом применения замены к термину л . Подтерм, соответствующий левой части правила, называется редексом или сокращаемым выражением . [14] Результатом применения этого правила является результат замены подтерма в позиции p в s на термин с заменой применено, см. рисунок 1. В данном случае говорят, что оно переписано за один шаг или переписано напрямую , чтобы по системе , формально обозначаемый как , или как некоторыми авторами.

Если срок можно переписать в несколько шагов в термин , то есть, если , термин говорят, что он переписан на , формально обозначаемый как . Другими словами, отношение является транзитивным замыканием отношения ; часто также обозначение используется для обозначения рефлексивно-транзитивного замыкания , то есть, если или . [15] Переписывание термина, заданное множеством правил можно рассматривать как абстрактную систему переписывания, определенную выше , с терминами в качестве ее объектов и как его отношение перезаписи.

Например, — это правило перезаписи, обычно используемое для установления нормальной формы относительно ассоциативности .Это правило можно применить к числителю в термине с соответствующей заменой , см. рисунок 2. [примечание 2] Применение этой замены к правой части правила дает член , и замена числителя этим термином дает , что является результатом применения правила перезаписи. В целом, применение правила перезаписи привело к тому, что называется «применением закона ассоциативности для к » в элементарной алгебре. В качестве альтернативы это правило можно было применить к знаменателю исходного члена, что дало бы .

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

[ редактировать ]

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

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

Следующая система перезаписи терминов нормализуется, [примечание 3] но не прекращается, [примечание 4] и не сливаются: [19]

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

и

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

Этот результат опровергает гипотезу Дершовица о том , что [21] который утверждал, что объединение двух завершающих систем переписывания терминов и снова завершается, если все левые части и правые части линейны , и нет никаких « перекрытий ». между левыми частями и правые части . Всем этим свойствам удовлетворяют примеры Тоямы.

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

[ редактировать ]

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

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Этот вариант предыдущего правила необходим, поскольку коммутативный закон A B = B A нельзя превратить в правило перезаписи. Правило типа A B B 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 )) → ...

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

[ редактировать ]
Перезапись строк
  • Рональд В. Бук и Фридрих Отто, Системы переписывания строк , Springer (1993).
  • Бенджамин Беннингхофен, Сюзанна Кеммерих и Майкл М. Рихтер , Системы редукций . LNCS 277 , Springer Verlag (1987).
Другой
[ редактировать ]
  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. ^ Jump up to: а б Клавель, М.; Дуран, Ф.; Экер, С.; Линкольн, П.; Марти-Олиет, Н.; Месегер, Дж.; Кесада, Дж. Ф. (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. ^ Jump up to: а б Книга и Отто, с. 10
  10. ^ Безем и др., с. 7,
  11. ^ Безем и др., с. 7
  12. ^ Мартин Дэвис и др. 1994, с. 178
  13. ^ Дершовиц, Жуано (1990), раздел 1, стр.245
  14. ^ Клоп, Дж.В. «Системы переписывания терминов» (PDF) . Статьи Нахума Дершовица и его студентов . Тель-Авивский университет. п. 12. Архивировано (PDF) из оригинала 15 августа 2021 года . Проверено 14 августа 2021 г.
  15. ^ Н. Дершовиц, Ж.-П. Жуанно (1990). Ян ван Леувен (ред.). Переписать системы . Справочник по теоретической информатике. Том. Б. Эльзевир. стр. 243–320. ; здесь: Разд. 2.3
  16. ^ Макс Доше (1989). «Моделирование машин Тьюринга с помощью правила леволинейной перезаписи». Учеб. 3-й Межд. Конф. по методам и приложениям переписывания . ЛНКС. Том. 355. Спрингер. стр. 109–120.
  17. ^ Макс Доше (сентябрь 1992 г.). «Моделирование машин Тьюринга по правилу обычной перезаписи» . Теоретическая информатика . 103 (2): 409–420. дои : 10.1016/0304-3975(92)90022-8 .
  18. ^ Жерар Юэ, сержант Ланкфорд (март 1978 г.). О единой проблеме остановки для систем переписывания терминов (PDF) (Технический отчет). ИРИА. п. 8. 283 . Проверено 16 июня 2013 г.
  19. ^ Бернхард Грамлих (июнь 1993 г.). «Относительно самого внутреннего, слабого, единообразного и модульного завершения систем переписывания терминов» . Воронков, Андрей (ред.). Учеб. Международная конференция по логическому программированию и автоматическому рассуждению (LPAR) . ЛНАИ. Том. 624. Спрингер. стр. 285–296. Архивировано из оригинала 4 марта 2016 г. Проверено 19 июня 2014 г. Здесь: Пример 3.3
  20. ^ Ёшихито Тояма (1987). «Противоположные примеры прекращения действия систем переписывания терминов прямой суммы» (PDF) . Инф. Процесс. Летт . 25 (3): 141–143. дои : 10.1016/0020-0190(87)90122-0 . hdl : 2433/99946 . Архивировано (PDF) из оригинала 13 ноября 2019 г. Проверено 13 ноября 2019 г.
  21. ^ Н. Дершовиц (1985). «Прекращение» (PDF) . В Жан-Пьере Жуанно (ред.). Учеб. РТА . ЛНКС. Том. 220. Спрингер. стр. 180–224. Архивировано (PDF) из оригинала 12 ноября 2013 г. Проверено 16 июня 2013 г. ; здесь: стр.210
  22. ^ Вольфрам, Д.А. (1993). Клаузальная теория типов . Издательство Кембриджского университета. стр. 47–50. дои : 10.1017/CBO9780511569906 . ISBN  9780521395380 . S2CID   42331173 .
  23. ^ Нипков, Тобиас; Прехофер, Кристиан (1998). «Переписывание высшего порядка и уравнения» . В Бибеле, В.; Шмитт, П. (ред.). Автоматизированный вычет – основа для приложений. Том I: Основы . Клювер. стр. 399–430. Архивировано из оригинала 16 августа 2021 г. Проверено 16 августа 2021 г.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 15c7f5dcb601eb5633049aca5cf7b433__1719356460
URL1:https://arc.ask3.ru/arc/aa/15/33/15c7f5dcb601eb5633049aca5cf7b433.html
Заголовок, (Title) документа по адресу, URL1:
Rewriting - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)