Consider the TRS R consisting of the rewrite rules 1: x * (y + z) -> (x * y) + (x * z) 2: (x + y) * z -> (x * z) + (y * z) 3: x * 1 -> x 4: 1 * y -> y There are 4 dependency pairs: 5: x *# (y + z) -> x *# y 6: x *# (y + z) -> x *# z 7: (x + y) *# z -> x *# z 8: (x + y) *# z -> y *# z The approximated dependency graph contains one SCC: {5-8}. - Consider the SCC {5-8}. There are no usable rules. By taking the polynomial interpretation [*#](x,y) = [+](x,y) = x + y + 1, the rules in {5-8} are strictly decreasing. Hence the TRS is terminating.