Termination Proof using AProVE

Term Rewriting System R:
[x, y, z]
*(x, +(y, z)) -> +(*(x, y), *(x, z))

Innermost Termination of R to be shown.

     ↳Dependency Pair Analysis

R contains the following Dependency Pairs:

*'(x, +(y, z)) -> *'(x, y)
*'(x, +(y, z)) -> *'(x, z)

Furthermore, R contains one SCC.

     ↳DPs

       →DP Problem 1

         ↳Forward Instantiation Transformation

Dependency Pairs:

*'(x, +(y, z)) -> *'(x, z)
*'(x, +(y, z)) -> *'(x, y)

Rule:

*(x, +(y, z)) -> +(*(x, y), *(x, z))

Strategy:

innermost

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

*'(x, +(y, z)) -> *'(x, y)

one new Dependency Pair is created:

*'(x'', +(+(y'', z''), z)) -> *'(x'', +(y'', z''))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳FwdInst

           →DP Problem 2

             ↳Forward Instantiation Transformation

Dependency Pairs:

*'(x'', +(+(y'', z''), z)) -> *'(x'', +(y'', z''))
*'(x, +(y, z)) -> *'(x, z)

Rule:

*(x, +(y, z)) -> +(*(x, y), *(x, z))

Strategy:

innermost

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

*'(x, +(y, z)) -> *'(x, z)

two new Dependency Pairs are created:

