Consider the TRS R consisting of the rewrite rule 1: f(g(X)) -> f(X) There is one dependency pair: 2: F(g(X)) -> F(X) The approximated dependency graph contains one SCC: {2}. - Consider the SCC {2}. There are no usable rules. By taking the polynomial interpretation [F](x) = [g](x) = x + 1, rule 2 is strictly decreasing. Hence the TRS is terminating.