Consider the TRS R consisting of the rewrite rule 1: a(b(x)) -> a(c(b(x))) There is one dependency pair: 2: A(b(x)) -> A(c(b(x))) The approximated dependency graph contains no SCCs and hence the TRS is trivially terminating.