Term Rewriting System R:
[x]
f(x) -> s(x)
f(s(s(x))) -> s(f(f(x)))

Innermost Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

F(s(s(x))) -> F(f(x))
F(s(s(x))) -> F(x)

Furthermore, R contains one SCC.


   R
DPs
       →DP Problem 1
Narrowing Transformation


Dependency Pairs:

F(s(s(x))) -> F(x)
F(s(s(x))) -> F(f(x))


Rules:


f(x) -> s(x)
f(s(s(x))) -> s(f(f(x)))


Strategy:

innermost




On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

F(s(s(x))) -> F(f(x))
two new Dependency Pairs are created:

F(s(s(x''))) -> F(s(x''))
F(s(s(s(s(x''))))) -> F(s(f(f(x''))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Narrowing Transformation


Dependency Pairs:

F(s(s(s(s(x''))))) -> F(s(f(f(x''))))
F(s(s(x''))) -> F(s(x''))
F(s(s(x))) -> F(x)


Rules:


f(x) -> s(x)
f(s(s(x))) -> s(f(f(x)))


Strategy:

innermost




On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

F(s(s(s(s(x''))))) -> F(s(f(f(x''))))
three new Dependency Pairs are created:

F(s(s(s(s(x'''))))) -> F(s(s(f(x'''))))
F(s(s(s(s(x'''))))) -> F(s(f(s(x'''))))
F(s(s(s(s(s(s(x'))))))) -> F(s(f(s(f(f(x'))))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 3
Forward Instantiation Transformation


Dependency Pairs:

F(s(s(s(s(s(s(x'))))))) -> F(s(f(s(f(f(x'))))))
F(s(s(s(s(x'''))))) -> F(s(f(s(x'''))))
F(s(s(s(s(x'''))))) -> F(s(s(f(x'''))))
F(s(s(x))) -> F(x)
F(s(s(x''))) -> F(s(x''))


Rules:


f(x) -> s(x)
f(s(s(x))) -> s(f(f(x)))


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

F(s(s(x))) -> F(x)
four new Dependency Pairs are created:

F(s(s(s(s(x''))))) -> F(s(s(x'')))
F(s(s(s(s(x''''))))) -> F(s(s(x'''')))
F(s(s(s(s(s(s(x'''''))))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(s(s(s(s(s(x'''))))))))) -> F(s(s(s(s(s(s(x''')))))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 4
Forward Instantiation Transformation


Dependency Pairs:

F(s(s(s(s(s(s(s(s(x'''))))))))) -> F(s(s(s(s(s(s(x''')))))))
F(s(s(s(s(s(s(x'''''))))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(s(x''''))))) -> F(s(s(x'''')))
F(s(s(s(s(x''))))) -> F(s(s(x'')))
F(s(s(s(s(x'''))))) -> F(s(f(s(x'''))))
F(s(s(s(s(x'''))))) -> F(s(s(f(x'''))))
F(s(s(x''))) -> F(s(x''))
F(s(s(s(s(s(s(x'))))))) -> F(s(f(s(f(f(x'))))))


Rules:


f(x) -> s(x)
f(s(s(x))) -> s(f(f(x)))


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

F(s(s(x''))) -> F(s(x''))
seven new Dependency Pairs are created:

F(s(s(s(x'''')))) -> F(s(s(x'''')))
F(s(s(s(s(s(x''''')))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(s(s(s(s(x'''')))))))) -> F(s(s(s(s(s(s(x'''')))))))
F(s(s(s(s(s(x'''')))))) -> F(s(s(s(s(x'''')))))
F(s(s(s(s(s(x'''''')))))) -> F(s(s(s(s(x'''''')))))
F(s(s(s(s(s(s(s(x''''''')))))))) -> F(s(s(s(s(s(s(x''''''')))))))
F(s(s(s(s(s(s(s(s(s(x''''')))))))))) -> F(s(s(s(s(s(s(s(s(x''''')))))))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 5
Forward Instantiation Transformation


Dependency Pairs:

F(s(s(s(s(s(s(s(s(s(x''''')))))))))) -> F(s(s(s(s(s(s(s(s(x''''')))))))))
F(s(s(s(s(s(s(s(x''''''')))))))) -> F(s(s(s(s(s(s(x''''''')))))))
F(s(s(s(s(s(x'''''')))))) -> F(s(s(s(s(x'''''')))))
F(s(s(s(s(s(x'''')))))) -> F(s(s(s(s(x'''')))))
F(s(s(s(s(s(s(s(x'''')))))))) -> F(s(s(s(s(s(s(x'''')))))))
F(s(s(s(s(s(x''''')))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(x'''')))) -> F(s(s(x'''')))
F(s(s(s(s(s(s(x'''''))))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(s(x''''))))) -> F(s(s(x'''')))
F(s(s(s(s(x''))))) -> F(s(s(x'')))
F(s(s(s(s(s(s(x'))))))) -> F(s(f(s(f(f(x'))))))
F(s(s(s(s(x'''))))) -> F(s(f(s(x'''))))
F(s(s(s(s(x'''))))) -> F(s(s(f(x'''))))
F(s(s(s(s(s(s(s(s(x'''))))))))) -> F(s(s(s(s(s(s(x''')))))))


Rules:


f(x) -> s(x)
f(s(s(x))) -> s(f(f(x)))


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

F(s(s(s(s(x''))))) -> F(s(s(x'')))
13 new Dependency Pairs are created:

F(s(s(s(s(s(s(x'''''))))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(s(s(s(s(s(x''''))))))))) -> F(s(s(s(s(s(s(x'''')))))))
F(s(s(s(s(s(s(x''''))))))) -> F(s(s(s(s(x'''')))))
F(s(s(s(s(s(s(x''''''))))))) -> F(s(s(s(s(x'''''')))))
F(s(s(s(s(s(s(s(s(x'''''''))))))))) -> F(s(s(s(s(s(s(x''''''')))))))
F(s(s(s(s(s(s(s(s(s(s(x'''''))))))))))) -> F(s(s(s(s(s(s(s(s(x''''')))))))))
F(s(s(s(s(s(x'''''')))))) -> F(s(s(s(x''''''))))
F(s(s(s(s(s(s(s(x''''''')))))))) -> F(s(s(s(s(s(x'''''''))))))
F(s(s(s(s(s(s(s(s(s(x'''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''))))))))
F(s(s(s(s(s(s(s(x'''''')))))))) -> F(s(s(s(s(s(x''''''))))))
F(s(s(s(s(s(s(s(x'''''''')))))))) -> F(s(s(s(s(s(x''''''''))))))
F(s(s(s(s(s(s(s(s(s(x''''''''')))))))))) -> F(s(s(s(s(s(s(s(x'''''''''))))))))
F(s(s(s(s(s(s(s(s(s(s(s(x''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x'''''''))))))))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 6
Forward Instantiation Transformation


Dependency Pairs:

F(s(s(s(s(s(s(s(s(s(s(s(x''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x'''''''))))))))))
F(s(s(s(s(s(s(s(s(s(x''''''''')))))))))) -> F(s(s(s(s(s(s(s(x'''''''''))))))))
F(s(s(s(s(s(s(s(x'''''''')))))))) -> F(s(s(s(s(s(x''''''''))))))
F(s(s(s(s(s(s(s(x'''''')))))))) -> F(s(s(s(s(s(x''''''))))))
F(s(s(s(s(s(s(s(s(s(x'''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''))))))))
F(s(s(s(s(s(s(s(x''''''')))))))) -> F(s(s(s(s(s(x'''''''))))))
F(s(s(s(s(s(x'''''')))))) -> F(s(s(s(x''''''))))
F(s(s(s(s(s(s(s(s(s(s(x'''''))))))))))) -> F(s(s(s(s(s(s(s(s(x''''')))))))))
F(s(s(s(s(s(s(s(s(x'''''''))))))))) -> F(s(s(s(s(s(s(x''''''')))))))
F(s(s(s(s(s(s(x''''''))))))) -> F(s(s(s(s(x'''''')))))
F(s(s(s(s(s(s(x''''))))))) -> F(s(s(s(s(x'''')))))
F(s(s(s(s(s(s(s(s(x''''))))))))) -> F(s(s(s(s(s(s(x'''')))))))
F(s(s(s(s(s(s(x'''''))))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(s(s(s(s(x''''''')))))))) -> F(s(s(s(s(s(s(x''''''')))))))
F(s(s(s(s(s(x'''''')))))) -> F(s(s(s(s(x'''''')))))
F(s(s(s(s(s(x'''')))))) -> F(s(s(s(s(x'''')))))
F(s(s(s(s(s(s(s(x'''')))))))) -> F(s(s(s(s(s(s(x'''')))))))
F(s(s(s(s(s(x''''')))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(x'''')))) -> F(s(s(x'''')))
F(s(s(s(s(s(s(s(s(x'''))))))))) -> F(s(s(s(s(s(s(x''')))))))
F(s(s(s(s(s(s(x'''''))))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(s(x''''))))) -> F(s(s(x'''')))
F(s(s(s(s(s(s(x'))))))) -> F(s(f(s(f(f(x'))))))
F(s(s(s(s(x'''))))) -> F(s(f(s(x'''))))
F(s(s(s(s(x'''))))) -> F(s(s(f(x'''))))
F(s(s(s(s(s(s(s(s(s(x''''')))))))))) -> F(s(s(s(s(s(s(s(s(x''''')))))))))


Rules:


f(x) -> s(x)
f(s(s(x))) -> s(f(f(x)))


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

F(s(s(s(s(x''''))))) -> F(s(s(x'''')))
20 new Dependency Pairs are created:

F(s(s(s(s(s(s(x''''''))))))) -> F(s(s(s(s(x'''''')))))
F(s(s(s(s(s(s(s(s(x'''))))))))) -> F(s(s(s(s(s(s(x''')))))))
F(s(s(s(s(s(s(s(s(x'''''''))))))))) -> F(s(s(s(s(s(s(x''''''')))))))
F(s(s(s(s(s(s(s(s(s(s(x''''''))))))))))) -> F(s(s(s(s(s(s(s(s(x'''''')))))))))
F(s(s(s(s(s(x'''''')))))) -> F(s(s(s(x''''''))))
F(s(s(s(s(s(s(s(x''''''')))))))) -> F(s(s(s(s(s(x'''''''))))))
F(s(s(s(s(s(s(s(s(s(x'''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''))))))))
F(s(s(s(s(s(s(s(x'''''')))))))) -> F(s(s(s(s(s(x''''''))))))
F(s(s(s(s(s(s(s(x'''''''')))))))) -> F(s(s(s(s(s(x''''''''))))))
F(s(s(s(s(s(s(s(s(s(x''''''''')))))))))) -> F(s(s(s(s(s(s(s(x'''''''''))))))))
F(s(s(s(s(s(s(s(s(s(s(s(x''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x'''''''))))))))))
F(s(s(s(s(s(s(s(s(x''''''))))))))) -> F(s(s(s(s(s(s(x'''''')))))))
F(s(s(s(s(s(s(s(s(x''''''''))))))))) -> F(s(s(s(s(s(s(x'''''''')))))))
F(s(s(s(s(s(s(s(s(s(s(x'''''''''))))))))))) -> F(s(s(s(s(s(s(s(s(x''''''''')))))))))
F(s(s(s(s(s(s(s(s(s(s(s(s(x'''''''))))))))))))) -> F(s(s(s(s(s(s(s(s(s(s(x''''''')))))))))))
F(s(s(s(s(s(s(s(s(s(s(s(x'''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x''''''''))))))))))
F(s(s(s(s(s(s(s(s(s(x'''''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''''))))))))
F(s(s(s(s(s(s(s(s(s(x'''''''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''''''))))))))
F(s(s(s(s(s(s(s(s(s(s(s(x''''''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x'''''''''''))))))))))
F(s(s(s(s(s(s(s(s(s(s(s(s(s(x''''''''')))))))))))))) -> F(s(s(s(s(s(s(s(s(s(s(s(x'''''''''))))))))))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 7
Polynomial Ordering


Dependency Pairs:

F(s(s(s(s(s(s(s(s(s(s(s(s(s(x''''''''')))))))))))))) -> F(s(s(s(s(s(s(s(s(s(s(s(x'''''''''))))))))))))
F(s(s(s(s(s(s(s(s(s(s(s(x''''''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x'''''''''''))))))))))
F(s(s(s(s(s(s(s(s(s(x'''''''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''''''))))))))
F(s(s(s(s(s(s(s(s(s(x'''''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''''))))))))
F(s(s(s(s(s(s(s(s(s(s(s(x'''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x''''''''))))))))))
F(s(s(s(s(s(s(s(s(s(s(s(s(x'''''''))))))))))))) -> F(s(s(s(s(s(s(s(s(s(s(x''''''')))))))))))
F(s(s(s(s(s(s(s(s(s(s(x'''''''''))))))))))) -> F(s(s(s(s(s(s(s(s(x''''''''')))))))))
F(s(s(s(s(s(s(s(s(x''''''''))))))))) -> F(s(s(s(s(s(s(x'''''''')))))))
F(s(s(s(s(s(s(s(s(x''''''))))))))) -> F(s(s(s(s(s(s(x'''''')))))))
F(s(s(s(s(s(s(s(s(s(s(s(x''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x'''''''))))))))))
F(s(s(s(s(s(s(s(s(s(x''''''''')))))))))) -> F(s(s(s(s(s(s(s(x'''''''''))))))))
F(s(s(s(s(s(s(s(x'''''''')))))))) -> F(s(s(s(s(s(x''''''''))))))
F(s(s(s(s(s(s(s(x'''''')))))))) -> F(s(s(s(s(s(x''''''))))))
F(s(s(s(s(s(s(s(s(s(x'''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''))))))))
F(s(s(s(s(s(s(s(x''''''')))))))) -> F(s(s(s(s(s(x'''''''))))))
F(s(s(s(s(s(x'''''')))))) -> F(s(s(s(x''''''))))
F(s(s(s(s(s(s(s(s(s(s(x''''''))))))))))) -> F(s(s(s(s(s(s(s(s(x'''''')))))))))
F(s(s(s(s(s(s(s(s(x'''''''))))))))) -> F(s(s(s(s(s(s(x''''''')))))))
F(s(s(s(s(s(s(s(s(x'''))))))))) -> F(s(s(s(s(s(s(x''')))))))
F(s(s(s(s(s(s(x''''''))))))) -> F(s(s(s(s(x'''''')))))
F(s(s(s(s(s(s(s(s(s(x''''''''')))))))))) -> F(s(s(s(s(s(s(s(x'''''''''))))))))
F(s(s(s(s(s(s(s(x'''''''')))))))) -> F(s(s(s(s(s(x''''''''))))))
F(s(s(s(s(s(s(s(x'''''')))))))) -> F(s(s(s(s(s(x''''''))))))
F(s(s(s(s(s(s(s(s(s(x'''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''))))))))
F(s(s(s(s(s(s(s(x''''''')))))))) -> F(s(s(s(s(s(x'''''''))))))
F(s(s(s(s(s(x'''''')))))) -> F(s(s(s(x''''''))))
F(s(s(s(s(s(s(s(s(s(s(x'''''))))))))))) -> F(s(s(s(s(s(s(s(s(x''''')))))))))
F(s(s(s(s(s(s(s(s(x'''''''))))))))) -> F(s(s(s(s(s(s(x''''''')))))))
F(s(s(s(s(s(s(x''''''))))))) -> F(s(s(s(s(x'''''')))))
F(s(s(s(s(s(s(x''''))))))) -> F(s(s(s(s(x'''')))))
F(s(s(s(s(s(s(s(s(x''''))))))))) -> F(s(s(s(s(s(s(x'''')))))))
F(s(s(s(s(s(s(x'''''))))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(s(s(s(s(s(s(x''''')))))))))) -> F(s(s(s(s(s(s(s(s(x''''')))))))))
F(s(s(s(s(s(s(s(x''''''')))))))) -> F(s(s(s(s(s(s(x''''''')))))))
F(s(s(s(s(s(x'''''')))))) -> F(s(s(s(s(x'''''')))))
F(s(s(s(s(s(x'''')))))) -> F(s(s(s(s(x'''')))))
F(s(s(s(s(s(s(s(x'''')))))))) -> F(s(s(s(s(s(s(x'''')))))))
F(s(s(s(s(s(x''''')))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(x'''')))) -> F(s(s(x'''')))
F(s(s(s(s(s(s(s(s(x'''))))))))) -> F(s(s(s(s(s(s(x''')))))))
F(s(s(s(s(s(s(x'''''))))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(s(s(s(x'))))))) -> F(s(f(s(f(f(x'))))))
F(s(s(s(s(x'''))))) -> F(s(f(s(x'''))))
F(s(s(s(s(x'''))))) -> F(s(s(f(x'''))))
F(s(s(s(s(s(s(s(s(s(s(s(x''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x'''''''))))))))))


Rules:


f(x) -> s(x)
f(s(s(x))) -> s(f(f(x)))


Strategy:

innermost




The following dependency pairs can be strictly oriented:

F(s(s(s(s(s(s(s(s(s(s(s(s(s(x''''''''')))))))))))))) -> F(s(s(s(s(s(s(s(s(s(s(s(x'''''''''))))))))))))
F(s(s(s(s(s(s(s(s(s(s(s(x''''''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x'''''''''''))))))))))
F(s(s(s(s(s(s(s(s(s(x'''''''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''''''))))))))
F(s(s(s(s(s(s(s(s(s(x'''''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''''))))))))
F(s(s(s(s(s(s(s(s(s(s(s(x'''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x''''''''))))))))))
F(s(s(s(s(s(s(s(s(s(s(s(s(x'''''''))))))))))))) -> F(s(s(s(s(s(s(s(s(s(s(x''''''')))))))))))
F(s(s(s(s(s(s(s(s(s(s(x'''''''''))))))))))) -> F(s(s(s(s(s(s(s(s(x''''''''')))))))))
F(s(s(s(s(s(s(s(s(x''''''''))))))))) -> F(s(s(s(s(s(s(x'''''''')))))))
F(s(s(s(s(s(s(s(s(x''''''))))))))) -> F(s(s(s(s(s(s(x'''''')))))))
F(s(s(s(s(s(s(s(s(s(s(s(x''''''')))))))))))) -> F(s(s(s(s(s(s(s(s(s(x'''''''))))))))))
F(s(s(s(s(s(s(s(s(s(x''''''''')))))))))) -> F(s(s(s(s(s(s(s(x'''''''''))))))))
F(s(s(s(s(s(s(s(x'''''''')))))))) -> F(s(s(s(s(s(x''''''''))))))
F(s(s(s(s(s(s(s(x'''''')))))))) -> F(s(s(s(s(s(x''''''))))))
F(s(s(s(s(s(s(s(s(s(x'''''')))))))))) -> F(s(s(s(s(s(s(s(x''''''))))))))
F(s(s(s(s(s(s(s(x''''''')))))))) -> F(s(s(s(s(s(x'''''''))))))
F(s(s(s(s(s(x'''''')))))) -> F(s(s(s(x''''''))))
F(s(s(s(s(s(s(s(s(s(s(x''''''))))))))))) -> F(s(s(s(s(s(s(s(s(x'''''')))))))))
F(s(s(s(s(s(s(s(s(x'''''''))))))))) -> F(s(s(s(s(s(s(x''''''')))))))
F(s(s(s(s(s(s(s(s(x'''))))))))) -> F(s(s(s(s(s(s(x''')))))))
F(s(s(s(s(s(s(x''''''))))))) -> F(s(s(s(s(x'''''')))))
F(s(s(s(s(s(s(s(s(s(s(x'''''))))))))))) -> F(s(s(s(s(s(s(s(s(x''''')))))))))
F(s(s(s(s(s(s(x''''))))))) -> F(s(s(s(s(x'''')))))
F(s(s(s(s(s(s(s(s(x''''))))))))) -> F(s(s(s(s(s(s(x'''')))))))
F(s(s(s(s(s(s(x'''''))))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(s(s(s(s(s(s(x''''')))))))))) -> F(s(s(s(s(s(s(s(s(x''''')))))))))
F(s(s(s(s(s(s(s(x''''''')))))))) -> F(s(s(s(s(s(s(x''''''')))))))
F(s(s(s(s(s(x'''''')))))) -> F(s(s(s(s(x'''''')))))
F(s(s(s(s(s(x'''')))))) -> F(s(s(s(s(x'''')))))
F(s(s(s(s(s(s(s(x'''')))))))) -> F(s(s(s(s(s(s(x'''')))))))
F(s(s(s(s(s(x''''')))))) -> F(s(s(s(s(x''''')))))
F(s(s(s(x'''')))) -> F(s(s(x'''')))
F(s(s(s(s(s(s(x'))))))) -> F(s(f(s(f(f(x'))))))
F(s(s(s(s(x'''))))) -> F(s(f(s(x'''))))
F(s(s(s(s(x'''))))) -> F(s(s(f(x'''))))


Additionally, the following usable rules for innermost can be oriented:

f(x) -> s(x)
f(s(s(x))) -> s(f(f(x)))


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(s(x1))=  1 + x1  
  POL(f(x1))=  1 + x1  
  POL(F(x1))=  1 + x1  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 8
Dependency Graph


Dependency Pair:


Rules:


f(x) -> s(x)
f(s(s(x))) -> s(f(f(x)))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.

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