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

Termination of R to be shown. 



   R
     ↳Dependency Pair Analysis



R contains the following Dependency Pairs:

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

Furthermore, R contains one SCC. 


   R
     ↳DPs
       →DP Problem 1
         ↳Negative Polynomial Order


Dependency Pair:

APP(g, app(g, x)) -> APP(g, app(h, app(g, x)))


Rules:


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





The original DP problem is in applicative form. Its DPs and usable rules are the following.

APP(g, app(g, x)) -> APP(g, app(h, app(g, x)))


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


It is proper and hence, it can be A-transformed which results in the DP problem

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


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


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

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

This corresponds to the following dependency pair in applicative form:

APP(g, app(g, x)) -> APP(g, app(h, app(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:


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





Using the Dependency Graph resulted in no new DP problems.

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