/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We split firstr-order part and higher-order part, and do modular checking by a general modularity. ******** FO SN check ******** Check SN using NaTT (Nagoya Termination Tool) Input TRS: 1: minus(X,0()) -> X 2: minus(s(Y),s(U)) -> minus(Y,U) 3: double(0()) -> 0() 4: double(s(V)) -> s(s(double(V))) 5: plus(0(),W) -> W 6: plus(s(P),X1) -> s(plus(P,X1)) 7: plus(s(Y1),U1) -> plus(Y1,s(U1)) 8: plus(s(V1),W1) -> s(plus(minus(V1,W1),double(W1))) 9: _(X1,X2) -> X1 10: _(X1,X2) -> X2 Number of strict rules: 10 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #minus(s(Y),s(U)) -> #minus(Y,U) #2: #plus(s(P),X1) -> #plus(P,X1) #3: #plus(s(Y1),U1) -> #plus(Y1,s(U1)) #4: #plus(s(V1),W1) -> #plus(minus(V1,W1),double(W1)) #5: #plus(s(V1),W1) -> #minus(V1,W1) #6: #plus(s(V1),W1) -> #double(W1) #7: #double(s(V)) -> #double(V) Number of SCCs: 3, DPs: 5 SCC { #7 } POLO(Sum)... succeeded. s w: x1 + 1 minus w: 0 #plus w: 0 _ w: 0 0 w: 0 #double w: x1 double w: 0 #minus w: 0 #_ w: 0 plus w: 0 USABLE RULES: { } Removed DPs: #7 Number of SCCs: 2, DPs: 4 SCC { #1 } POLO(Sum)... succeeded. s w: x1 + 1 minus w: 0 #plus w: 0 _ w: 0 0 w: 0 #double w: 0 double w: 0 #minus w: x2 #_ w: 0 plus w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 1, DPs: 3 SCC { #2..4 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + 1 #plus w: x1 _ w: 0 0 w: 1238 #double w: 0 double w: 1237 #minus w: 0 #_ w: 0 plus w: 0 USABLE RULES: { 1 2 } Removed DPs: #2..4 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: minus(X,0()) -> X 2: minus(s(Y),s(U)) -> minus(Y,U) 3: double(0()) -> 0() 4: double(s(V)) -> s(s(double(V))) 5: plus(0(),W) -> W 6: plus(s(P),X1) -> s(plus(P,X1)) 7: plus(s(Y1),U1) -> plus(Y1,s(U1)) 8: plus(s(V1),W1) -> s(plus(minus(V1,W1),double(W1))) 9: _(X1,X2) -> X1 10: _(X1,X2) -> X2 Number of strict rules: 10 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #minus(s(Y),s(U)) -> #minus(Y,U) #2: #plus(s(P),X1) -> #plus(P,X1) #3: #plus(s(Y1),U1) -> #plus(Y1,s(U1)) #4: #plus(s(V1),W1) -> #plus(minus(V1,W1),double(W1)) #5: #plus(s(V1),W1) -> #minus(V1,W1) #6: #plus(s(V1),W1) -> #double(W1) #7: #double(s(V)) -> #double(V) Number of SCCs: 3, DPs: 5 SCC { #7 } POLO(Sum)... succeeded. s w: x1 + 1 minus w: 0 #plus w: 0 _ w: 0 0 w: 0 #double w: x1 double w: 0 #minus w: 0 #_ w: 0 plus w: 0 USABLE RULES: { } Removed DPs: #7 Number of SCCs: 2, DPs: 4 SCC { #1 } POLO(Sum)... succeeded. s w: x1 + 1 minus w: 0 #plus w: 0 _ w: 0 0 w: 0 #double w: 0 double w: 0 #minus w: x2 #_ w: 0 plus w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 1, DPs: 3 SCC { #2..4 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + 1 #plus w: x1 _ w: 0 0 w: 1238 #double w: 0 double w: 1237 #minus w: 0 #_ w: 0 plus w: 0 USABLE RULES: { 1 2 } Removed DPs: #2..4 Number of SCCs: 0, DPs: 0 >>YES ******** Signature ******** map : ((c -> c),d) -> d nil : d cons : (c,d) -> d filter : ((c -> b),d) -> d filter2 : (b,(c -> b),c,d) -> d true : b false : b ******** Computation rules ******** (9) map(J1,nil) => nil (10) map(F2,cons(Y2,U2)) => cons(F2[Y2],map(F2,U2)) (11) filter(H2,nil) => nil (12) filter(I2,cons(P2,X3)) => filter2(I2[P2],I2,P2,X3) (13) filter2(true,Z3,U3,V3) => cons(U3,filter(Z3,V3)) (14) filter2(false,I3,P3,X4) => filter(I3,X4) ******** General Schema criterion ******** Found constructors: 0, cons, false, nil, s, true Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>Regared as equal: filter2, filter Checking (1) minus(X,0) => X (meta X)[is acc in X,0] [is acc in X] >>True Checking (2) minus(s(Y),s(U)) => minus(Y,U) (fun minus=minus) subterm comparison of args w. LR LR (meta Y)[is acc in s(Y),s(U)] [is positive in s(Y)] [is acc in Y] (meta U)[is acc in s(Y),s(U)] [is positive in s(Y)] [is positive in s(U)] [is acc in U] >>True Checking (3) double(0) => 0 (fun double>0) >>True Checking (4) double(s(V)) => s(s(double(V))) (fun double>s) (fun double>s) (fun double=double) subterm comparison of args w. LR LR (meta V)[is acc in s(V)] [is positive in s(V)] [is acc in V] >>True Checking (5) 0 + W => W (meta W)[is acc in 0,W] [is positive in 0] [is acc in W] >>True Checking (6) s(P) + X1 => s(P + X1) (fun plus>s) (fun plus=plus) subterm comparison of args w. LR LR (meta P)[is acc in s(P),X1] [is positive in s(P)] [is acc in P] (meta X1)[is acc in s(P),X1] [is positive in s(P)] [is acc in X1] >>True Checking (7) s(Y1) + U1 => Y1 + s(U1) (fun plus=plus) subterm comparison of args w. LR LR (meta Y1)[is acc in s(Y1),U1] [is positive in s(Y1)] [is acc in Y1] (fun plus>s) (meta U1)[is acc in s(Y1),U1] [is positive in s(Y1)] [is acc in U1] >>True Checking (8) s(V1) + W1 => s(minus(V1,W1) + double(W1)) (fun plus>s) (fun plus=plus) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) minus(X,0) => X (meta X)[is acc in X,0] [is acc in X] >>True Checking (2) minus(s(Y),s(U)) => minus(Y,U) (fun minus=minus) subterm comparison of args w. RL RL (meta Y)[is acc in s(Y),s(U)] [is positive in s(Y)] [is acc in Y] (meta U)[is acc in s(Y),s(U)] [is positive in s(Y)] [is positive in s(U)] [is acc in U] >>True Checking (3) double(0) => 0 (fun double>0) >>True Checking (4) double(s(V)) => s(s(double(V))) (fun double>s) (fun double>s) (fun double=double) subterm comparison of args w. RL RL (meta V)[is acc in s(V)] [is positive in s(V)] [is acc in V] >>True Checking (5) 0 + W => W (meta W)[is acc in 0,W] [is positive in 0] [is acc in W] >>True Checking (6) s(P) + X1 => s(P + X1) (fun plus>s) (fun plus=plus) subterm comparison of args w. RL RL (meta P)[is acc in s(P),X1] [is positive in s(P)] [is acc in P] (meta X1)[is acc in s(P),X1] [is positive in s(P)] [is acc in X1] >>True Checking (7) s(Y1) + U1 => Y1 + s(U1) (fun plus=plus) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) minus(X,0) => X (meta X)[is acc in X,0] [is acc in X] >>True Checking (2) minus(s(Y),s(U)) => minus(Y,U) (fun minus=minus) subterm comparison of args w. Mul Mul (meta Y)[is acc in s(Y),s(U)] [is positive in s(Y)] [is acc in Y] (meta U)[is acc in s(Y),s(U)] [is positive in s(Y)] [is positive in s(U)] [is acc in U] >>True Checking (3) double(0) => 0 (fun double>0) >>True Checking (4) double(s(V)) => s(s(double(V))) (fun double>s) (fun double>s) (fun double=double) subterm comparison of args w. Mul Mul (meta V)[is acc in s(V)] [is positive in s(V)] [is acc in V] >>True Checking (5) 0 + W => W (meta W)[is acc in 0,W] [is positive in 0] [is acc in W] >>True Checking (6) s(P) + X1 => s(P + X1) (fun plus>s) (fun plus=plus) subterm comparison of args w. Mul Mul (meta P)[is acc in s(P),X1] [is positive in s(P)] [is acc in P] (meta X1)[is acc in s(P),X1] [is positive in s(P)] [is acc in X1] >>True Checking (7) s(Y1) + U1 => Y1 + s(U1) (fun plus=plus) subterm comparison of args w. Mul Mul >>False Found constructors: nil, cons, true, false Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>Regared as equal: filter2, filter Checking (9) map(J1,nil) => nil (fun map>nil) >>True Checking (10) map(F2,cons(Y2,U2)) => cons(F2[Y2],map(F2,U2)) (fun map>cons) (meta F2)[is acc in F2,cons(Y2,U2)] [is acc in F2] (meta Y2)[is acc in F2,cons(Y2,U2)] [is positive in cons(Y2,U2)] [is acc in Y2] (fun map=map) subterm comparison of args w. LR LR (meta F2)[is acc in F2,cons(Y2,U2)] [is acc in F2] (meta U2)[is acc in F2,cons(Y2,U2)] [is positive in cons(Y2,U2)] [is acc in U2] >>True Checking (11) filter(H2,nil) => nil (fun filter>nil) >>True Checking (12) filter(I2,cons(P2,X3)) => filter2(I2[P2],I2,P2,X3) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (meta I2)[is acc in I2,cons(P2,X3)] [is acc in I2] (meta P2)[is acc in I2,cons(P2,X3)] [is positive in cons(P2,X3)] [is acc in P2] (meta I2)[is acc in I2,cons(P2,X3)] [is acc in I2] (meta P2)[is acc in I2,cons(P2,X3)] [is positive in cons(P2,X3)] [is acc in P2] (meta X3)[is acc in I2,cons(P2,X3)] [is positive in cons(P2,X3)] [is acc in X3] >>True Checking (13) filter2(true,Z3,U3,V3) => cons(U3,filter(Z3,V3)) (fun filter2>cons) (meta U3)[is acc in true,Z3,U3,V3] [is positive in true] [is acc in U3] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta Z3)[is acc in true,Z3,U3,V3] [is positive in true] [is acc in Z3] (meta V3)[is acc in true,Z3,U3,V3] [is positive in true] [is acc in V3] >>True Checking (14) filter2(false,I3,P3,X4) => filter(I3,X4) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta I3)[is acc in false,I3,P3,X4] [is positive in false] [is acc in I3] (meta X4)[is acc in false,I3,P3,X4] [is positive in false] [is acc in X4] >>True #SN! ******** Signature ******** 0 : a cons : (c,d) -> d double : a -> a false : b filter : ((c -> b),d) -> d filter2 : (b,(c -> b),c,d) -> d map : ((c -> c),d) -> d minus : (a,a) -> a nil : d plus : (a,a) -> a s : a -> a true : b ******** Computation Rules ******** (1) minus(X,0) => X (2) minus(s(Y),s(U)) => minus(Y,U) (3) double(0) => 0 (4) double(s(V)) => s(s(double(V))) (5) 0 + W => W (6) s(P) + X1 => s(P + X1) (7) s(Y1) + U1 => Y1 + s(U1) (8) s(V1) + W1 => s(minus(V1,W1) + double(W1)) (9) map(J1,nil) => nil (10) map(F2,cons(Y2,U2)) => cons(F2[Y2],map(F2,U2)) (11) filter(H2,nil) => nil (12) filter(I2,cons(P2,X3)) => filter2(I2[P2],I2,P2,X3) (13) filter2(true,Z3,U3,V3) => cons(U3,filter(Z3,V3)) (14) filter2(false,I3,P3,X4) => filter(I3,X4) YES