WikiDer > Критическая пара (логика)

Треугольная диаграмма критической пары, полученная из двух правил перезаписи s → т (верхний ряд, слева) и л→р (верно). В замена σ объединяет то субтерм s|_п с л. Результирующий термин наложения sσ[lσ]_п (нижний ряд, средний) можно переписать на термин tσ и sσ[rσ ']_п (нижний ряд, левый и правый) соответственно. Последние два члена образуют критическую пару. В конечном итоге они могут быть переписаны на общий термин, если набор правил перезаписи сливаться.

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

Например, в термине rewriting system with rules

ж(грамм(Икс,y),z)	→ грамм(Икс,z)
грамм(Икс,y)	→ Икс,

единственная критическая пара - это ⟨грамм(Икс,z), ж(Икс,z)⟩. Оба этих термина могут быть образованы от термина ж(грамм(Икс,y),z), применив одно правило перезаписи.

В качестве другого примера рассмотрим систему переписывания терминов с одним правилом

ж(Икс,y)

→ Икс.

Применяя это правило двумя разными способами к термину ж(ж(Икс,Икс),Икс), Мы видим, что (ж(Икс,Икс), ж(Икс,Икс)) является (тривиальной) критической парой.

Когда обе стороны критической пары могут уменьшать к тому же члену критическая пара называется сходящийся. Если одна сторона критической пары идентична другой, критическая пара называется банальный.

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

Слабое слияние явно влечет сходящиеся критические пары: если любая критическая пара ⟨а, б⟩ Возникает, затем а и б имеют общий редукт, поэтому критическая пара сходится.

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

• Завершение Кнута – Бендикса, алгоритм на основе критических пар для вычисления сливаться и прекращение система переписывания терминов, эквивалентная заданной

внешняя ссылка

• Вайсштейн, Эрик В. «Критическая пара». MathWorld.

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

• Франц Баадер и Тобиас Нипков, Перезапись терминов и все такое, Cambridge University Press, 1998 г. (ссылка на книгу)
• Тереза, Системы перезаписи терминов, Кембриджский трактат по теоретической информатике, 2003. (ссылка на книгу)