*'(x'', +(y, +(y'', z''))) -> *'(x'', +(y'', z''))
*'(x', +(y, +(+(y'''', z''''), z''))) -> *'(x', +(+(y'''', z''''), z''))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳FwdInst

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 3

                 ↳Forward Instantiation Transformation

Dependency Pairs:

*'(x', +(y, +(+(y'''', z''''), z''))) -> *'(x', +(+(y'''', z''''), z''))
*'(x'', +(y, +(y'', z''))) -> *'(x'', +(y'', z''))
*'(x'', +(+(y'', z''), z)) -> *'(x'', +(y'', z''))

Rule:

*(x, +(y, z)) -> +(*(x, y), *(x, z))

Strategy:

innermost

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

*'(x'', +(+(y'', z''), z)) -> *'(x'', +(y'', z''))

three new Dependency Pairs are created:

*'(x'''', +(+(+(y'''', z''''), z''0), z)) -> *'(x'''', +(+(y'''', z''''), z''0))
*'(x'''', +(+(y''0, +(y'''', z'''')), z)) -> *'(x'''', +(y''0, +(y'''', z'''')))
*'(x'''', +(+(y''', +(+(y'''''', z''''''), z'''')), z)) -> *'(x'''', +(y''', +(+(y'''''', z''''''), z'''')))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳FwdInst

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 4

                 ↳Forward Instantiation Transformation

Dependency Pairs:

*'(x'''', +(+(y''', +(+(y'''''', z''''''), z'''')), z)) -> *'(x'''', +(y''', +(+(y'''''', z''''''), z'''')))
*'(x'''', +(+(y''0, +(y'''', z'''')), z)) -> *'(x'''', +(y''0, +(y'''', z'''')))
*'(x'''', +(+(+(y'''', z''''), z''0), z)) -> *'(x'''', +(+(y'''', z''''), z''0))
*'(x'', +(y, +(y'', z''))) -> *'(x'', +(y'', z''))
*'(x', +(y, +(+(y'''', z''''), z''))) -> *'(x', +(+(y'''', z''''), z''))

Rule:

*(x, +(y, z)) -> +(*(x, y), *(x, z))

Strategy:

innermost

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

*'(x'', +(y, +(y'', z''))) -> *'(x'', +(y'', z''))

five new Dependency Pairs are created:

*'(x'''', +(y, +(y''0, +(y'''', z'''')))) -> *'(x'''', +(y''0, +(y'''', z'''')))
*'(x'''', +(y, +(y''', +(+(y'''''', z''''''), z'''')))) -> *'(x'''', +(y''', +(+(y'''''', z''''''), z'''')))
*'(x''', +(y, +(+(+(y'''''', z''''''), z''0''), z'''))) -> *'(x''', +(+(+(y'''''', z''''''), z''0''), z'''))
*'(x''', +(y, +(+(y''0'', +(y'''''', z'''''')), z'''))) -> *'(x''', +(+(y''0'', +(y'''''', z'''''')), z'''))
*'(x''', +(y, +(+(y''''', +(+(y'''''''', z''''''''), z'''''')), z'''))) -> *'(x''', +(+(y''''', +(+(y'''''''', z''''''''), z'''''')), z'''))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳FwdInst

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 5

                 ↳Forward Instantiation Transformation

Dependency Pairs:

*'(x''', +(y, +(+(y''''', +(+(y'''''''', z''''''''), z'''''')), z'''))) -> *'(x''', +(+(y''''', +(+(y'''''''', z''''''''), z'''''')), z'''))
*'(x''', +(y, +(+(y''0'', +(y'''''', z'''''')), z'''))) -> *'(x''', +(+(y''0'', +(y'''''', z'''''')), z'''))
*'(x''', +(y, +(+(+(y'''''', z''''''), z''0''), z'''))) -> *'(x''', +(+(+(y'''''', z''''''), z''0''), z'''))
*'(x'''', +(y, +(y''', +(+(y'''''', z''''''), z'''')))) -> *'(x'''', +(y''', +(+(y'''''', z''''''), z'''')))
*'(x'''', +(y, +(y''0, +(y'''', z'''')))) -> *'(x'''', +(y''0, +(y'''', z'''')))
*'(x'''', +(+(y''0, +(y'''', z'''')), z)) -> *'(x'''', +(y''0, +(y'''', z'''')))
*'(x'''', +(+(+(y'''', z''''), z''0), z)) -> *'(x'''', +(+(y'''', z''''), z''0))
*'(x', +(y, +(+(y'''', z''''), z''))) -> *'(x', +(+(y'''', z''''), z''))
*'(x'''', +(+(y''', +(+(y'''''', z''''''), z'''')), z)) -> *'(x'''', +(y''', +(+(y'''''', z''''''), z'''')))

Rule:

*(x, +(y, z)) -> +(*(x, y), *(x, z))

Strategy:

innermost

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

*'(x', +(y, +(+(y'''', z''''), z''))) -> *'(x', +(+(y'''', z''''), z''))

nine new Dependency Pairs are created:

*'(x''', +(y, +(+(y''''0, z''''0), +(+(y'''''', z''''''), z'''0)))) -> *'(x''', +(+(y''''0, z''''0), +(+(y'''''', z''''''), z'''0)))
*'(x'', +(y, +(+(+(y'''''', z''''''), z''''0), z'''))) -> *'(x'', +(+(+(y'''''', z''''''), z''''0), z'''))
*'(x'', +(y, +(+(y''''0, +(y'''''', z'''''')), z'''))) -> *'(x'', +(+(y''''0, +(y'''''', z'''''')), z'''))
*'(x'', +(y, +(+(y'''''', +(+(y'''''''', z''''''''), z'''''')), z'''))) -> *'(x'', +(+(y'''''', +(+(y'''''''', z''''''''), z'''''')), z'''))
*'(x'', +(y, +(+(y''''0, z''''0), +(y''0'', +(y'''''', z''''''))))) -> *'(x'', +(+(y''''0, z''''0), +(y''0'', +(y'''''', z''''''))))
*'(x'', +(y, +(+(y''''0, z''''0), +(y'''''', +(+(y'''''''', z''''''''), z''''''))))) -> *'(x'', +(+(y''''0, z''''0), +(y'''''', +(+(y'''''''', z''''''''), z''''''))))
*'(x'', +(y, +(+(y''''', z''''0), +(+(+(y'''''''', z''''''''), z''0''''), z'''''')))) -> *'(x'', +(+(y''''', z''''0), +(+(+(y'''''''', z''''''''), z''0''''), z'''''')))
*'(x'', +(y, +(+(y''''', z''''0), +(+(y''0'''', +(y'''''''', z'''''''')), z'''''')))) -> *'(x'', +(+(y''''', z''''0), +(+(y''0'''', +(y'''''''', z'''''''')), z'''''')))
*'(x'', +(y, +(+(y''''', z''''0), +(+(y''''''', +(+(y'''''''''', z''''''''''), z'''''''')), z'''''')))) -> *'(x'', +(+(y''''', z''''0), +(+(y''''''', +(+(y'''''''''', z''''''''''), z'''''''')), z'''''')))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳FwdInst

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 6

                 ↳Polynomial Ordering

Dependency Pairs:

*'(x'', +(y, +(+(y''''', z''''0), +(+(y''''''', +(+(y'''''''''', z''''''''''), z'''''''')), z'''''')))) -> *'(x'', +(+(y''''', z''''0), +(+(y''''''', +(+(y'''''''''', z''''''''''), z'''''''')), z'''''')))
*'(x'', +(y, +(+(y''''', z''''0), +(+(y''0'''', +(y'''''''', z'''''''')), z'''''')))) -> *'(x'', +(+(y''''', z''''0), +(+(y''0'''', +(y'''''''', z'''''''')), z'''''')))
*'(x'', +(y, +(+(y''''', z''''0), +(+(+(y'''''''', z''''''''), z''0''''), z'''''')))) -> *'(x'', +(+(y''''', z''''0), +(+(+(y'''''''', z''''''''), z''0''''), z'''''')))
*'(x'', +(y, +(+(y''''0, z''''0), +(y'''''', +(+(y'''''''', z''''''''), z''''''))))) -> *'(x'', +(+(y''''0, z''''0), +(y'''''', +(+(y'''''''', z''''''''), z''''''))))
*'(x'', +(y, +(+(y''''0, z''''0), +(y''0'', +(y'''''', z''''''))))) -> *'(x'', +(+(y''''0, z''''0), +(y''0'', +(y'''''', z''''''))))
*'(x'', +(y, +(+(y'''''', +(+(y'''''''', z''''''''), z'''''')), z'''))) -> *'(x'', +(+(y'''''', +(+(y'''''''', z''''''''), z'''''')), z'''))
*'(x'', +(y, +(+(y''''0, +(y'''''', z'''''')), z'''))) -> *'(x'', +(+(y''''0, +(y'''''', z'''''')), z'''))
*'(x'', +(y, +(+(+(y'''''', z''''''), z''''0), z'''))) -> *'(x'', +(+(+(y'''''', z''''''), z''''0), z'''))
*'(x''', +(y, +(+(y''''0, z''''0), +(+(y'''''', z''''''), z'''0)))) -> *'(x''', +(+(y''''0, z''''0), +(+(y'''''', z''''''), z'''0)))
*'(x''', +(y, +(+(y''0'', +(y'''''', z'''''')), z'''))) -> *'(x''', +(+(y''0'', +(y'''''', z'''''')), z'''))
*'(x''', +(y, +(+(+(y'''''', z''''''), z''0''), z'''))) -> *'(x''', +(+(+(y'''''', z''''''), z''0''), z'''))
*'(x'''', +(y, +(y''', +(+(y'''''', z''''''), z'''')))) -> *'(x'''', +(y''', +(+(y'''''', z''''''), z'''')))
*'(x'''', +(y, +(y''0, +(y'''', z'''')))) -> *'(x'''', +(y''0, +(y'''', z'''')))
*'(x'''', +(+(y''', +(+(y'''''', z''''''), z'''')), z)) -> *'(x'''', +(y''', +(+(y'''''', z''''''), z'''')))
*'(x'''', +(+(y''0, +(y'''', z'''')), z)) -> *'(x'''', +(y''0, +(y'''', z'''')))
*'(x'''', +(+(+(y'''', z''''), z''0), z)) -> *'(x'''', +(+(y'''', z''''), z''0))
*'(x''', +(y, +(+(y''''', +(+(y'''''''', z''''''''), z'''''')), z'''))) -> *'(x''', +(+(y''''', +(+(y'''''''', z''''''''), z'''''')), z'''))

Rule:

*(x, +(y, z)) -> +(*(x, y), *(x, z))

Strategy:

innermost

The following dependency pairs can be strictly oriented:

*'(x'', +(y, +(+(y''''', z''''0), +(+(y''''''', +(+(y'''''''''', z''''''''''), z'''''''')), z'''''')))) -> *'(x'', +(+(y''''', z''''0), +(+(y''''''', +(+(y'''''''''', z''''''''''), z'''''''')), z'''''')))
*'(x'', +(y, +(+(y''''', z''''0), +(+(y''0'''', +(y'''''''', z'''''''')), z'''''')))) -> *'(x'', +(+(y''''', z''''0), +(+(y''0'''', +(y'''''''', z'''''''')), z'''''')))
*'(x'', +(y, +(+(y''''', z''''0), +(+(+(y'''''''', z''''''''), z''0''''), z'''''')))) -> *'(x'', +(+(y''''', z''''0), +(+(+(y'''''''', z''''''''), z''0''''), z'''''')))
*'(x'', +(y, +(+(y''''0, z''''0), +(y'''''', +(+(y'''''''', z''''''''), z''''''))))) -> *'(x'', +(+(y''''0, z''''0), +(y'''''', +(+(y'''''''', z''''''''), z''''''))))
*'(x'', +(y, +(+(y''''0, z''''0), +(y''0'', +(y'''''', z''''''))))) -> *'(x'', +(+(y''''0, z''''0), +(y''0'', +(y'''''', z''''''))))
*'(x'', +(y, +(+(y'''''', +(+(y'''''''', z''''''''), z'''''')), z'''))) -> *'(x'', +(+(y'''''', +(+(y'''''''', z''''''''), z'''''')), z'''))
*'(x'', +(y, +(+(y''''0, +(y'''''', z'''''')), z'''))) -> *'(x'', +(+(y''''0, +(y'''''', z'''''')), z'''))
*'(x'', +(y, +(+(+(y'''''', z''''''), z''''0), z'''))) -> *'(x'', +(+(+(y'''''', z''''''), z''''0), z'''))
*'(x''', +(y, +(+(y''''0, z''''0), +(+(y'''''', z''''''), z'''0)))) -> *'(x''', +(+(y''''0, z''''0), +(+(y'''''', z''''''), z'''0)))
*'(x''', +(y, +(+(y''0'', +(y'''''', z'''''')), z'''))) -> *'(x''', +(+(y''0'', +(y'''''', z'''''')), z'''))
*'(x''', +(y, +(+(+(y'''''', z''''''), z''0''), z'''))) -> *'(x''', +(+(+(y'''''', z''''''), z''0''), z'''))
*'(x'''', +(y, +(y''', +(+(y'''''', z''''''), z'''')))) -> *'(x'''', +(y''', +(+(y'''''', z''''''), z'''')))
*'(x'''', +(y, +(y''0, +(y'''', z'''')))) -> *'(x'''', +(y''0, +(y'''', z'''')))
*'(x'''', +(+(y''', +(+(y'''''', z''''''), z'''')), z)) -> *'(x'''', +(y''', +(+(y'''''', z''''''), z'''')))
*'(x'''', +(+(y''0, +(y'''', z'''')), z)) -> *'(x'''', +(y''0, +(y'''', z'''')))
*'(x'''', +(+(+(y'''', z''''), z''0), z)) -> *'(x'''', +(+(y'''', z''''), z''0))
*'(x''', +(y, +(+(y''''', +(+(y'''''''', z''''''''), z'''''')), z'''))) -> *'(x''', +(+(y''''', +(+(y'''''''', z''''''''), z'''''')), z'''))

There are no usable rules for innermost w.r.t. to the implicit AFS that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:

POL(*'(x₁, x₂)) = 1 + x₁ + x₂

POL(+(x₁, x₂)) = 1 + x₁ + x₂

resulting in one new DP problem.

     ↳DPs

       →DP Problem 1

         ↳FwdInst

           →DP Problem 2

             ↳FwdInst

...

               →DP Problem 7

                 ↳Dependency Graph

Dependency Pair:

Rule:

*(x, +(y, z)) -> +(*(x, y), *(x, z))

Strategy:

innermost

Using the Dependency Graph resulted in no new DP problems.

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

POL(*'(x₁, x₂))	= 1 + x₁ + x₂
POL(+(x₁, x₂))	= 1 + x₁ + x₂