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

Innermost Termination of R to be shown.

`   R`
`     ↳Dependency Pair Analysis`

R contains the following Dependency Pairs:

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

Furthermore, R contains one SCC.

`   R`
`     ↳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:

`   R`
`     ↳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:

`   R`
`     ↳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:

`   R`
`     ↳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:

`   R`
`     ↳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:

`   R`
`     ↳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(*'(x1, x2)) =  1 + x1 + x2 POL(+(x1, x2)) =  1 + x1 + x2

resulting in one new DP problem.

`   R`
`     ↳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