YES Problem: 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) Proof: DP Processor: DPs: din#(der(plus(X,Y))) -> din#(der(X)) din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) u21#(dout(DX),X,Y) -> din#(der(Y)) u21#(dout(DX),X,Y) -> u22#(din(der(Y)),X,Y,DX) din#(der(times(X,Y))) -> din#(der(X)) din#(der(times(X,Y))) -> u31#(din(der(X)),X,Y) u31#(dout(DX),X,Y) -> din#(der(Y)) u31#(dout(DX),X,Y) -> u32#(din(der(Y)),X,Y,DX) din#(der(der(X))) -> din#(der(X)) din#(der(der(X))) -> u41#(din(der(X)),X) u41#(dout(DX),X) -> din#(der(DX)) u41#(dout(DX),X) -> u42#(din(der(DX)),X,DX) TRS: 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) TDG Processor: DPs: din#(der(plus(X,Y))) -> din#(der(X)) din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) u21#(dout(DX),X,Y) -> din#(der(Y)) u21#(dout(DX),X,Y) -> u22#(din(der(Y)),X,Y,DX) din#(der(times(X,Y))) -> din#(der(X)) din#(der(times(X,Y))) -> u31#(din(der(X)),X,Y) u31#(dout(DX),X,Y) -> din#(der(Y)) u31#(dout(DX),X,Y) -> u32#(din(der(Y)),X,Y,DX) din#(der(der(X))) -> din#(der(X)) din#(der(der(X))) -> u41#(din(der(X)),X) u41#(dout(DX),X) -> din#(der(DX)) u41#(dout(DX),X) -> u42#(din(der(DX)),X,DX) TRS: 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) graph: u41#(dout(DX),X) -> din#(der(DX)) -> din#(der(der(X))) -> u41#(din(der(X)),X) u41#(dout(DX),X) -> din#(der(DX)) -> din#(der(der(X))) -> din#(der(X)) u41#(dout(DX),X) -> din#(der(DX)) -> din#(der(times(X,Y))) -> u31#(din(der(X)),X,Y) u41#(dout(DX),X) -> din#(der(DX)) -> din#(der(times(X,Y))) -> din#(der(X)) u41#(dout(DX),X) -> din#(der(DX)) -> din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) u41#(dout(DX),X) -> din#(der(DX)) -> din#(der(plus(X,Y))) -> din#(der(X)) u31#(dout(DX),X,Y) -> din#(der(Y)) -> din#(der(der(X))) -> u41#(din(der(X)),X) u31#(dout(DX),X,Y) -> din#(der(Y)) -> 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) u31#(dout(DX),X,Y) -> din#(der(Y)) -> din#(der(times(X,Y))) -> din#(der(X)) u31#(dout(DX),X,Y) -> din#(der(Y)) -> din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) 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(der(X))) -> u41#(din(der(X)),X) u21#(dout(DX),X,Y) -> din#(der(Y)) -> din#(der(der(X))) -> din#(der(X)) u21#(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(times(X,Y))) -> din#(der(X)) u21#(dout(DX),X,Y) -> din#(der(Y)) -> din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) u21#(dout(DX),X,Y) -> din#(der(Y)) -> din#(der(plus(X,Y))) -> din#(der(X)) din#(der(times(X,Y))) -> u31#(din(der(X)),X,Y) -> u31#(dout(DX),X,Y) -> u32#(din(der(Y)),X,Y,DX) din#(der(times(X,Y))) -> u31#(din(der(X)),X,Y) -> u31#(dout(DX),X,Y) -> din#(der(Y)) din#(der(times(X,Y))) -> din#(der(X)) -> din#(der(der(X))) -> u41#(din(der(X)),X) din#(der(times(X,Y))) -> din#(der(X)) -> din#(der(der(X))) -> din#(der(X)) din#(der(times(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(times(X,Y))) -> din#(der(X)) din#(der(times(X,Y))) -> din#(der(X)) -> din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) din#(der(times(X,Y))) -> din#(der(X)) -> din#(der(plus(X,Y))) -> din#(der(X)) din#(der(der(X))) -> u41#(din(der(X)),X) -> u41#(dout(DX),X) -> u42#(din(der(DX)),X,DX) din#(der(der(X))) -> u41#(din(der(X)),X) -> u41#(dout(DX),X) -> din#(der(DX)) din#(der(der(X))) -> din#(der(X)) -> din#(der(der(X))) -> u41#(din(der(X)),X) din#(der(der(X))) -> din#(der(X)) -> din#(der(der(X))) -> din#(der(X)) din#(der(der(X))) -> din#(der(X)) -> din#(der(times(X,Y))) -> u31#(din(der(X)),X,Y) din#(der(der(X))) -> din#(der(X)) -> din#(der(times(X,Y))) -> din#(der(X)) din#(der(der(X))) -> din#(der(X)) -> din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) din#(der(der(X))) -> din#(der(X)) -> din#(der(plus(X,Y))) -> din#(der(X)) din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) -> u21#(dout(DX),X,Y) -> u22#(din(der(Y)),X,Y,DX) din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) -> u21#(dout(DX),X,Y) -> din#(der(Y)) din#(der(plus(X,Y))) -> din#(der(X)) -> din#(der(der(X))) -> u41#(din(der(X)),X) din#(der(plus(X,Y))) -> din#(der(X)) -> din#(der(der(X))) -> din#(der(X)) din#(der(plus(X,Y))) -> din#(der(X)) -> din#(der(times(X,Y))) -> u31#(din(der(X)),X,Y) din#(der(plus(X,Y))) -> din#(der(X)) -> din#(der(times(X,Y))) -> din#(der(X)) din#(der(plus(X,Y))) -> din#(der(X)) -> din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) din#(der(plus(X,Y))) -> din#(der(X)) -> din#(der(plus(X,Y))) -> din#(der(X)) SCC Processor: #sccs: 1 #rules: 9 #arcs: 42/144 DPs: u41#(dout(DX),X) -> din#(der(DX)) din#(der(plus(X,Y))) -> din#(der(X)) din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) u21#(dout(DX),X,Y) -> din#(der(Y)) din#(der(times(X,Y))) -> din#(der(X)) din#(der(times(X,Y))) -> u31#(din(der(X)),X,Y) u31#(dout(DX),X,Y) -> din#(der(Y)) din#(der(der(X))) -> din#(der(X)) din#(der(der(X))) -> u41#(din(der(X)),X) TRS: 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) Arctic Interpretation Processor: dimension: 1 interpretation: [u41#](x0, x1) = x0 + 4x1 + 0, [u31#](x0, x1, x2) = 4x2 + 0, [u21#](x0, x1, x2) = 4x2 + 0, [din#](x0) = 4x0 + 0, [u42](x0, x1, x2) = x0 + 4x1 + 4x2 + 0, [u41](x0, x1) = x0 + 4x1 + 0, [u32](x0, x1, x2, x3) = 2x0 + 6x1 + 6x2 + 6x3 + 5, [u31](x0, x1, x2) = 2x0 + 6x1 + 6x2 + 5, [times](x0, x1) = 2x0 + 2x1 + 1, [u22](x0, x1, x2, x3) = x0 + 4x1 + 4x2 + 4x3 + 0, [dout](x0) = 4x0 + 0, [u21](x0, x1, x2) = x0 + 4x1 + 4x2 + 0, [din](x0) = 4x0 + 0, [der](x0) = x0, [plus](x0, x1) = x0 + x1 orientation: u41#(dout(DX),X) = 4DX + 4X + 0 >= 4DX + 0 = din#(der(DX)) din#(der(plus(X,Y))) = 4X + 4Y + 0 >= 4X + 0 = din#(der(X)) din#(der(plus(X,Y))) = 4X + 4Y + 0 >= 4Y + 0 = u21#(din(der(X)),X,Y) u21#(dout(DX),X,Y) = 4Y + 0 >= 4Y + 0 = din#(der(Y)) din#(der(times(X,Y))) = 6X + 6Y + 5 >= 4X + 0 = din#(der(X)) din#(der(times(X,Y))) = 6X + 6Y + 5 >= 4Y + 0 = u31#(din(der(X)),X,Y) u31#(dout(DX),X,Y) = 4Y + 0 >= 4Y + 0 = din#(der(Y)) din#(der(der(X))) = 4X + 0 >= 4X + 0 = din#(der(X)) din#(der(der(X))) = 4X + 0 >= 4X + 0 = u41#(din(der(X)),X) din(der(plus(X,Y))) = 4X + 4Y + 0 >= 4X + 4Y + 0 = u21(din(der(X)),X,Y) u21(dout(DX),X,Y) = 4DX + 4X + 4Y + 0 >= 4DX + 4X + 4Y + 0 = u22(din(der(Y)),X,Y,DX) u22(dout(DY),X,Y,DX) = 4DX + 4DY + 4X + 4Y + 0 >= 4DX + 4DY + 0 = dout(plus(DX,DY)) din(der(times(X,Y))) = 6X + 6Y + 5 >= 6X + 6Y + 5 = u31(din(der(X)),X,Y) u31(dout(DX),X,Y) = 6DX + 6X + 6Y + 5 >= 6DX + 6X + 6Y + 5 = u32(din(der(Y)),X,Y,DX) u32(dout(DY),X,Y,DX) = 6DX + 6DY + 6X + 6Y + 5 >= 6DX + 6DY + 6X + 6Y + 5 = dout(plus(times(X,DY),times(Y,DX))) din(der(der(X))) = 4X + 0 >= 4X + 0 = u41(din(der(X)),X) u41(dout(DX),X) = 4DX + 4X + 0 >= 4DX + 4X + 0 = u42(din(der(DX)),X,DX) u42(dout(DDX),X,DX) = 4DDX + 4DX + 4X + 0 >= 4DDX + 0 = dout(DDX) problem: DPs: u41#(dout(DX),X) -> din#(der(DX)) din#(der(plus(X,Y))) -> din#(der(X)) din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) u21#(dout(DX),X,Y) -> din#(der(Y)) u31#(dout(DX),X,Y) -> din#(der(Y)) din#(der(der(X))) -> din#(der(X)) din#(der(der(X))) -> u41#(din(der(X)),X) TRS: 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) SCC Processor: #sccs: 1 #rules: 6 #arcs: 39/49 DPs: u41#(dout(DX),X) -> din#(der(DX)) din#(der(plus(X,Y))) -> din#(der(X)) din#(der(plus(X,Y))) -> u21#(din(der(X)),X,Y) u21#(dout(DX),X,Y) -> din#(der(Y)) din#(der(der(X))) -> din#(der(X)) din#(der(der(X))) -> u41#(din(der(X)),X) TRS: 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) KBO Processor: argument filtering: pi(plus) = [] pi(der) = [] pi(din) = [] pi(u21) = 0 pi(dout) = [0] pi(u22) = [0,3] pi(times) = [] pi(u31) = 0 pi(u32) = [0,3] pi(u41) = 0 pi(u42) = [0,2] pi(din#) = [0] pi(u21#) = 0 pi(u41#) = 0 weight function: w0 = 1 w(din#) = w(u41) = w(u31) = w(times) = w(dout) = w(din) = w(der) = w( plus) = 1 w(u41#) = w(u21#) = w(u42) = w(u32) = w(u22) = w(u21) = 0 precedence: times ~ dout ~ plus > u41# ~ u21# ~ din# ~ u42 ~ u41 ~ u32 ~ u31 ~ u22 ~ u21 ~ din ~ der problem: DPs: din#(der(plus(X,Y))) -> din#(der(X)) din#(der(der(X))) -> din#(der(X)) TRS: 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) Arctic Interpretation Processor: dimension: 1 interpretation: [din#](x0) = x0 + 0, [u42](x0, x1, x2) = x1 + 0, [u41](x0, x1) = x0 + x1 + 0, [u32](x0, x1, x2, x3) = 4x1 + 1, [u31](x0, x1, x2) = 4x1 + 4, [times](x0, x1) = 4x0 + 3x1 + 4, [u22](x0, x1, x2, x3) = 0, [dout](x0) = 0, [u21](x0, x1, x2) = 1, [din](x0) = x0 + 0, [der](x0) = x0 + 0, [plus](x0, x1) = 2x0 + 1 orientation: din#(der(plus(X,Y))) = 2X + 1 >= X + 0 = din#(der(X)) din#(der(der(X))) = X + 0 >= X + 0 = din#(der(X)) din(der(plus(X,Y))) = 2X + 1 >= 1 = u21(din(der(X)),X,Y) u21(dout(DX),X,Y) = 1 >= 0 = u22(din(der(Y)),X,Y,DX) u22(dout(DY),X,Y,DX) = 0 >= 0 = dout(plus(DX,DY)) din(der(times(X,Y))) = 4X + 3Y + 4 >= 4X + 4 = u31(din(der(X)),X,Y) u31(dout(DX),X,Y) = 4X + 4 >= 4X + 1 = u32(din(der(Y)),X,Y,DX) u32(dout(DY),X,Y,DX) = 4X + 1 >= 0 = dout(plus(times(X,DY),times(Y,DX))) din(der(der(X))) = X + 0 >= X + 0 = u41(din(der(X)),X) u41(dout(DX),X) = X + 0 >= X + 0 = u42(din(der(DX)),X,DX) u42(dout(DDX),X,DX) = X + 0 >= 0 = dout(DDX) problem: DPs: din#(der(der(X))) -> din#(der(X)) TRS: 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) Subterm Criterion Processor: simple projection: pi(din#) = 0 problem: DPs: TRS: 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) Qed