YES Problem: from(X) -> cons(X,n__from(s(X))) 2ndspos(0(),Z) -> rnil() 2ndspos(s(N),cons(X,Z)) -> 2ndspos(s(N),cons2(X,activate(Z))) 2ndspos(s(N),cons2(X,cons(Y,Z))) -> rcons(posrecip(Y),2ndsneg(N,activate(Z))) 2ndsneg(0(),Z) -> rnil() 2ndsneg(s(N),cons(X,Z)) -> 2ndsneg(s(N),cons2(X,activate(Z))) 2ndsneg(s(N),cons2(X,cons(Y,Z))) -> rcons(negrecip(Y),2ndspos(N,activate(Z))) pi(X) -> 2ndspos(X,from(0())) plus(0(),Y) -> Y plus(s(X),Y) -> s(plus(X,Y)) times(0(),Y) -> 0() times(s(X),Y) -> plus(Y,times(X,Y)) square(X) -> times(X,X) from(X) -> n__from(X) activate(n__from(X)) -> from(X) activate(X) -> X Proof: DP Processor: DPs: 2ndspos#(s(N),cons(X,Z)) -> activate#(Z) 2ndspos#(s(N),cons(X,Z)) -> 2ndspos#(s(N),cons2(X,activate(Z))) 2ndspos#(s(N),cons2(X,cons(Y,Z))) -> activate#(Z) 2ndspos#(s(N),cons2(X,cons(Y,Z))) -> 2ndsneg#(N,activate(Z)) 2ndsneg#(s(N),cons(X,Z)) -> activate#(Z) 2ndsneg#(s(N),cons(X,Z)) -> 2ndsneg#(s(N),cons2(X,activate(Z))) 2ndsneg#(s(N),cons2(X,cons(Y,Z))) -> activate#(Z) 2ndsneg#(s(N),cons2(X,cons(Y,Z))) -> 2ndspos#(N,activate(Z)) pi#(X) -> from#(0()) pi#(X) -> 2ndspos#(X,from(0())) plus#(s(X),Y) -> plus#(X,Y) times#(s(X),Y) -> times#(X,Y) times#(s(X),Y) -> plus#(Y,times(X,Y)) square#(X) -> times#(X,X) activate#(n__from(X)) -> from#(X) TRS: from(X) -> cons(X,n__from(s(X))) 2ndspos(0(),Z) -> rnil() 2ndspos(s(N),cons(X,Z)) -> 2ndspos(s(N),cons2(X,activate(Z))) 2ndspos(s(N),cons2(X,cons(Y,Z))) -> rcons(posrecip(Y),2ndsneg(N,activate(Z))) 2ndsneg(0(),Z) -> rnil() 2ndsneg(s(N),cons(X,Z)) -> 2ndsneg(s(N),cons2(X,activate(Z))) 2ndsneg(s(N),cons2(X,cons(Y,Z))) -> rcons(negrecip(Y),2ndspos(N,activate(Z))) pi(X) -> 2ndspos(X,from(0())) plus(0(),Y) -> Y plus(s(X),Y) -> s(plus(X,Y)) times(0(),Y) -> 0() times(s(X),Y) -> plus(Y,times(X,Y)) square(X) -> times(X,X) from(X) -> n__from(X) activate(n__from(X)) -> from(X) activate(X) -> X Usable Rule Processor: DPs: 2ndspos#(s(N),cons(X,Z)) -> activate#(Z) 2ndspos#(s(N),cons(X,Z)) -> 2ndspos#(s(N),cons2(X,activate(Z))) 2ndspos#(s(N),cons2(X,cons(Y,Z))) -> activate#(Z) 2ndspos#(s(N),cons2(X,cons(Y,Z))) -> 2ndsneg#(N,activate(Z)) 2ndsneg#(s(N),cons(X,Z)) -> activate#(Z) 2ndsneg#(s(N),cons(X,Z)) -> 2ndsneg#(s(N),cons2(X,activate(Z))) 2ndsneg#(s(N),cons2(X,cons(Y,Z))) -> activate#(Z) 2ndsneg#(s(N),cons2(X,cons(Y,Z))) -> 2ndspos#(N,activate(Z)) pi#(X) -> from#(0()) pi#(X) -> 2ndspos#(X,from(0())) plus#(s(X),Y) -> plus#(X,Y) times#(s(X),Y) -> times#(X,Y) times#(s(X),Y) -> plus#(Y,times(X,Y)) square#(X) -> times#(X,X) activate#(n__from(X)) -> from#(X) TRS: activate(n__from(X)) -> from(X) activate(X) -> X from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) times(0(),Y) -> 0() times(s(X),Y) -> plus(Y,times(X,Y)) plus(0(),Y) -> Y plus(s(X),Y) -> s(plus(X,Y)) Matrix Interpretation Processor: dim=1 usable rules: activate(n__from(X)) -> from(X) activate(X) -> X from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) interpretation: [square#](x0) = 7/2x0 + 5/2, [times#](x0, x1) = 3/2x0 + 2x1 + 2, [plus#](x0, x1) = 3/2x0 + 1, [pi#](x0) = 3x0 + 2, [2ndsneg#](x0, x1) = 3/2x0 + x1, [activate#](x0) = 1/2, [2ndspos#](x0, x1) = 5/2x0 + x1 + 1/2, [from#](x0) = 0, [times](x0, x1) = 2, [plus](x0, x1) = 0, [cons2](x0, x1) = 1/2x1, [activate](x0) = x0 + 1, [0] = 0, [cons](x0, x1) = 2x1 + 1, [n__from](x0) = 0, [s](x0) = 2x0 + 3, [from](x0) = 1 orientation: 2ndspos#(s(N),cons(X,Z)) = 5N + 2Z + 9 >= 1/2 = activate#(Z) 2ndspos#(s(N),cons(X,Z)) = 5N + 2Z + 9 >= 5N + 1/2Z + 17/2 = 2ndspos#(s(N),cons2(X,activate(Z))) 2ndspos#(s(N),cons2(X,cons(Y,Z))) = 5N + Z + 17/2 >= 1/2 = activate#(Z) 2ndspos#(s(N),cons2(X,cons(Y,Z))) = 5N + Z + 17/2 >= 3/2N + Z + 1 = 2ndsneg#(N,activate(Z)) 2ndsneg#(s(N),cons(X,Z)) = 3N + 2Z + 11/2 >= 1/2 = activate#(Z) 2ndsneg#(s(N),cons(X,Z)) = 3N + 2Z + 11/2 >= 3N + 1/2Z + 5 = 2ndsneg#(s(N),cons2(X,activate(Z))) 2ndsneg#(s(N),cons2(X,cons(Y,Z))) = 3N + Z + 5 >= 1/2 = activate#(Z) 2ndsneg#(s(N),cons2(X,cons(Y,Z))) = 3N + Z + 5 >= 5/2N + Z + 3/2 = 2ndspos#(N,activate(Z)) pi#(X) = 3X + 2 >= 0 = from#(0()) pi#(X) = 3X + 2 >= 5/2X + 3/2 = 2ndspos#(X,from(0())) plus#(s(X),Y) = 3X + 11/2 >= 3/2X + 1 = plus#(X,Y) times#(s(X),Y) = 3X + 2Y + 13/2 >= 3/2X + 2Y + 2 = times#(X,Y) times#(s(X),Y) = 3X + 2Y + 13/2 >= 3/2Y + 1 = plus#(Y,times(X,Y)) square#(X) = 7/2X + 5/2 >= 7/2X + 2 = times#(X,X) activate#(n__from(X)) = 1/2 >= 0 = from#(X) activate(n__from(X)) = 1 >= 1 = from(X) activate(X) = X + 1 >= X = X from(X) = 1 >= 1 = cons(X,n__from(s(X))) from(X) = 1 >= 0 = n__from(X) times(0(),Y) = 2 >= 0 = 0() times(s(X),Y) = 2 >= 0 = plus(Y,times(X,Y)) plus(0(),Y) = 0 >= Y = Y plus(s(X),Y) = 0 >= 3 = s(plus(X,Y)) problem: DPs: TRS: activate(n__from(X)) -> from(X) activate(X) -> X from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) times(0(),Y) -> 0() times(s(X),Y) -> plus(Y,times(X,Y)) plus(0(),Y) -> Y plus(s(X),Y) -> s(plus(X,Y)) Qed