Consider the TRS R consisting of the rewrite rules

1: f(a,a) -> f(a,b)
2: f(a,b) -> f(s(a),c)
3: f(s(X),c) -> f(X,c)
4: f(c,c) -> f(a,a)

There are 4 dependency pairs:

5: F(a,a) -> F(a,b)
6: F(a,b) -> F(s(a),c)
7: F(s(X),c) -> F(X,c)
8: F(c,c) -> F(a,a)

The approximated dependency graph contains one SCC:
{5-8}.

- Consider the SCC {5-8}.
There are no usable rules.
By taking the polynomial interpretation
[a] = 0,
[b] = [c] = 1,
[s](x) = x
and [F](x,y) = x + 1,
the rules in {5-7}
are weakly decreasing and
rule 8
is strictly decreasing.
There is one new SCC.

- Consider the SCC {7}.
By taking the polynomial interpretation
[c] = 1,
[s](x) = x + 1
and [F](x,y) = x + y + 1,
rule 7
is strictly decreasing.


Hence the TRS is terminating.