YES TRS: { gcd(x, 0()) -> x, gcd(0(), y) -> y, gcd(s(x), s(y)) -> if(<(x, y), gcd(s(x), -(y, x)), gcd(-(x, y), s(y)))} DP: Strict: {gcd#(s(x), s(y)) -> gcd#(s(x), -(y, x)), gcd#(s(x), s(y)) -> gcd#(-(x, y), s(y))} Weak: { gcd(x, 0()) -> x, gcd(0(), y) -> y, gcd(s(x), s(y)) -> if(<(x, y), gcd(s(x), -(y, x)), gcd(-(x, y), s(y)))} EDG: {} SCCS: Qed