Term Rewriting System R:
[X, Y, DX, DY, DDX]
din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) -> dout(DDX)

Termination of R to be shown. 



   R
     ↳Dependency Pair Analysis



R contains the following Dependency Pairs:

DIN(der(plus(X, Y))) -> U21(din(der(X)), X, Y)
DIN(der(plus(X, Y))) -> DIN(der(X))
DIN(der(times(X, Y))) -> U31(din(der(X)), X, Y)
DIN(der(times(X, Y))) -> DIN(der(X))
DIN(der(der(X))) -> U41(din(der(X)), X)
DIN(der(der(X))) -> DIN(der(X))
U21(dout(DX), X, Y) -> U22(din(der(Y)), X, Y, DX)
U21(dout(DX), X, Y) -> DIN(der(Y))
U31(dout(DX), X, Y) -> U32(din(der(Y)), X, Y, DX)
U31(dout(DX), X, Y) -> DIN(der(Y))
U41(dout(DX), X) -> U42(din(der(DX)), X, DX)
U41(dout(DX), X) -> DIN(der(DX))

Furthermore, R contains one SCC. 


   R
     ↳DPs
       →DP Problem 1
         ↳Polynomial Ordering


Dependency Pairs:

DIN(der(der(X))) -> DIN(der(X))
U41(dout(DX), X) -> DIN(der(DX))
DIN(der(der(X))) -> U41(din(der(X)), X)
DIN(der(times(X, Y))) -> DIN(der(X))
U31(dout(DX), X, Y) -> DIN(der(Y))
DIN(der(times(X, Y))) -> U31(din(der(X)), X, Y)
DIN(der(plus(X, Y))) -> DIN(der(X))
U21(dout(DX), X, Y) -> DIN(der(Y))
DIN(der(plus(X, Y))) -> U21(din(der(X)), X, Y)


Rules:


din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) -> dout(DDX)





The following dependency pair can be strictly oriented:

U41(dout(DX), X) -> DIN(der(DX))


Additionally, the following usable rules w.r.t. to the implicit AFS can be oriented:

u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u42(dout(DDX), X, DX) -> dout(DDX)


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(plus(x1, x2))=  0  
  POL(U31(x1, x2, x3))=  0  
  POL(u22(x1, x2, x3, x4))=  x1  
  POL(dout(x1))=  1  
  POL(din(x1))=  0  
  POL(u21(x1, x2, x3))=  0  
  POL(u41(x1, x2))=  0  
  POL(DIN(x1))=  0  
  POL(u32(x1, x2, x3, x4))=  x1  
  POL(u42(x1, x2, x3))=  x1  
  POL(U41(x1, x2))=  x1  
  POL(U21(x1, x2, x3))=  0  
  POL(times(x1, x2))=  0  
  POL(u31(x1, x2, x3))=  0  
  POL(der(x1))=  0  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳Polo
           →DP Problem 2
             ↳Dependency Graph


Dependency Pairs:

DIN(der(der(X))) -> DIN(der(X))
DIN(der(der(X))) -> U41(din(der(X)), X)
DIN(der(times(X, Y))) -> DIN(der(X))
U31(dout(DX), X, Y) -> DIN(der(Y))
DIN(der(times(X, Y))) -> U31(din(der(X)), X, Y)
DIN(der(plus(X, Y))) -> DIN(der(X))
U21(dout(DX), X, Y) -> DIN(der(Y))
DIN(der(plus(X, Y))) -> U21(din(der(X)), X, Y)


Rules:


din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) -> dout(DDX)





Using the Dependency Graph the DP problem was split into 1 DP problems.


   R
     ↳DPs
       →DP Problem 1
         ↳Polo
           →DP Problem 2
             ↳DGraph
             ...
               →DP Problem 3
                 ↳Polynomial Ordering


Dependency Pairs:

DIN(der(times(X, Y))) -> DIN(der(X))
U31(dout(DX), X, Y) -> DIN(der(Y))
DIN(der(times(X, Y))) -> U31(din(der(X)), X, Y)
DIN(der(plus(X, Y))) -> DIN(der(X))
U21(dout(DX), X, Y) -> DIN(der(Y))
DIN(der(plus(X, Y))) -> U21(din(der(X)), X, Y)
DIN(der(der(X))) -> DIN(der(X))


Rules:


din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) -> dout(DDX)





The following dependency pairs can be strictly oriented:

