Termination Proof using AProVE

Term Rewriting System R:
[x, y]
f(g(x)) -> g(f(f(x)))
f(h(x)) -> h(g(x))
f'(s(x), y, y) -> f'(y, x, s(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)
F'(s(x), y, y) -> F'(y, x, s(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))
f'(s(x), y, y) -> f'(y, x, s(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))
f'(s(x), y, y) -> f'(y, x, s(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))
f'(s(x), y, y) -> f'(y, x, s(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))
f'(s(x), y, y) -> f'(y, x, s(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))
f'(s(x), y, y) -> f'(y, x, s(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))
f'(s(x), y, y) -> f'(y, x, s(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))
f'(s(x), y, y) -> f'(y, x, s(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))
f'(s(x), y, y) -> f'(y, x, s(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 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))
f'(s(x), y, y) -> f'(y, x, s(x))

Strategy:

innermost

Using the Dependency Graph resulted in no new DP problems.

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