В математической логике , А критическая пара возникает в перспективе переписывания систем , где правила перезаписи перекрывают друг друга , чтобы получить два различных термина. Более подробно, ( t 1 , t 2 ) является критической парой, если существует термин t, для которого два разных применения правила перезаписи (либо одно и то же правило, применяемое по-разному, или два разных правила) дают термины t 1 и t 2 .
Например, в термине rewriting system with rules
f ( g ( x , y ), z ) → g ( x , z ) г ( х , у ) → х ,
единственная критическая пара ⟨ г ( х , г ), е ( х , г )⟩. Оба эти члена могут быть получены из члена f ( g ( x , y ), z ), применив одно правило перезаписи.
В качестве другого примера рассмотрим систему переписывания терминов с одним правилом
f ( x , y ) → х .
Применяя это правило двумя разными способами к члену f ( f ( x , x ), x ), мы видим, что ( f ( x , x ), f ( x , x )) является (тривиальной) критической парой.
Когда обе стороны критической пары могут сводиться к одному члену, критическая пара называется сходящейся . Если одна сторона критической пары идентична другой, критическая пара называется тривиальной .
Если система переписывания терминов не является конфлюэнтной , критическая пара может не сойтись, поэтому критические пары являются потенциальными источниками, где слияние не удастся. Фактически, лемма о критических парах утверждает, что система переписывания термов является слабо (то есть локально) конфлюэнтной, если все критические пары сходятся. Таким образом, чтобы выяснить, является ли система переписывания терминов слабо конфлюэнтной, достаточно проверить все критические пары и посмотреть, сходятся ли они. Это позволяет алгоритмически выяснить, является ли система переписывания терминов слабо конфлюэнтной или нет, учитывая, что можно алгоритмически проверить, сходятся ли два термина.
Слабые впадения явно подразумевают конвергентные критические пары: если любая критическая пара ⟨ , б ⟩ возникает, то и б имеют общую REDUCT и , следовательно , критическая пара сходится.
Смотрите также
- Завершение Кнута – Бендикса , алгоритм, основанный на критических парах, для вычисления сливающейся и завершающей системы перезаписи терминов, эквивалентной заданной
Внешние ссылки
Рекомендации
- Франц Баадер и Тобиас Нипков , « Изменение терминов и все такое» , Cambridge University Press, 1998 (ссылка на книгу)
- Тереза, Системы перезаписи терминов , Кембриджские тракты по теоретической информатике, 2003 г. (веб-ссылка на книгу)