Termination Proof using AProVE

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

Innermost Termination of R to be shown.

     ↳Dependency Pair Analysis

R contains the following Dependency Pairs:

F(g(X)) -> F(f(X))
F(g(X)) -> F(X)

Furthermore, R contains one SCC.

     ↳DPs

       →DP Problem 1

         ↳Narrowing Transformation

Dependency Pairs:

F(g(X)) -> F(X)
F(g(X)) -> F(f(X))

Rules:

f(g(X)) -> g(f(f(X)))
f(h(X)) -> h(g(X))

Strategy:

innermost

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

F(g(X)) -> F(f(X))

two new Dependency Pairs are created:

F(g(g(X''))) -> F(g(f(f(X''))))
F(g(h(X''))) -> F(h(g(X'')))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳Forward Instantiation Transformation

Dependency Pairs:

F(g(g(X''))) -> F(g(f(f(X''))))
F(g(X)) -> F(X)

Rules:

f(g(X)) -> g(f(f(X)))
f(h(X)) -> h(g(X))

Strategy:

innermost

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

F(g(X)) -> F(X)

two new Dependency Pairs are created:

F(g(g(X''))) -> F(g(X''))
F(g(g(g(X'''')))) -> F(g(g(X'''')))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 3

                 ↳Narrowing Transformation

Dependency Pairs:

F(g(g(g(X'''')))) -> F(g(g(X'''')))
F(g(g(X''))) -> F(g(X''))
F(g(g(X''))) -> F(g(f(f(X''))))

Rules:

f(g(X)) -> g(f(f(X)))
f(h(X)) -> h(g(X))

Strategy:

innermost

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

F(g(g(X''))) -> F(g(f(f(X''))))

two new Dependency Pairs are created:

F(g(g(g(X')))) -> F(g(f(g(f(f(X'))))))
F(g(g(h(X')))) -> F(g(f(h(g(X')))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 4

                 ↳Rewriting Transformation

Dependency Pairs:

F(g(g(h(X')))) -> F(g(f(h(g(X')))))
F(g(g(g(X')))) -> F(g(f(g(f(f(X'))))))
F(g(g(X''))) -> F(g(X''))
F(g(g(g(X'''')))) -> F(g(g(X'''')))

Rules:

f(g(X)) -> g(f(f(X)))
f(h(X)) -> h(g(X))

Strategy:

innermost

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

F(g(g(g(X')))) -> F(g(f(g(f(f(X'))))))

one new Dependency Pair is created:

F(g(g(g(X')))) -> F(g(g(f(f(f(f(X')))))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 5

                 ↳Rewriting Transformation

Dependency Pairs:

F(g(g(g(X')))) -> F(g(g(f(f(f(f(X')))))))
F(g(g(g(X'''')))) -> F(g(g(X'''')))
F(g(g(X''))) -> F(g(X''))
F(g(g(h(X')))) -> F(g(f(h(g(X')))))

Rules:

f(g(X)) -> g(f(f(X)))
f(h(X)) -> h(g(X))

Strategy:

innermost

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

F(g(g(h(X')))) -> F(g(f(h(g(X')))))

one new Dependency Pair is created:

F(g(g(h(X')))) -> F(g(h(g(g(X')))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 6

                 ↳Forward Instantiation Transformation

Dependency Pairs:

F(g(g(g(X'''')))) -> F(g(g(X'''')))
F(g(g(X''))) -> F(g(X''))
F(g(g(g(X')))) -> F(g(g(f(f(f(f(X')))))))

Rules:

f(g(X)) -> g(f(f(X)))
f(h(X)) -> h(g(X))

Strategy:

innermost

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

F(g(g(X''))) -> F(g(X''))

three new Dependency Pairs are created:

F(g(g(g(X'''')))) -> F(g(g(X'''')))
F(g(g(g(g(X''''''))))) -> F(g(g(g(X''''''))))
F(g(g(g(g(X''''))))) -> F(g(g(g(X''''))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 7

                 ↳Forward Instantiation Transformation

Dependency Pairs:

F(g(g(g(g(X''''))))) -> F(g(g(g(X''''))))
F(g(g(g(g(X''''''))))) -> F(g(g(g(X''''''))))
F(g(g(g(X'''')))) -> F(g(g(X'''')))
F(g(g(g(X')))) -> F(g(g(f(f(f(f(X')))))))
F(g(g(g(X'''')))) -> F(g(g(X'''')))

Rules:

f(g(X)) -> g(f(f(X)))
f(h(X)) -> h(g(X))

Strategy:

innermost

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

F(g(g(g(X'''')))) -> F(g(g(X'''')))

four new Dependency Pairs are created:

F(g(g(g(g(X''''''))))) -> F(g(g(g(X''''''))))
F(g(g(g(g(X'''))))) -> F(g(g(g(X'''))))
F(g(g(g(g(g(X'''''''')))))) -> F(g(g(g(g(X'''''''')))))
F(g(g(g(g(g(X'''''')))))) -> F(g(g(g(g(X'''''')))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 8

                 ↳Argument Filtering and Ordering

Dependency Pairs:

F(g(g(g(g(g(X'''''')))))) -> F(g(g(g(g(X'''''')))))
F(g(g(g(g(g(X'''''''')))))) -> F(g(g(g(g(X'''''''')))))
F(g(g(g(g(X'''))))) -> F(g(g(g(X'''))))
F(g(g(g(g(X''''''))))) -> F(g(g(g(X''''''))))
F(g(g(g(g(X''''''))))) -> F(g(g(g(X''''''))))
F(g(g(g(X'''')))) -> F(g(g(X'''')))
F(g(g(g(X')))) -> F(g(g(f(f(f(f(X')))))))
F(g(g(g(g(X''''))))) -> F(g(g(g(X''''))))

Rules:

f(g(X)) -> g(f(f(X)))
f(h(X)) -> h(g(X))

Strategy:

innermost

The following dependency pairs can be strictly oriented:

F(g(g(g(g(g(X'''''')))))) -> F(g(g(g(g(X'''''')))))
F(g(g(g(g(g(X'''''''')))))) -> F(g(g(g(g(X'''''''')))))
F(g(g(g(g(X'''))))) -> F(g(g(g(X'''))))
F(g(g(g(g(X''''''))))) -> F(g(g(g(X''''''))))
F(g(g(g(X'''')))) -> F(g(g(X'''')))
F(g(g(g(X')))) -> F(g(g(f(f(f(f(X')))))))
F(g(g(g(g(X''''))))) -> F(g(g(g(X''''))))

The following usable rules for innermost w.r.t. to the AFS can be oriented:

f(g(X)) -> g(f(f(X)))
f(h(X)) -> h(g(X))

Used ordering: Homeomorphic Embedding Order with EMB
resulting in one new DP problem.
Used Argument Filtering System:

F(x₁) -> F(x₁)
g(x₁) -> g(x₁)
f(x₁) -> x₁
h(x₁) -> h

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 9

                 ↳Dependency Graph

Dependency Pair:

Rules:

f(g(X)) -> g(f(f(X)))
f(h(X)) -> h(g(X))

Strategy:

innermost

Using the Dependency Graph resulted in no new DP problems.

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