Consider the TRS R consisting of the rewrite rules

1: f(f(x)) -> f(c(f(x)))
2: f(f(x)) -> f(d(f(x)))
3: g(c(x)) -> x
4: g(d(x)) -> x
5: g(c(h(0))) -> g(d(1))
6: g(c(1)) -> g(d(h(0)))
7: g(h(x)) -> g(x)

There are 5 dependency pairs:

8: F(f(x)) -> F(c(f(x)))
9: F(f(x)) -> F(d(f(x)))
10: G(c(h(0))) -> G(d(1))
11: G(c(1)) -> G(d(h(0)))
12: G(h(x)) -> G(x)

The approximated dependency graph contains one SCC:
{12}.

- Consider the SCC {12}.
There are no usable rules.
By taking the polynomial interpretation
[G](x) = [h](x) = x + 1,
rule 12
is strictly decreasing.

Hence the TRS is terminating.