Term Rewriting System R:
[x, y, z, u]
f(j(x, y), y) -> g(f(x, k(y)))
f(x, h1(y, z)) -> h2(0, x, h1(y, z))
g(h2(x, y, h1(z, u))) -> h2(s(x), y, h1(z, u))
h2(x, j(y, h1(z, u)), h1(z, u)) -> h2(s(x), y, h1(s(z), u))
i(f(x, h(y))) -> y
i(h2(s(x), y, h1(x, z))) -> z
k(h(x)) -> h1(0, x)
k(h1(x, y)) -> h1(s(x), y)

Innermost Termination of R to be shown. 



   R
     ↳Dependency Pair Analysis



R contains the following Dependency Pairs:

F(j(x, y), y) -> G(f(x, k(y)))
F(j(x, y), y) -> F(x, k(y))
F(j(x, y), y) -> K(y)
F(x, h1(y, z)) -> H2(0, x, h1(y, z))
G(h2(x, y, h1(z, u))) -> H2(s(x), y, h1(z, u))
H2(x, j(y, h1(z, u)), h1(z, u)) -> H2(s(x), y, h1(s(z), u))

Furthermore, R contains two SCCs. 


   R
     ↳DPs
       →DP Problem 1
         ↳Usable Rules (Innermost)
       →DP Problem 2
         ↳UsableRules


Dependency Pair:

H2(x, j(y, h1(z, u)), h1(z, u)) -> H2(s(x), y, h1(s(z), u))


Rules:


f(j(x, y), y) -> g(f(x, k(y)))
f(x, h1(y, z)) -> h2(0, x, h1(y, z))
g(h2(x, y, h1(z, u))) -> h2(s(x), y, h1(z, u))
h2(x, j(y, h1(z, u)), h1(z, u)) -> h2(s(x), y, h1(s(z), u))
i(f(x, h(y))) -> y
i(h2(s(x), y, h1(x, z))) -> z
k(h(x)) -> h1(0, x)
k(h1(x, y)) -> h1(s(x), y)


Strategy:

innermost




As we are in the innermost case, we can delete all 8 non-usable-rules.


   R
     ↳DPs
       →DP Problem 1
         ↳UsableRules
           →DP Problem 3
             ↳Size-Change Principle
       →DP Problem 2
         ↳UsableRules


Dependency Pair:

H2(x, j(y, h1(z, u)), h1(z, u)) -> H2(s(x), y, h1(s(z), u))


Rule:

none


Strategy:

innermost




We number the DPs as follows:
  1. H2(x, j(y, h1(z, u)), h1(z, u)) -> H2(s(x), y, h1(s(z), u))
and get the following Size-Change Graph(s):
{1} , {1}
2>2

which lead(s) to this/these maximal multigraph(s):
{1} , {1}
2>2

DP: empty set
Oriented Rules: none

We used the order Homeomorphic Embedding Order with Non-Strict Precedence.
trivial

with Argument Filtering System:
h1(x1, x2) -> h1(x1, x2)
s(x1) -> s(x1)
j(x1, x2) -> j(x1, x2)

We obtain no new DP problems. 


   R
     ↳DPs
       →DP Problem 1
         ↳UsableRules
       →DP Problem 2
         ↳Usable Rules (Innermost)


Dependency Pair:

F(j(x, y), y) -> F(x, k(y))


Rules:


f(j(x, y), y) -> g(f(x, k(y)))
f(x, h1(y, z)) -> h2(0, x, h1(y, z))
g(h2(x, y, h1(z, u))) -> h2(s(x), y, h1(z, u))
h2(x, j(y, h1(z, u)), h1(z, u)) -> h2(s(x), y, h1(s(z), u))
i(f(x, h(y))) -> y
i(h2(s(x), y, h1(x, z))) -> z
k(h(x)) -> h1(0, x)
k(h1(x, y)) -> h1(s(x), y)


Strategy:

innermost




As we are in the innermost case, we can delete all 6 non-usable-rules.


   R
     ↳DPs
       →DP Problem 1
         ↳UsableRules
       →DP Problem 2
         ↳UsableRules
           →DP Problem 4
             ↳Size-Change Principle


Dependency Pair:

F(j(x, y), y) -> F(x, k(y))


Rules:


k(h1(x, y)) -> h1(s(x), y)
k(h(x)) -> h1(0, x)


Strategy:

innermost




We number the DPs as follows:
  1. F(j(x, y), y) -> F(x, k(y))
and get the following Size-Change Graph(s):
{1} , {1}
1>1

which lead(s) to this/these maximal multigraph(s):
{1} , {1}
1>1

DP: empty set
Oriented Rules: none

We used the order Homeomorphic Embedding Order with Non-Strict Precedence.
trivial

with Argument Filtering System:
j(x1, x2) -> j(x1, x2)

We obtain no new DP problems.

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