Term Rewriting System R:
[x]
g(h(g(x))) -> g(x)
g(g(x)) -> g(h(g(x)))
h(h(x)) -> h(f(h(x), x))

Termination of R to be shown. 



   R
     ↳Dependency Pair Analysis



R contains the following Dependency Pairs:

G(g(x)) -> G(h(g(x)))
G(g(x)) -> H(g(x))
H(h(x)) -> H(f(h(x), x))

Furthermore, R contains one SCC. 


   R
     ↳DPs
       →DP Problem 1
         ↳Negative Polynomial Order


Dependency Pair:

G(g(x)) -> G(h(g(x)))


Rules:


g(h(g(x))) -> g(x)
g(g(x)) -> g(h(g(x)))
h(h(x)) -> h(f(h(x), x))





The following Dependency Pair can be strictly oriented using the given order.

G(g(x)) -> G(h(g(x)))


Moreover, the following usable rules (regarding the implicit AFS) are oriented.

h(h(x)) -> h(f(h(x), x))
g(h(g(x))) -> g(x)
g(g(x)) -> g(h(g(x)))


Used ordering:
Polynomial Order with Interpretation:

POL( G(x1) ) = x1

POL( g(x1) ) = 1

POL( h(x1) ) = 0


This results in one new DP problem. 


   R
     ↳DPs
       →DP Problem 1
         ↳Neg POLO
           →DP Problem 2
             ↳Dependency Graph


Dependency Pair:


Rules:


g(h(g(x))) -> g(x)
g(g(x)) -> g(h(g(x)))
h(h(x)) -> h(f(h(x), x))





Using the Dependency Graph resulted in no new DP problems.

Termination of R successfully shown.
Duration:
0:00 minutes