### (0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

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

Rewrite Strategy: INNERMOST

### (1) CpxTrsToCdtProof (BOTH BOUNDS(ID, ID) transformation)

Converted Cpx (relative) TRS to CDT

### (2) Obligation:

Complexity Dependency Tuples Problem
Rules:

din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
din(der(der(z0))) → u41(din(der(z0)), z0)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
u42(dout(z0), z1, z2) → dout(z0)
Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(U22(din(der(z2)), z1, z2, z0), DIN(der(z2)))
U22(dout(z0), z1, z2, z3) → c4
U31(dout(z0), z1, z2) → c5(U32(din(der(z2)), z1, z2, z0), DIN(der(z2)))
U32(dout(z0), z1, z2, z3) → c6
U41(dout(z0), z1) → c7(U42(din(der(z0)), z1, z0), DIN(der(z0)))
U42(dout(z0), z1, z2) → c8
S tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(U22(din(der(z2)), z1, z2, z0), DIN(der(z2)))
U22(dout(z0), z1, z2, z3) → c4
U31(dout(z0), z1, z2) → c5(U32(din(der(z2)), z1, z2, z0), DIN(der(z2)))
U32(dout(z0), z1, z2, z3) → c6
U41(dout(z0), z1) → c7(U42(din(der(z0)), z1, z0), DIN(der(z0)))
U42(dout(z0), z1, z2) → c8
K tuples:none
Defined Rule Symbols:

din, u21, u22, u31, u32, u41, u42

Defined Pair Symbols:

DIN, U21, U22, U31, U32, U41, U42

Compound Symbols:

c, c1, c2, c3, c4, c5, c6, c7, c8

### (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID) transformation)

Removed 3 trailing nodes:

U22(dout(z0), z1, z2, z3) → c4
U42(dout(z0), z1, z2) → c8
U32(dout(z0), z1, z2, z3) → c6

### (4) Obligation:

Complexity Dependency Tuples Problem
Rules:

