Solution

3.6. Алгебраїчна парадигма

Дані представляються за допомогою термів або позначених графів, а алгоритми - системами правил переписування (орієнтованих рівностей чи умовних рівностей, співвідношень алгебри даних). Об’єкт, який визначається системою рівностей, за допомогою яких виражаються правила переписування, є відношенням конгруентності на множині всіх термів абсолютно вільної алгебри термів, що породжується константами. Це відношення визначається як конгруентне замикання співвідношень переписування, які розглядаються як тотожності алгебри термів.

Елементарним кроком обчислень в алгебраїчній парадигмі є мeтчінг (відповідність зразку), перевірка умов і підстановка. Стратегія переписування визначає, в якому порядку застосовуються правила переписування і підтерми (підвирази) поточного терма для співставлення з лівими частинами співвідношень. Для канонічних систем правил переписування результат не залежить від стратегії. Якщо система правил не є канонічною, то стратегія визначає не тільки час переписування, але й результат. В будь-якому випадку результат переписування, за умови закінчення обчислень, є термом, який еквівалентний висхідному термові за відношенням конгруен­тності, що визначається системою правил переписування. Тобто, стратегія вибирає результат в класі конгруентних термін. Відповідна алгебраїчна програма обчислення НСД наведена нижче.

RS(х,у) (

(x, х) = x,

(х > у) ((x, у) = (х - у, у)),

(x < у) ((x у) = (x, у - х))

).