YES(O(1), O(n^2)) 12.84/3.77 YES(O(1), O(n^2)) 12.84/3.80 12.84/3.80 12.84/3.80
12.84/3.80 12.84/3.800 CpxTRS12.84/3.80
↳1 CpxTrsToCdtProof (BOTH BOUNDS(ID, ID))12.84/3.80
↳2 CdtProblem12.84/3.80
↳3 CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))12.84/3.80
↳4 CdtProblem12.84/3.80
↳5 CdtPolyRedPairProof (UPPER BOUND (ADD(O(n^1))))12.84/3.80
↳6 CdtProblem12.84/3.80
↳7 CdtPolyRedPairProof (UPPER BOUND (ADD(O(n^1))))12.84/3.80
↳8 CdtProblem12.84/3.80
↳9 CdtPolyRedPairProof (UPPER BOUND (ADD(O(n^2))))12.84/3.80
↳10 CdtProblem12.84/3.80
↳11 SIsEmptyProof (BOTH BOUNDS(ID, ID))12.84/3.80
↳12 BOUNDS(O(1), O(1))12.84/3.80
din(der(plus(X, Y))) → u21(din(der(X)), X, Y) 12.84/3.80
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX) 12.84/3.80
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY)) 12.84/3.80
din(der(times(X, Y))) → u31(din(der(X)), X, Y) 12.84/3.80
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX) 12.84/3.80
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX))) 12.84/3.80
din(der(der(X))) → u41(din(der(X)), X) 12.84/3.80
u41(dout(DX), X) → u42(din(der(DX)), X, DX) 12.84/3.80
u42(dout(DDX), X, DX) → dout(DDX)
Tuples:
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1) 12.84/3.80
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1) 12.84/3.80
din(der(der(z0))) → u41(din(der(z0)), z0) 12.84/3.80
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0) 12.84/3.80
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0)) 12.84/3.80
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0) 12.84/3.80
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3))) 12.84/3.80
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0) 12.84/3.80
u42(dout(z0), z1, z2) → dout(z0)
S tuples:
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 12.84/3.80
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 12.84/3.80
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0))) 12.84/3.80
U21(dout(z0), z1, z2) → c3(U22(din(der(z2)), z1, z2, z0), DIN(der(z2))) 12.84/3.80
U31(dout(z0), z1, z2) → c5(U32(din(der(z2)), z1, z2, z0), DIN(der(z2))) 12.84/3.80
U41(dout(z0), z1) → c7(U42(din(der(z0)), z1, z0), DIN(der(z0)))
K tuples:none
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 12.84/3.80
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 12.84/3.80
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0))) 12.84/3.80
U21(dout(z0), z1, z2) → c3(U22(din(der(z2)), z1, z2, z0), DIN(der(z2))) 12.84/3.80
U31(dout(z0), z1, z2) → c5(U32(din(der(z2)), z1, z2, z0), DIN(der(z2))) 12.84/3.80
U41(dout(z0), z1) → c7(U42(din(der(z0)), z1, z0), DIN(der(z0)))
din, u21, u22, u31, u32, u41, u42
DIN, U21, U31, U41
c, c1, c2, c3, c5, c7
Tuples:
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1) 13.40/3.83
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1) 13.40/3.83
din(der(der(z0))) → u41(din(der(z0)), z0) 13.40/3.83
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0) 13.40/3.83
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0)) 13.40/3.83
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0) 13.40/3.83
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3))) 13.40/3.83
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0) 13.40/3.83
u42(dout(z0), z1, z2) → dout(z0)
S tuples:
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0))) 13.40/3.83
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U31(dout(z0), z1, z2) → c5(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0)))
K tuples:none
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0))) 13.40/3.83
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U31(dout(z0), z1, z2) → c5(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0)))
din, u21, u22, u31, u32, u41, u42
DIN, U21, U31, U41
c, c1, c2, c3, c5, c7
We considered the (Usable) Rules:
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0)))
And the Tuples:
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1) 13.40/3.83
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1) 13.40/3.83
din(der(der(z0))) → u41(din(der(z0)), z0) 13.40/3.83
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0) 13.40/3.83
u42(dout(z0), z1, z2) → dout(z0) 13.40/3.83
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0) 13.40/3.83
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3))) 13.40/3.83
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0) 13.40/3.83
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
The order we found is given by the following interpretation:
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0))) 13.40/3.83
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U31(dout(z0), z1, z2) → c5(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0)))
POL(DIN(x1)) = 0 13.40/3.83
POL(U21(x1, x2, x3)) = [5]x1 13.40/3.83
POL(U31(x1, x2, x3)) = 0 13.40/3.83
POL(U41(x1, x2)) = [3]x1 13.40/3.83
POL(c(x1, x2)) = x1 + x2 13.40/3.83
POL(c1(x1, x2)) = x1 + x2 13.40/3.83
POL(c2(x1, x2)) = x1 + x2 13.40/3.83
POL(c3(x1)) = x1 13.40/3.83
POL(c5(x1)) = x1 13.40/3.83
POL(c7(x1)) = x1 13.40/3.83
POL(der(x1)) = 0 13.40/3.83
POL(din(x1)) = 0 13.40/3.83
POL(dout(x1)) = [2] + x1 13.40/3.83
POL(plus(x1, x2)) = 0 13.40/3.83
POL(times(x1, x2)) = 0 13.40/3.83
POL(u21(x1, x2, x3)) = 0 13.40/3.83
POL(u22(x1, x2, x3, x4)) = [4]x1 13.40/3.83
POL(u31(x1, x2, x3)) = x1 13.40/3.83
POL(u32(x1, x2, x3, x4)) = [1] + x1 13.40/3.83
POL(u41(x1, x2)) = 0 13.40/3.83
POL(u42(x1, x2, x3)) = [4]x1
Tuples:
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1) 13.40/3.83
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1) 13.40/3.83
din(der(der(z0))) → u41(din(der(z0)), z0) 13.40/3.83
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0) 13.40/3.83
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0)) 13.40/3.83
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0) 13.40/3.83
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3))) 13.40/3.83
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0) 13.40/3.83
u42(dout(z0), z1, z2) → dout(z0)
S tuples:
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0))) 13.40/3.83
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U31(dout(z0), z1, z2) → c5(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0)))
K tuples:
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0))) 13.40/3.83
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
Defined Rule Symbols:
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0)))
din, u21, u22, u31, u32, u41, u42
DIN, U21, U31, U41
c, c1, c2, c3, c5, c7
We considered the (Usable) Rules:
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
And the Tuples:
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1) 13.40/3.83
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1) 13.40/3.83
din(der(der(z0))) → u41(din(der(z0)), z0) 13.40/3.83
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0) 13.40/3.83
u42(dout(z0), z1, z2) → dout(z0) 13.40/3.83
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0) 13.40/3.83
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3))) 13.40/3.83
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0) 13.40/3.83
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
The order we found is given by the following interpretation:
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0))) 13.40/3.83
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U31(dout(z0), z1, z2) → c5(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0)))
POL(DIN(x1)) = [3] 13.40/3.83
POL(U21(x1, x2, x3)) = [4]x1 13.40/3.83
POL(U31(x1, x2, x3)) = [2]x1 13.40/3.83
POL(U41(x1, x2)) = [2]x1 13.40/3.83
POL(c(x1, x2)) = x1 + x2 13.40/3.83
POL(c1(x1, x2)) = x1 + x2 13.40/3.83
POL(c2(x1, x2)) = x1 + x2 13.40/3.83
POL(c3(x1)) = x1 13.40/3.83
POL(c5(x1)) = x1 13.40/3.83
POL(c7(x1)) = x1 13.40/3.83
POL(der(x1)) = 0 13.40/3.83
POL(din(x1)) = 0 13.40/3.83
POL(dout(x1)) = [2] 13.40/3.83
POL(plus(x1, x2)) = 0 13.40/3.83
POL(times(x1, x2)) = 0 13.40/3.83
POL(u21(x1, x2, x3)) = [4]x1 13.40/3.83
POL(u22(x1, x2, x3, x4)) = [4] + [4]x1 13.40/3.83
POL(u31(x1, x2, x3)) = x1 13.40/3.83
POL(u32(x1, x2, x3, x4)) = x1 13.40/3.83
POL(u41(x1, x2)) = 0 13.40/3.83
POL(u42(x1, x2, x3)) = x1
Tuples:
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1) 13.40/3.83
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1) 13.40/3.83
din(der(der(z0))) → u41(din(der(z0)), z0) 13.40/3.83
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0) 13.40/3.83
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0)) 13.40/3.83
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0) 13.40/3.83
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3))) 13.40/3.83
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0) 13.40/3.83
u42(dout(z0), z1, z2) → dout(z0)
S tuples:
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0))) 13.40/3.83
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U31(dout(z0), z1, z2) → c5(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0)))
K tuples:
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
Defined Rule Symbols:
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0))) 13.40/3.83
U31(dout(z0), z1, z2) → c5(DIN(der(z2)))
din, u21, u22, u31, u32, u41, u42
DIN, U21, U31, U41
c, c1, c2, c3, c5, c7
We considered the (Usable) Rules:
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
And the Tuples:
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1) 13.40/3.83
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1) 13.40/3.83
din(der(der(z0))) → u41(din(der(z0)), z0) 13.40/3.83
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0) 13.40/3.83
u42(dout(z0), z1, z2) → dout(z0) 13.40/3.83
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0) 13.40/3.83
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3))) 13.40/3.83
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0) 13.40/3.83
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0))
The order we found is given by the following interpretation:
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0))) 13.40/3.83
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U31(dout(z0), z1, z2) → c5(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0)))
POL(DIN(x1)) = x12 13.40/3.83
POL(U21(x1, x2, x3)) = [3]x1 + [2]x2 + [3]x3 + x32 + [2]x2·x3 + [2]x1·x3 + x12 13.40/3.83
POL(U31(x1, x2, x3)) = [3]x1 + [2]x3 + x32 + [2]x2·x3 + [2]x1·x3 + x12 13.40/3.83
POL(U41(x1, x2)) = [2] + x1 + [2]x2 + [3]x12 13.40/3.83
POL(c(x1, x2)) = x1 + x2 13.40/3.83
POL(c1(x1, x2)) = x1 + x2 13.40/3.83
POL(c2(x1, x2)) = x1 + x2 13.40/3.83
POL(c3(x1)) = x1 13.40/3.83
POL(c5(x1)) = x1 13.40/3.83
POL(c7(x1)) = x1 13.40/3.83
POL(der(x1)) = [3] + x1 13.40/3.83
POL(din(x1)) = 0 13.40/3.83
POL(dout(x1)) = [2] + x1 13.40/3.83
POL(plus(x1, x2)) = [2] + x1 + x2 13.40/3.83
POL(times(x1, x2)) = [1] + x1 + x2 13.40/3.83
POL(u21(x1, x2, x3)) = x1 + x1·x3 13.40/3.83
POL(u22(x1, x2, x3, x4)) = x1 + x1·x4 + [2]x12 13.40/3.83
POL(u31(x1, x2, x3)) = [2]x1·x3 + x12 13.40/3.83
POL(u32(x1, x2, x3, x4)) = [2]x3 + x42 + [2]x3·x4 + x1·x4 + [2]x12 + [2]x1·x2 13.40/3.83
POL(u41(x1, x2)) = [2]x1·x2 + [2]x12 13.40/3.83
POL(u42(x1, x2, x3)) = [2]x2·x3 + [2]x12
Tuples:
din(der(plus(z0, z1))) → u21(din(der(z0)), z0, z1) 13.40/3.83
din(der(times(z0, z1))) → u31(din(der(z0)), z0, z1) 13.40/3.83
din(der(der(z0))) → u41(din(der(z0)), z0) 13.40/3.83
u21(dout(z0), z1, z2) → u22(din(der(z2)), z1, z2, z0) 13.40/3.83
u22(dout(z0), z1, z2, z3) → dout(plus(z3, z0)) 13.40/3.83
u31(dout(z0), z1, z2) → u32(din(der(z2)), z1, z2, z0) 13.40/3.83
u32(dout(z0), z1, z2, z3) → dout(plus(times(z1, z0), times(z2, z3))) 13.40/3.83
u41(dout(z0), z1) → u42(din(der(z0)), z1, z0) 13.40/3.83
u42(dout(z0), z1, z2) → dout(z0)
S tuples:none
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0))) 13.40/3.83
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U31(dout(z0), z1, z2) → c5(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0)))
Defined Rule Symbols:
U21(dout(z0), z1, z2) → c3(DIN(der(z2))) 13.40/3.83
U41(dout(z0), z1) → c7(DIN(der(z0))) 13.40/3.83
U31(dout(z0), z1, z2) → c5(DIN(der(z2))) 13.40/3.83
DIN(der(plus(z0, z1))) → c(U21(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(times(z0, z1))) → c1(U31(din(der(z0)), z0, z1), DIN(der(z0))) 13.40/3.83
DIN(der(der(z0))) → c2(U41(din(der(z0)), z0), DIN(der(z0)))
din, u21, u22, u31, u32, u41, u42
DIN, U21, U31, U41
c, c1, c2, c3, c5, c7