YES Problem: from(X) -> cons(X,n__from(n__s(X))) 2ndspos(0(),Z) -> rnil() 2ndspos(s(N),cons(X,n__cons(Y,Z))) -> rcons(posrecip(activate(Y)),2ndsneg(N,activate(Z))) 2ndsneg(0(),Z) -> rnil() 2ndsneg(s(N),cons(X,n__cons(Y,Z))) -> rcons(negrecip(activate(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) s(X) -> n__s(X) cons(X1,X2) -> n__cons(X1,X2) activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(X) -> X Proof: DP Processor: DPs: from#(X) -> cons#(X,n__from(n__s(X))) 2ndspos#(s(N),cons(X,n__cons(Y,Z))) -> activate#(Z) 2ndspos#(s(N),cons(X,n__cons(Y,Z))) -> 2ndsneg#(N,activate(Z)) 2ndspos#(s(N),cons(X,n__cons(Y,Z))) -> activate#(Y) 2ndsneg#(s(N),cons(X,n__cons(Y,Z))) -> activate#(Z) 2ndsneg#(s(N),cons(X,n__cons(Y,Z))) -> 2ndspos#(N,activate(Z)) 2ndsneg#(s(N),cons(X,n__cons(Y,Z))) -> activate#(Y) pi#(X) -> from#(0()) pi#(X) -> 2ndspos#(X,from(0())) plus#(s(X),Y) -> plus#(X,Y) plus#(s(X),Y) -> s#(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)) -> activate#(X) activate#(n__from(X)) -> from#(activate(X)) activate#(n__s(X)) -> activate#(X) activate#(n__s(X)) -> s#(activate(X)) activate#(n__cons(X1,X2)) -> activate#(X1) activate#(n__cons(X1,X2)) -> cons#(activate(X1),X2) TRS: from(X) -> cons(X,n__from(n__s(X))) 2ndspos(0(),Z) -> rnil() 2ndspos(s(N),cons(X,n__cons(Y,Z))) -> rcons(posrecip(activate(Y)),2ndsneg(N,activate(Z))) 2ndsneg(0(),Z) -> rnil() 2ndsneg(s(N),cons(X,n__cons(Y,Z))) -> rcons(negrecip(activate(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) s(X) -> n__s(X) cons(X1,X2) -> n__cons(X1,X2) activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(X) -> X Usable Rule Processor: DPs: from#(X) -> cons#(X,n__from(n__s(X))) 2ndspos#(s(N),cons(X,n__cons(Y,Z))) -> activate#(Z) 2ndspos#(s(N),cons(X,n__cons(Y,Z))) -> 2ndsneg#(N,activate(Z)) 2ndspos#(s(N),cons(X,n__cons(Y,Z))) -> activate#(Y) 2ndsneg#(s(N),cons(X,n__cons(Y,Z))) -> activate#(Z) 2ndsneg#(s(N),cons(X,n__cons(Y,Z))) -> 2ndspos#(N,activate(Z)) 2ndsneg#(s(N),cons(X,n__cons(Y,Z))) -> activate#(Y) pi#(X) -> from#(0()) pi#(X) -> 2ndspos#(X,from(0())) plus#(s(X),Y) -> plus#(X,Y) plus#(s(X),Y) -> s#(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)) -> activate#(X) activate#(n__from(X)) -> from#(activate(X)) activate#(n__s(X)) -> activate#(X) activate#(n__s(X)) -> s#(activate(X)) activate#(n__cons(X1,X2)) -> activate#(X1) activate#(n__cons(X1,X2)) -> cons#(activate(X1),X2) TRS: activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(X) -> X from(X) -> cons(X,n__from(n__s(X))) from(X) -> n__from(X) s(X) -> n__s(X) cons(X1,X2) -> n__cons(X1,X2) 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)) Matrix Interpretation Processor: dim=2 usable rules: activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(X) -> X from(X) -> cons(X,n__from(n__s(X))) from(X) -> n__from(X) s(X) -> n__s(X) cons(X1,X2) -> n__cons(X1,X2) interpretation: [square#](x0) = [3 2]x0 + [2], [times#](x0, x1) = [1 0]x0 + [2 0]x1 + [1], [s#](x0) = [0], [plus#](x0, x1) = [1 0]x0 + [1], [pi#](x0) = [3 1]x0 + [2], [2ndsneg#](x0, x1) = [3 0]x0 + [1 0]x1, [activate#](x0) = [1 0]x0 + [1], [2ndspos#](x0, x1) = [2 0]x0 + [1 0]x1, [cons#](x0, x1) = [0], [from#](x0) = [1], [1 0] [2 2] [1] [times](x0, x1) = [0 2]x0 + [3 0]x1 + [3], [0 2] [1 1] [2] [plus](x0, x1) = [0 1]x0 + [1 0]x1 + [2], [1 0] [activate](x0) = [3 1]x0, [1 0] [0 2] [1] [n__cons](x0, x1) = [1 0]x0 + [1 1]x1 + [0], [2 0] [2] [s](x0) = [0 0]x0 + [2], [0] [0] = [2], [1 0] [0 2] [1] [cons](x0, x1) = [1 0]x0 + [1 2]x1 + [0], [1 0] [1] [n__from](x0) = [0 0]x0 + [0], [2 0] [2] [n__s](x0) = [0 0]x0 + [0], [1 0] [1] [from](x0) = [3 0]x0 + [3] orientation: from#(X) = [1] >= [0] = cons#(X,n__from(n__s(X))) 2ndspos#(s(N),cons(X,n__cons(Y,Z))) = [4 0]N + [1 0]X + [2 0]Y + [2 2]Z + [5] >= [1 0]Z + [1] = activate#(Z) 2ndspos#(s(N),cons(X,n__cons(Y,Z))) = [4 0]N + [1 0]X + [2 0]Y + [2 2]Z + [5] >= [3 0]N + [1 0]Z = 2ndsneg#(N,activate(Z)) 2ndspos#(s(N),cons(X,n__cons(Y,Z))) = [4 0]N + [1 0]X + [2 0]Y + [2 2]Z + [5] >= [1 0]Y + [1] = activate#(Y) 2ndsneg#(s(N),cons(X,n__cons(Y,Z))) = [6 0]N + [1 0]X + [2 0]Y + [2 2]Z + [7] >= [1 0]Z + [1] = activate#(Z) 2ndsneg#(s(N),cons(X,n__cons(Y,Z))) = [6 0]N + [1 0]X + [2 0]Y + [2 2]Z + [7] >= [2 0]N + [1 0]Z = 2ndspos#(N,activate(Z)) 2ndsneg#(s(N),cons(X,n__cons(Y,Z))) = [6 0]N + [1 0]X + [2 0]Y + [2 2]Z + [7] >= [1 0]Y + [1] = activate#(Y) pi#(X) = [3 1]X + [2] >= [1] = from#(0()) pi#(X) = [3 1]X + [2] >= [2 0]X + [1] = 2ndspos#(X,from(0())) plus#(s(X),Y) = [2 0]X + [3] >= [1 0]X + [1] = plus#(X,Y) plus#(s(X),Y) = [2 0]X + [3] >= [0] = s#(plus(X,Y)) times#(s(X),Y) = [2 0]X + [2 0]Y + [3] >= [1 0]X + [2 0]Y + [1] = times#(X,Y) times#(s(X),Y) = [2 0]X + [2 0]Y + [3] >= [1 0]Y + [1] = plus#(Y,times(X,Y)) square#(X) = [3 2]X + [2] >= [3 0]X + [1] = times#(X,X) activate#(n__from(X)) = [1 0]X + [2] >= [1 0]X + [1] = activate#(X) activate#(n__from(X)) = [1 0]X + [2] >= [1] = from#(activate(X)) activate#(n__s(X)) = [2 0]X + [3] >= [1 0]X + [1] = activate#(X) activate#(n__s(X)) = [2 0]X + [3] >= [0] = s#(activate(X)) activate#(n__cons(X1,X2)) = [1 0]X1 + [0 2]X2 + [2] >= [1 0]X1 + [1] = activate#(X1) activate#(n__cons(X1,X2)) = [1 0]X1 + [0 2]X2 + [2] >= [0] = cons#(activate(X1),X2) [1 0] [1] [1 0] [1] activate(n__from(X)) = [3 0]X + [3] >= [3 0]X + [3] = from(activate(X)) [2 0] [2] [2 0] [2] activate(n__s(X)) = [6 0]X + [6] >= [0 0]X + [2] = s(activate(X)) [1 0] [0 2] [1] [1 0] [0 2] [1] activate(n__cons(X1,X2)) = [4 0]X1 + [1 7]X2 + [3] >= [1 0]X1 + [1 2]X2 + [0] = cons(activate(X1),X2) [1 0] activate(X) = [3 1]X >= X = X [1 0] [1] [1 0] [1] from(X) = [3 0]X + [3] >= [3 0]X + [3] = cons(X,n__from(n__s(X))) [1 0] [1] [1 0] [1] from(X) = [3 0]X + [3] >= [0 0]X + [0] = n__from(X) [2 0] [2] [2 0] [2] s(X) = [0 0]X + [2] >= [0 0]X + [0] = n__s(X) [1 0] [0 2] [1] [1 0] [0 2] [1] cons(X1,X2) = [1 0]X1 + [1 2]X2 + [0] >= [1 0]X1 + [1 1]X2 + [0] = n__cons(X1,X2) [1 1] [6] plus(0(),Y) = [1 0]Y + [4] >= Y = Y [1 1] [6] [0 4] [2 2] [6] plus(s(X),Y) = [1 0]Y + [4] >= [0 0]X + [0 0]Y + [2] = s(plus(X,Y)) [2 2] [1] [0] times(0(),Y) = [3 0]Y + [7] >= [2] = 0() [2 0] [2 2] [3] [1 2] [5 4] [6] times(s(X),Y) = [0 0]X + [3 0]Y + [7] >= [1 0]X + [2 3]Y + [3] = plus(Y,times(X,Y)) problem: DPs: TRS: activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(X) -> X from(X) -> cons(X,n__from(n__s(X))) from(X) -> n__from(X) s(X) -> n__s(X) cons(X1,X2) -> n__cons(X1,X2) 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)) Qed