Нормальная форма (реферат) - Normal form (abstract rewriting)

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

Определение

Формально заявлено, если (А, →) является абстрактная система переписывания, немного Икс∈А в нормальная форма если нет у∈А существует такое, что Икс→у.

Например, используя термин «система переписывания» с одним правилом грамм(Икс,у)→Икс, период, термин грамм(грамм(4,2),грамм(3,1)) можно переписать следующим образом, применив правило к самому внешнему вхождению ^{[примечание 1]} из грамм:

грамм(грамм(4,2),грамм(3,1)) → грамм(4,2) → 4.

Поскольку к последнему члену 4 не применяется никаких правил, его нельзя переписать дальше, и, следовательно, это нормальная форма термина грамм(грамм(4,2),грамм(3,1)) относительно этой системы переписывания терминов.

Свойства нормализации

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

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

Другой пример: система единого правила { р(Икс,у)→р(у,Икс)} не имеет нормализующих свойств (не слабых или сильных), поскольку из любого члена, например р(4,2) начинается одиночная последовательность перезаписи, а именно. р(4,2)→р(2,4)→р(4,2)→р(2,4) → ..., что бесконечно долго.

Нормализация и конфлюентность

Лемма Ньюмана заявляет, что если абстрактная система переписывания А сильно нормализует и является слабо сливной, тогда А является сливаться.

Результат позволяет еще больше обобщить лемма о критической паре.^{[требуется разъяснение ]}

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

Каноническая форма

Примечания

^ Каждое появление грамм где применяется правило, выделено жирный шрифт.
^ Поскольку каждый термин, содержащий грамм можно переписать конечным числом применений первого правила к терму без каких-либо грамм, который находится в нормальной форме.
^ Поскольку к сроку грамм(3,3) второе правило можно применять снова и снова, не достигая какой-либо нормальной формы.
^ Для данного срока пусть м и п обозначают общее количество грамм и из грамм применительно к идентичным аргументам соответственно. Правильное применение любого правила снижает ценность м+п, что возможно только конечное число раз.