/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES ******** General Schema criterion ******** Found constructors: 0, add, false, nil, s, true Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>Regared as equal: filter2, filter Checking (1) eq(0,0) => true (fun eq>true) >>True Checking (2) eq(0,s(X)) => false (fun eq>false) >>True Checking (3) eq(s(Y),0) => false (fun eq>false) >>True Checking (4) eq(s(U),s(V)) => eq(U,V) (fun eq=eq) subterm comparison of args w. LR LR (meta U)[is acc in s(U),s(V)] [is positive in s(U)] [is acc in U] (meta V)[is acc in s(U),s(V)] [is positive in s(U)] [is positive in s(V)] [is acc in V] >>True Checking (5) le(0,W) => true (fun le>true) >>True Checking (6) le(s(P),0) => false (fun le>false) >>True Checking (7) le(s(X1),s(Y1)) => le(X1,Y1) (fun le=le) subterm comparison of args w. LR LR (meta X1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is acc in X1] (meta Y1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is positive in s(Y1)] [is acc in Y1] >>True Checking (8) nil@U1 => U1 (meta U1)[is acc in nil,U1] [is positive in nil] [is acc in U1] >>True Checking (9) add(V1,W1)@P1 => add(V1,W1@P1) (fun app>add) (meta V1)[is acc in add(V1,W1),P1] [is positive in add(V1,W1)] [is acc in V1] (fun app=app) subterm comparison of args w. LR LR (meta W1)[is acc in add(V1,W1),P1] [is positive in add(V1,W1)] [is acc in W1] (meta P1)[is acc in add(V1,W1),P1] [is positive in add(V1,W1)] [is acc in P1] >>True Checking (10) min(add(X2,nil)) => X2 (meta X2)[is acc in add(X2,nil)] [is positive in add(X2,nil)] [is acc in X2] >>True Checking (11) min(add(U2,add(Y2,V2))) => ifxb6220min(le(U2,Y2),add(U2,add(Y2,V2))) (fun min>ifxb6220min) (fun min>le) (meta U2)[is acc in add(U2,add(Y2,V2))] [is positive in add(U2,add(Y2,V2))] [is acc in U2] (meta Y2)[is acc in add(U2,add(Y2,V2))] [is positive in add(U2,add(Y2,V2))] [is positive in add(Y2,V2)] [is acc in Y2] (fun min>add) (meta U2)[is acc in add(U2,add(Y2,V2))] [is positive in add(U2,add(Y2,V2))] [is acc in U2] (fun min>add) (meta Y2)[is acc in add(U2,add(Y2,V2))] [is positive in add(U2,add(Y2,V2))] [is positive in add(Y2,V2)] [is acc in Y2] (meta V2)[is acc in add(U2,add(Y2,V2))] [is positive in add(U2,add(Y2,V2))] [is positive in add(Y2,V2)] [is acc in V2] >>True Checking (12) ifxb6220min(true,add(P2,add(W2,X3))) => min(add(P2,X3)) (fun ifxb6220min>min) (fun ifxb6220min>add) (meta P2)[is acc in true,add(P2,add(W2,X3))] [is positive in true] [is positive in add(P2,add(W2,X3))] [is acc in P2] (meta X3)[is acc in true,add(P2,add(W2,X3))] [is positive in true] [is positive in add(P2,add(W2,X3))] [is positive in add(W2,X3)] [is acc in X3] >>True Checking (13) ifxb6220min(false,add(U3,add(Y3,V3))) => min(add(Y3,V3)) (fun ifxb6220min>min) (fun ifxb6220min>add) (meta Y3)[is acc in false,add(U3,add(Y3,V3))] [is positive in false] [is positive in add(U3,add(Y3,V3))] [is positive in add(Y3,V3)] [is acc in Y3] (meta V3)[is acc in false,add(U3,add(Y3,V3))] [is positive in false] [is positive in add(U3,add(Y3,V3))] [is positive in add(Y3,V3)] [is acc in V3] >>True Checking (14) rm(W3,nil) => nil (fun rm>nil) >>True Checking (15) rm(X4,add(P3,Y4)) => ifxb6220rm(eq(X4,P3),X4,add(P3,Y4)) (fun rm>ifxb6220rm) (fun rm>eq) (meta X4)[is acc in X4,add(P3,Y4)] [is acc in X4] (meta P3)[is acc in X4,add(P3,Y4)] [is positive in add(P3,Y4)] [is acc in P3] (meta X4)[is acc in X4,add(P3,Y4)] [is acc in X4] (fun rm>add) (meta P3)[is acc in X4,add(P3,Y4)] [is positive in add(P3,Y4)] [is acc in P3] (meta Y4)[is acc in X4,add(P3,Y4)] [is positive in add(P3,Y4)] [is acc in Y4] >>True Checking (16) ifxb6220rm(true,V4,add(U4,W4)) => rm(V4,W4) (fun ifxb6220rm>rm) (meta V4)[is acc in true,V4,add(U4,W4)] [is positive in true] [is acc in V4] (meta W4)[is acc in true,V4,add(U4,W4)] [is positive in true] [is positive in add(U4,W4)] [is acc in W4] >>True Checking (17) ifxb6220rm(false,X5,add(P4,Y5)) => add(P4,rm(X5,Y5)) (fun ifxb6220rm>add) (meta P4)[is acc in false,X5,add(P4,Y5)] [is positive in false] [is positive in add(P4,Y5)] [is acc in P4] (fun ifxb6220rm>rm) (meta X5)[is acc in false,X5,add(P4,Y5)] [is positive in false] [is acc in X5] (meta Y5)[is acc in false,X5,add(P4,Y5)] [is positive in false] [is positive in add(P4,Y5)] [is acc in Y5] >>True Checking (18) minsort(nil,nil) => nil (fun minsort>nil) >>True Checking (19) minsort(add(U5,V5),W5) => ifxb6220minsort(eq(U5,min(add(U5,V5))),add(U5,V5),W5) (fun minsort>ifxb6220minsort) (fun minsort>eq) (meta U5)[is acc in add(U5,V5),W5] [is positive in add(U5,V5)] [is acc in U5] (fun minsort>min) (fun minsort>add) (meta U5)[is acc in add(U5,V5),W5] [is positive in add(U5,V5)] [is acc in U5] (meta V5)[is acc in add(U5,V5),W5] [is positive in add(U5,V5)] [is acc in V5] (fun minsort>add) (meta U5)[is acc in add(U5,V5),W5] [is positive in add(U5,V5)] [is acc in U5] (meta V5)[is acc in add(U5,V5),W5] [is positive in add(U5,V5)] [is acc in V5] (meta W5)[is acc in add(U5,V5),W5] [is positive in add(U5,V5)] [is acc in W5] >>True Checking (20) ifxb6220minsort(true,add(P5,X6),Y6) => add(P5,minsort(rm(P5,X6)@Y6,nil)) (fun ifxb6220minsort>add) (meta P5)[is acc in true,add(P5,X6),Y6] [is positive in true] [is positive in add(P5,X6)] [is acc in P5] (fun ifxb6220minsort>minsort) (fun ifxb6220minsort>app) (fun ifxb6220minsort>rm) (meta P5)[is acc in true,add(P5,X6),Y6] [is positive in true] [is positive in add(P5,X6)] [is acc in P5] (meta X6)[is acc in true,add(P5,X6),Y6] [is positive in true] [is positive in add(P5,X6)] [is acc in X6] (meta Y6)[is acc in true,add(P5,X6),Y6] [is positive in true] [is positive in add(P5,X6)] [is acc in Y6] (fun ifxb6220minsort>nil) >>True Checking (21) ifxb6220minsort(false,add(U6,V6),W6) => minsort(V6,add(U6,W6)) (fun ifxb6220minsort>minsort) (meta V6)[is acc in false,add(U6,V6),W6] [is positive in false] [is positive in add(U6,V6)] [is acc in V6] (fun ifxb6220minsort>add) (meta U6)[is acc in false,add(U6,V6),W6] [is positive in false] [is positive in add(U6,V6)] [is acc in U6] (meta W6)[is acc in false,add(U6,V6),W6] [is positive in false] [is positive in add(U6,V6)] [is acc in W6] >>True Checking (22) map(J6,nil) => nil (fun map>nil) >>True Checking (23) map(F7,add(Y7,U7)) => add(F7[Y7],map(F7,U7)) (fun map>add) (meta F7)[is acc in F7,add(Y7,U7)] [is acc in F7] (meta Y7)[is acc in F7,add(Y7,U7)] [is positive in add(Y7,U7)] [is acc in Y7] (fun map=map) subterm comparison of args w. LR LR (meta F7)[is acc in F7,add(Y7,U7)] [is acc in F7] (meta U7)[is acc in F7,add(Y7,U7)] [is positive in add(Y7,U7)] [is acc in U7] >>True Checking (24) filter(H7,nil) => nil (fun filter>nil) >>True Checking (25) filter(I7,add(P7,X8)) => filter2(I7[P7],I7,P7,X8) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (meta I7)[is acc in I7,add(P7,X8)] [is acc in I7] (meta P7)[is acc in I7,add(P7,X8)] [is positive in add(P7,X8)] [is acc in P7] (meta I7)[is acc in I7,add(P7,X8)] [is acc in I7] (meta P7)[is acc in I7,add(P7,X8)] [is positive in add(P7,X8)] [is acc in P7] (meta X8)[is acc in I7,add(P7,X8)] [is positive in add(P7,X8)] [is acc in X8] >>True Checking (26) filter2(true,Z8,U8,V8) => add(U8,filter(Z8,V8)) (fun filter2>add) (meta U8)[is acc in true,Z8,U8,V8] [is positive in true] [is acc in U8] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta Z8)[is acc in true,Z8,U8,V8] [is positive in true] [is acc in Z8] (meta V8)[is acc in true,Z8,U8,V8] [is positive in true] [is acc in V8] >>True Checking (27) filter2(false,I8,P8,X9) => filter(I8,X9) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta I8)[is acc in false,I8,P8,X9] [is positive in false] [is acc in I8] (meta X9)[is acc in false,I8,P8,X9] [is positive in false] [is acc in X9] >>True #SN! ******** Signature ******** 0 : b add : (b,c) -> c app : (c,c) -> c eq : (b,b) -> a false : a filter : ((b -> a),c) -> c filter2 : (a,(b -> a),b,c) -> c ifxb6220min : (a,c) -> b ifxb6220minsort : (a,c,c) -> c ifxb6220rm : (a,b,c) -> c le : (b,b) -> a map : ((b -> b),c) -> c min : c -> b minsort : (c,c) -> c nil : c rm : (b,c) -> c s : b -> b true : a ******** Computation Rules ******** (1) eq(0,0) => true (2) eq(0,s(X)) => false (3) eq(s(Y),0) => false (4) eq(s(U),s(V)) => eq(U,V) (5) le(0,W) => true (6) le(s(P),0) => false (7) le(s(X1),s(Y1)) => le(X1,Y1) (8) nil@U1 => U1 (9) add(V1,W1)@P1 => add(V1,W1@P1) (10) min(add(X2,nil)) => X2 (11) min(add(U2,add(Y2,V2))) => ifxb6220min(le(U2,Y2),add(U2,add(Y2,V2))) (12) ifxb6220min(true,add(P2,add(W2,X3))) => min(add(P2,X3)) (13) ifxb6220min(false,add(U3,add(Y3,V3))) => min(add(Y3,V3)) (14) rm(W3,nil) => nil (15) rm(X4,add(P3,Y4)) => ifxb6220rm(eq(X4,P3),X4,add(P3,Y4)) (16) ifxb6220rm(true,V4,add(U4,W4)) => rm(V4,W4) (17) ifxb6220rm(false,X5,add(P4,Y5)) => add(P4,rm(X5,Y5)) (18) minsort(nil,nil) => nil (19) minsort(add(U5,V5),W5) => ifxb6220minsort(eq(U5,min(add(U5,V5))),add(U5,V5),W5) (20) ifxb6220minsort(true,add(P5,X6),Y6) => add(P5,minsort(rm(P5,X6)@Y6,nil)) (21) ifxb6220minsort(false,add(U6,V6),W6) => minsort(V6,add(U6,W6)) (22) map(J6,nil) => nil (23) map(F7,add(Y7,U7)) => add(F7[Y7],map(F7,U7)) (24) filter(H7,nil) => nil (25) filter(I7,add(P7,X8)) => filter2(I7[P7],I7,P7,X8) (26) filter2(true,Z8,U8,V8) => add(U8,filter(Z8,V8)) (27) filter2(false,I8,P8,X9) => filter(I8,X9) YES