din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
din(der(der(z0))) → u41(din(der(z0)), z0)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
u42(dout(z0), z1, z2) → dout(z0)
Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(U22(din(der(z2)), z1, z2, z0), DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(U32(din(der(z2)), z1, z2, z0), DIN(der(z2)))
U41(dout(z0), z1) → c7(U42(din(der(z0)), z1, z0), DIN(der(z0)))
S tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(U22(din(der(z2)), z1, z2, z0), DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(U32(din(der(z2)), z1, z2, z0), DIN(der(z2)))
U41(dout(z0), z1) → c7(U42(din(der(z0)), z1, z0), DIN(der(z0)))
K tuples:none
Defined Rule Symbols:

din, u21, u22, u31, u32, u41, u42

Defined Pair Symbols:

DIN, U21, U31, U41

Compound Symbols:

c, c1, c2, c3, c5, c7

### (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID) transformation)

Removed 3 trailing tuple parts

### (6) Obligation:

Complexity Dependency Tuples Problem
Rules:

din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
din(der(der(z0))) → u41(din(der(z0)), z0)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
u42(dout(z0), z1, z2) → dout(z0)
Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
S tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
K tuples:none
Defined Rule Symbols:

din, u21, u22, u31, u32, u41, u42

Defined Pair Symbols:

DIN, U21, U31, U41

Compound Symbols:

c, c1, c2, c3, c5, c7

### (7) CdtRuleRemovalProof (UPPER BOUND (ADD(O(n^1))) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
We considered the (Usable) Rules:

u42(dout(z0), z1, z2) → dout(z0)
din(der(der(z0))) → u41(din(der(z0)), z0)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
And the Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
The order we found is given by the following interpretation:
Polynomial interpretation :

POL(DIN(x1)) = [2]x1
POL(U21(x1, x2, x3)) = 0
POL(U31(x1, x2, x3)) = [4]x1
POL(U41(x1, x2)) = [4]x1
POL(c(x1, x2)) = x1 + x2
POL(c1(x1, x2)) = x1 + x2
POL(c2(x1, x2)) = x1 + x2
POL(c3(x1)) = x1
POL(c5(x1)) = x1
POL(c7(x1)) = x1
POL(der(x1)) = 0
POL(din(x1)) = 0
POL(dout(x1)) = [2] + x1
POL(plus(x1, x2)) = 0
POL(times(x1, x2)) = [4]
POL(u21(x1, x2, x3)) = [2]x1
POL(u22(x1, x2, x3, x4)) = [4]x1
POL(u31(x1, x2, x3)) = [4]x1
POL(u32(x1, x2, x3, x4)) = [2] + x1 + x4
POL(u41(x1, x2)) = [4]x1
POL(u42(x1, x2, x3)) = [3] + [3]x1 + [2]x3

### (8) Obligation:

Complexity Dependency Tuples Problem
Rules:

din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
din(der(der(z0))) → u41(din(der(z0)), z0)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
u42(dout(z0), z1, z2) → dout(z0)
Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
S tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
K tuples:

U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
Defined Rule Symbols:

din, u21, u22, u31, u32, u41, u42

Defined Pair Symbols:

DIN, U21, U31, U41

Compound Symbols:

c, c1, c2, c3, c5, c7

### (9) CdtRuleRemovalProof (UPPER BOUND (ADD(O(n^1))) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
We considered the (Usable) Rules:

u42(dout(z0), z1, z2) → dout(z0)
din(der(der(z0))) → u41(din(der(z0)), z0)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
And the Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
The order we found is given by the following interpretation:
Polynomial interpretation :

POL(DIN(x1)) = [1]
POL(U21(x1, x2, x3)) = [4]x1
POL(U31(x1, x2, x3)) = [4]x1
POL(U41(x1, x2)) = x1
POL(c(x1, x2)) = x1 + x2
POL(c1(x1, x2)) = x1 + x2
POL(c2(x1, x2)) = x1 + x2
POL(c3(x1)) = x1
POL(c5(x1)) = x1
POL(c7(x1)) = x1
POL(der(x1)) = 0
POL(din(x1)) = 0
POL(dout(x1)) = [2]
POL(plus(x1, x2)) = [5]
POL(times(x1, x2)) = [3]
POL(u21(x1, x2, x3)) = 0
POL(u22(x1, x2, x3, x4)) = [4]x1
POL(u31(x1, x2, x3)) = 0
POL(u32(x1, x2, x3, x4)) = [4]x1
POL(u41(x1, x2)) = 0
POL(u42(x1, x2, x3)) = [4]x1

### (10) Obligation:

Complexity Dependency Tuples Problem
Rules:

din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
din(der(der(z0))) → u41(din(der(z0)), z0)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
u42(dout(z0), z1, z2) → dout(z0)
Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
S tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
K tuples:

U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
Defined Rule Symbols:

din, u21, u22, u31, u32, u41, u42

Defined Pair Symbols:

DIN, U21, U31, U41

Compound Symbols:

c, c1, c2, c3, c5, c7

### (11) CdtRuleRemovalProof (UPPER BOUND (ADD(O(n^2))) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
We considered the (Usable) Rules:

u42(dout(z0), z1, z2) → dout(z0)
din(der(der(z0))) → u41(din(der(z0)), z0)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
And the Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
The order we found is given by the following interpretation:
Polynomial interpretation :

POL(DIN(x1)) = x1
POL(U21(x1, x2, x3)) = [2]x1·x3 + [2]x1·x2
POL(U31(x1, x2, x3)) = [2]x1·x3
POL(U41(x1, x2)) = [2]x1
POL(c(x1, x2)) = x1 + x2
POL(c1(x1, x2)) = x1 + x2
POL(c2(x1, x2)) = x1 + x2
POL(c3(x1)) = x1
POL(c5(x1)) = x1
POL(c7(x1)) = x1
POL(der(x1)) = x1
POL(din(x1)) = 0
POL(dout(x1)) = [2] + x1
POL(plus(x1, x2)) = [2] + x1
POL(times(x1, x2)) = x1
POL(u21(x1, x2, x3)) = [2]x1 + [2]x1·x3 + [3]x12
POL(u22(x1, x2, x3, x4)) = [2] + x1 + x4 + [3]x42 + x3·x4
POL(u31(x1, x2, x3)) = [2]x1·x3 + [3]x1·x2
POL(u32(x1, x2, x3, x4)) = [2]x1 + [2]x2 + [2]x3·x4 + [2]x2·x4
POL(u41(x1, x2)) = [2]x1·x2
POL(u42(x1, x2, x3)) = [2]x1 + [3]x2 + [2]x2·x3

### (12) Obligation:

Complexity Dependency Tuples Problem
Rules:

din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
din(der(der(z0))) → u41(din(der(z0)), z0)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
u42(dout(z0), z1, z2) → dout(z0)
Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
S tuples:

DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
K tuples:

U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
Defined Rule Symbols:

din, u21, u22, u31, u32, u41, u42

Defined Pair Symbols:

DIN, U21, U31, U41

Compound Symbols:

c, c1, c2, c3, c5, c7

### (13) CdtRuleRemovalProof (UPPER BOUND (ADD(O(n^2))) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
We considered the (Usable) Rules:

u42(dout(z0), z1, z2) → dout(z0)
din(der(der(z0))) → u41(din(der(z0)), z0)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
And the Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
The order we found is given by the following interpretation:
Polynomial interpretation :

POL(DIN(x1)) = [1] + [2]x1
POL(U21(x1, x2, x3)) = [1] + [2]x1 + [2]x1·x3 + x12
POL(U31(x1, x2, x3)) = [1] + x3 + [2]x1·x3
POL(U41(x1, x2)) = [2]x12
POL(c(x1, x2)) = x1 + x2
POL(c1(x1, x2)) = x1 + x2
POL(c2(x1, x2)) = x1 + x2
POL(c3(x1)) = x1
POL(c5(x1)) = x1
POL(c7(x1)) = x1
POL(der(x1)) = x1
POL(din(x1)) = 0
POL(dout(x1)) = [1] + x1
POL(plus(x1, x2)) = [1] + x1
POL(times(x1, x2)) = [1] + x1 + x2
POL(u21(x1, x2, x3)) = [2]x1 + x1·x2
POL(u22(x1, x2, x3, x4)) = [2] + [3]x1 + x2 + x4 + [3]x12
POL(u31(x1, x2, x3)) = [2]x1 + [3]x1·x3 + [3]x1·x2
POL(u32(x1, x2, x3, x4)) = [1] + [2]x2 + [2]x3 + [2]x12
POL(u41(x1, x2)) = [2]x1·x2
POL(u42(x1, x2, x3)) = x2 + x2·x3 + [2]x12

### (14) Obligation:

Complexity Dependency Tuples Problem
Rules:

din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
din(der(der(z0))) → u41(din(der(z0)), z0)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
u42(dout(z0), z1, z2) → dout(z0)
Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
S tuples:

DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
K tuples:

U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
Defined Rule Symbols:

din, u21, u22, u31, u32, u41, u42

Defined Pair Symbols:

DIN, U21, U31, U41

Compound Symbols:

c, c1, c2, c3, c5, c7

### (15) CdtRuleRemovalProof (UPPER BOUND (ADD(O(n^2))) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
We considered the (Usable) Rules:

u42(dout(z0), z1, z2) → dout(z0)
din(der(der(z0))) → u41(din(der(z0)), z0)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
And the Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
The order we found is given by the following interpretation:
Polynomial interpretation :

POL(DIN(x1)) = [2] + x1
POL(U21(x1, x2, x3)) = x1·x3 + x12
POL(U31(x1, x2, x3)) = x3 + [2]x12
POL(U41(x1, x2)) = [2]x12
POL(c(x1, x2)) = x1 + x2
POL(c1(x1, x2)) = x1 + x2
POL(c2(x1, x2)) = x1 + x2
POL(c3(x1)) = x1
POL(c5(x1)) = x1
POL(c7(x1)) = x1
POL(der(x1)) = [2] + x1
POL(din(x1)) = 0
POL(dout(x1)) = [2] + x1
POL(plus(x1, x2)) = x1
POL(times(x1, x2)) = x1 + x2
POL(u21(x1, x2, x3)) = [2]x1 + [2]x1·x3 + [3]x12 + [2]x1·x2
POL(u22(x1, x2, x3, x4)) = [3] + [3]x1 + [3]x2 + [3]x3 + x4 + x3·x4 + x2·x4
POL(u31(x1, x2, x3)) = [2]x1·x3 + [3]x12 + [2]x1·x2
POL(u32(x1, x2, x3, x4)) = [2]x1 + [3]x2 + [3]x3 + [3]x4 + x3·x4 + [2]x2·x4 + [3]x1·x4 + [3]x12 + [2]x1·x2 + [3]x1·x3
POL(u41(x1, x2)) = [2]x1·x2 + [2]x12
POL(u42(x1, x2, x3)) = [1] + [3]x2 + [3]x3 + x32 + x2·x3 + x12

### (16) Obligation:

Complexity Dependency Tuples Problem
Rules:

din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1)
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1)
din(der(der(z0))) → u41(din(der(z0)), z0)
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0)
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0)
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3)))
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0)
u42(dout(z0), z1, z2) → dout(z0)
Tuples:

DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
S tuples:none
K tuples:

U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
U41(dout(z0), z1) → c7(DIN(der(z0)))
U21(dout(z0), z1, z2) → c3(DIN(der(z2)))
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0)))
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
Defined Rule Symbols:

din, u21, u22, u31, u32, u41, u42

Defined Pair Symbols:

DIN, U21, U31, U41

Compound Symbols:

c, c1, c2, c3, c5, c7

### (17) SIsEmptyProof (BOTH BOUNDS(ID, ID) transformation)

The set S is empty