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

Innermost Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

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

Furthermore, R contains two SCCs.


   R
DPs
       →DP Problem 1
Forward Instantiation Transformation
       →DP Problem 2
FwdInst


Dependency Pairs:

MINUS(+(x, y)) -> MINUS(x)
MINUS(+(x, y)) -> MINUS(y)


Rules:


+(x, 0) -> x
+(minus(x), x) -> 0
minus(0) -> 0
minus(minus(x)) -> x
minus(+(x, y)) -> +(minus(y), minus(x))
*(x, 1) -> x
*(x, 0) -> 0
*(x, +(y, z)) -> +(*(x, y), *(x, z))
*(x, minus(y)) -> minus(*(x, y))


Strategy:

innermost




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

MINUS(+(x, y)) -> MINUS(y)
one new Dependency Pair is created:

MINUS(+(x, +(x'', y''))) -> MINUS(+(x'', y''))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
FwdInst
           →DP Problem 3
Forward Instantiation Transformation
       →DP Problem 2
FwdInst


Dependency Pairs:

MINUS(+(x, +(x'', y''))) -> MINUS(+(x'', y''))
MINUS(+(x, y)) -> MINUS(x)


Rules:


+(x, 0) -> x
+(minus(x), x) -> 0
minus(0) -> 0
minus(minus(x)) -> x
minus(+(x, y)) -> +(minus(y), minus(x))
*(x, 1) -> x
*(x, 0) -> 0
*(x, +(y, z)) -> +(*(x, y), *(x, z))
*(x, minus(y)) -> minus(*(x, y))


Strategy:

innermost




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

MINUS(+(x, y)) -> MINUS(x)
two new Dependency Pairs are created:

MINUS(+(+(x'', y''), y)) -> MINUS(+(x'', y''))
MINUS(+(+(x'', +(x'''', y'''')), y)) -> MINUS(+(x'', +(x'''', y'''')))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
FwdInst
           →DP Problem 3
FwdInst
             ...
               →DP Problem 4
Polynomial Ordering
       →DP Problem 2
FwdInst


Dependency Pairs:

MINUS(+(+(x'', +(x'''', y'''')), y)) -> MINUS(+(x'', +(x'''', y'''')))
MINUS(+(+(x'', y''), y)) -> MINUS(+(x'', y''))
MINUS(+(x, +(x'', y''))) -> MINUS(+(x'', y''))


Rules:


+(x, 0) -> x
+(minus(x), x) -> 0
minus(0) -> 0
minus(minus(x)) -> x
minus(+(x, y)) -> +(minus(y), minus(x))
*(x, 1) -> x
*(x, 0) -> 0
*(x, +(y, z)) -> +(*(x, y), *(x, z))
*(x, minus(y)) -> minus(*(x, y))


Strategy:

innermost




The following dependency pairs can be strictly oriented:

MINUS(+(+(x'', +(x'''', y'''')), y)) -> MINUS(+(x'', +(x'''', y'''')))
MINUS(+(+(x'', y''), y)) -> MINUS(+(x'', y''))
MINUS(+(x, +(x'', y''))) -> MINUS(+(x'', y''))


Additionally, the following usable rules for innermost can be oriented:

+(x, 0) -> x
+(minus(x), x) -> 0


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(0)=  0  
  POL(minus(x1))=  x1  
  POL(MINUS(x1))=  1 + x1  
  POL(+(x1, x2))=  1 + x1 + x2  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
FwdInst
           →DP Problem 3
FwdInst
             ...
               →DP Problem 5
Dependency Graph
       →DP Problem 2
FwdInst


Dependency Pair:


Rules:


+(x, 0) -> x
+(minus(x), x) -> 0
minus(0) -> 0
minus(minus(x)) -> x
minus(+(x, y)) -> +(minus(y), minus(x))
*(x, 1) -> x
*(x, 0) -> 0
*(x, +(y, z)) -> +(*(x, y), *(x, z))
*(x, minus(y)) -> minus(*(x, y))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
FwdInst
       →DP Problem 2
Forward Instantiation Transformation


Dependency Pairs:

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


Rules:


+(x, 0) -> x
+(minus(x), x) -> 0
minus(0) -> 0
minus(minus(x)) -> x
minus(+(x, y)) -> +(minus(y), minus(x))
*(x, 1) -> x
*(x, 0) -> 0
*(x, +(y, z)) -> +(*(x, y), *(x, z))
*(x, minus(y)) -> minus(*(x, y))


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
FwdInst
           →DP Problem 6
Forward Instantiation Transformation


Dependency Pairs:

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


Rules:


+(x, 0) -> x
+(minus(x), x) -> 0
minus(0) -> 0
minus(minus(x)) -> x
minus(+(x, y)) -> +(minus(y), minus(x))
*(x, 1) -> x
*(x, 0) -> 0
*(x, +(y, z)) -> +(*(x, y), *(x, z))
*(x, minus(y)) -> minus(*(x, y))


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 6
FwdInst
             ...
               →DP Problem 7
Polynomial Ordering


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''))


Rules:


+(x, 0) -> x
+(minus(x), x) -> 0
minus(0) -> 0
minus(minus(x)) -> x
minus(+(x, y)) -> +(minus(y), minus(x))
*(x, 1) -> x
*(x, 0) -> 0
*(x, +(y, z)) -> +(*(x, y), *(x, z))
*(x, minus(y)) -> minus(*(x, y))


Strategy:

innermost




The following dependency pairs can be strictly oriented:

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


Additionally, the following usable rules for innermost can be oriented:

+(x, 0) -> x
+(minus(x), x) -> 0


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(0)=  0  
  POL(*'(x1, x2))=  1 + x1 + x2  
  POL(minus(x1))=  x1  
  POL(+(x1, x2))=  1 + x1 + x2  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
FwdInst
       →DP Problem 2
FwdInst
           →DP Problem 6
FwdInst
             ...
               →DP Problem 8
Dependency Graph


Dependency Pair:


Rules:


+(x, 0) -> x
+(minus(x), x) -> 0
minus(0) -> 0
minus(minus(x)) -> x
minus(+(x, y)) -> +(minus(y), minus(x))
*(x, 1) -> x
*(x, 0) -> 0
*(x, +(y, z)) -> +(*(x, y), *(x, z))
*(x, minus(y)) -> minus(*(x, y))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.

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