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