Ортогональность (переписывание терминов) - Orthogonality (term rewriting)

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

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

Например, система переписывания терминов с правилами редукции

${displaystyle ho _{1} : f(x,y)ightarrow g(y)}$

${displaystyle ho _{2} : h(y)ightarrow f(g(y),y)}$

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

Системы ортогональной перезаписи термов сливаться.