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)

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


Strategy:

innermost




The following dependency pair can be strictly oriented:

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


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

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)
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u42(dout(DDX), X, DX) -> dout(DDX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))


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(din(x1))=  0  
  POL(u21(x1, x2, x3))=  0  
  POL(u41(x1, x2))=  0  
  POL(dout(x1))=  1  
  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(u31(x1, x2, x3))=  0  
  POL(times(x1, x2))=  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)


Strategy:

innermost




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)


Strategy:

innermost




The following dependency pairs can be strictly oriented:

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


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

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)
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u42(dout(DDX), X, DX) -> dout(DDX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(plus(x1, x2))=  x1 + x2  
  POL(U31(x1, x2, x3))=  x3  
  POL(u22(x1, x2, x3, x4))=  0  
  POL(din(x1))=  0  
  POL(u21(x1, x2, x3))=  0  
  POL(u41(x1, x2))=  0  
  POL(dout(x1))=  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(times(x1, x2))=  1 + x1 + x2  
  POL(u31(x1, x2, x3))=  0  
  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:

U31(dout(DX), X, Y) -> DIN(der(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)


Strategy:

innermost




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


Strategy:

innermost




The following dependency pair can be strictly oriented:

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


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

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)
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u42(dout(DDX), X, DX) -> dout(DDX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))


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

resulting in one new DP problem.



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


Dependency Pairs:

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)


Strategy:

innermost




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)


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

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)
u41(dout(DX), X) -> u42(din(der(DX)), X, DX)
u31(dout(DX), X, Y) -> u32(din(der(Y)), X, Y, DX)
u21(dout(DX), X, Y) -> u22(din(der(Y)), X, Y, DX)
u42(dout(DDX), X, DX) -> dout(DDX)
u32(dout(DY), X, Y, DX) -> dout(plus(times(X, DY), times(Y, DX)))
u22(dout(DY), X, Y, DX) -> dout(plus(DX, DY))


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(plus(x1, x2))=  1 + x1 + x2  
  POL(u22(x1, x2, x3, x4))=  0  
  POL(din(x1))=  0  
  POL(u21(x1, x2, x3))=  0  
  POL(u41(x1, x2))=  0  
  POL(dout(x1))=  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(times(x1, x2))=  0  
  POL(u31(x1, x2, x3))=  0  
  POL(der(x1))=  x1  

resulting in one new DP problem.



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


Dependency Pair:

U21(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)


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.

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