DIN(der(plus(X, Y))) -> DIN(der(X))
DIN(der(plus(X, Y))) -> U21(din(der(X)), X, Y)


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

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(plus(x1, x2))=  1 + x1 + x2  
  POL(U31(x1, x2, x3))=  x3  
  POL(u22(x1, x2, x3, x4))=  0  
  POL(dout(x1))=  0  
  POL(din(x1))=  0  
  POL(u21(x1, x2, x3))=  0  
  POL(u41(x1, x2))=  0  
  POL(DIN(x1))=  x1  
  POL(u32(x1, x2, x3, x4))=  0  
  POL(u42(x1, x2, x3))=  0  
  POL(U21(x1, x2, x3))=  x3  
  POL(u31(x1, x2, x3))=  0  
  POL(times(x1, x2))=  x1 + x2  
  POL(der(x1))=  x1  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳Polo
           →DP Problem 2
             ↳DGraph
             ...
               →DP Problem 4
                 ↳Dependency Graph


Dependency Pairs:

DIN(der(times(X, Y))) -> DIN(der(X))
U31(dout(DX), X, Y) -> DIN(der(Y))
DIN(der(times(X, Y))) -> U31(din(der(X)), X, Y)
U21(dout(DX), X, Y) -> DIN(der(Y))
DIN(der(der(X))) -> DIN(der(X))


Rules:


din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) -> dout(DDX)





Using the Dependency Graph the DP problem was split into 1 DP problems.


   R
     ↳DPs
       →DP Problem 1
         ↳Polo
           →DP Problem 2
             ↳DGraph
             ...
               →DP Problem 5
                 ↳Polynomial Ordering


Dependency Pairs:

DIN(der(der(X))) -> DIN(der(X))
U31(dout(DX), X, Y) -> DIN(der(Y))
DIN(der(times(X, Y))) -> U31(din(der(X)), X, Y)
DIN(der(times(X, Y))) -> DIN(der(X))


Rules:


din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) -> dout(DDX)





The following dependency pairs can be strictly oriented:

DIN(der(times(X, Y))) -> U31(din(der(X)), X, Y)
DIN(der(times(X, Y))) -> DIN(der(X))


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

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(plus(x1, x2))=  0  
  POL(U31(x1, x2, x3))=  x3  
  POL(u22(x1, x2, x3, x4))=  0  
  POL(dout(x1))=  0  
  POL(din(x1))=  0  
  POL(u21(x1, x2, x3))=  0  
  POL(u41(x1, x2))=  0  
  POL(DIN(x1))=  x1  
  POL(u32(x1, x2, x3, x4))=  0  
  POL(u42(x1, x2, x3))=  0  
  POL(u31(x1, x2, x3))=  0  
  POL(times(x1, x2))=  1 + x1 + x2  
  POL(der(x1))=  x1  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳Polo
           →DP Problem 2
             ↳DGraph
             ...
               →DP Problem 6
                 ↳Dependency Graph


Dependency Pairs:

DIN(der(der(X))) -> DIN(der(X))
U31(dout(DX), X, Y) -> DIN(der(Y))


Rules:


din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) -> dout(DDX)





Using the Dependency Graph the DP problem was split into 1 DP problems.


   R
     ↳DPs
       →DP Problem 1
         ↳Polo
           →DP Problem 2
             ↳DGraph
             ...
               →DP Problem 7
                 ↳Forward Instantiation Transformation


Dependency Pair:

DIN(der(der(X))) -> DIN(der(X))


Rules:


din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) -> dout(DDX)





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

DIN(der(der(X))) -> DIN(der(X))
one new Dependency Pair is created:

DIN(der(der(der(X'')))) -> DIN(der(der(X'')))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳Polo
           →DP Problem 2
             ↳DGraph
             ...
               →DP Problem 8
                 ↳Forward Instantiation Transformation


Dependency Pair:

DIN(der(der(der(X'')))) -> DIN(der(der(X'')))


Rules:


din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) -> dout(DDX)





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

DIN(der(der(der(X'')))) -> DIN(der(der(X'')))
one new Dependency Pair is created:

DIN(der(der(der(der(X''''))))) -> DIN(der(der(der(X''''))))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳Polo
           →DP Problem 2
             ↳DGraph
             ...
               →DP Problem 9
                 ↳Polynomial Ordering


Dependency Pair:

DIN(der(der(der(der(X''''))))) -> DIN(der(der(der(X''''))))


Rules:


din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) -> dout(DDX)





The following dependency pair can be strictly oriented:

DIN(der(der(der(der(X''''))))) -> DIN(der(der(der(X''''))))


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

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(DIN(x1))=  1 + x1  
  POL(der(x1))=  1 + x1  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳Polo
           →DP Problem 2
             ↳DGraph
             ...
               →DP Problem 10
                 ↳Dependency Graph


Dependency Pair:


Rules:


din(der(plus(X, Y))) -> u21(din(der(X)), X, Y)
din(der(times(X, Y))) -> u31(din(der(X)), X, Y)
din(der(der(X))) -> u41(din(der(X)), X)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) -> dout(DDX)





Using the Dependency Graph resulted in no new DP problems.

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