/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, cons, edge, empty, 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) or(true,W) => true (fun or>true) >>True Checking (6) or(false,P) => P (meta P)[is acc in false,P] [is positive in false] [is acc in P] >>True Checking (7) union(empty,X1) => X1 (meta X1)[is acc in empty,X1] [is positive in empty] [is acc in X1] >>True Checking (8) union(edge(V1,W1,U1),Y1) => edge(V1,W1,union(U1,Y1)) (fun union>edge) (meta V1)[is acc in edge(V1,W1,U1),Y1] [is positive in edge(V1,W1,U1)] [is acc in V1] (meta W1)[is acc in edge(V1,W1,U1),Y1] [is positive in edge(V1,W1,U1)] [is acc in W1] (fun union=union) subterm comparison of args w. LR LR (meta U1)[is acc in edge(V1,W1,U1),Y1] [is positive in edge(V1,W1,U1)] [is acc in U1] (meta Y1)[is acc in edge(V1,W1,U1),Y1] [is positive in edge(V1,W1,U1)] [is acc in Y1] >>True Checking (9) reach(X2,Y2,empty,P1) => false (fun reach>false) >>True Checking (10) reach(X3,Y3,edge(W2,P2,V2),U2) => ifxb6220reachxb62201(eq(X3,W2),X3,Y3,edge(W2,P2,V2),U2) (fun reach>ifxb6220reachxb62201) (fun reach>eq) (meta X3)[is acc in X3,Y3,edge(W2,P2,V2),U2] [is acc in X3] (meta W2)[is acc in X3,Y3,edge(W2,P2,V2),U2] [is positive in edge(W2,P2,V2)] [is acc in W2] (meta X3)[is acc in X3,Y3,edge(W2,P2,V2),U2] [is acc in X3] (meta Y3)[is acc in X3,Y3,edge(W2,P2,V2),U2] [is acc in Y3] (fun reach>edge) (meta W2)[is acc in X3,Y3,edge(W2,P2,V2),U2] [is positive in edge(W2,P2,V2)] [is acc in W2] (meta P2)[is acc in X3,Y3,edge(W2,P2,V2),U2] [is positive in edge(W2,P2,V2)] [is acc in P2] (meta V2)[is acc in X3,Y3,edge(W2,P2,V2),U2] [is positive in edge(W2,P2,V2)] [is acc in V2] (meta U2)[is acc in X3,Y3,edge(W2,P2,V2),U2] [is positive in edge(W2,P2,V2)] [is acc in U2] >>True Checking (11) ifxb6220reachxb62201(true,X4,Y4,edge(W3,P3,V3),U3) => ifxb6220reachxb62202(eq(Y4,P3),X4,Y4,edge(W3,P3,V3),U3) (fun ifxb6220reachxb62201>ifxb6220reachxb62202) (fun ifxb6220reachxb62201>eq) (meta Y4)[is acc in true,X4,Y4,edge(W3,P3,V3),U3] [is positive in true] [is acc in Y4] (meta P3)[is acc in true,X4,Y4,edge(W3,P3,V3),U3] [is positive in true] [is positive in edge(W3,P3,V3)] [is acc in P3] (meta X4)[is acc in true,X4,Y4,edge(W3,P3,V3),U3] [is positive in true] [is acc in X4] (meta Y4)[is acc in true,X4,Y4,edge(W3,P3,V3),U3] [is positive in true] [is acc in Y4] (fun ifxb6220reachxb62201>edge) (meta W3)[is acc in true,X4,Y4,edge(W3,P3,V3),U3] [is positive in true] [is positive in edge(W3,P3,V3)] [is acc in W3] (meta P3)[is acc in true,X4,Y4,edge(W3,P3,V3),U3] [is positive in true] [is positive in edge(W3,P3,V3)] [is acc in P3] (meta V3)[is acc in true,X4,Y4,edge(W3,P3,V3),U3] [is positive in true] [is positive in edge(W3,P3,V3)] [is acc in V3] (meta U3)[is acc in true,X4,Y4,edge(W3,P3,V3),U3] [is positive in true] [is positive in edge(W3,P3,V3)] [is acc in U3] >>True Checking (12) ifxb6220reachxb62201(false,X5,Y5,edge(W4,P4,V4),U4) => reach(X5,Y5,V4,edge(W4,P4,U4)) (fun ifxb6220reachxb62201>reach) (meta X5)[is acc in false,X5,Y5,edge(W4,P4,V4),U4] [is positive in false] [is acc in X5] (meta Y5)[is acc in false,X5,Y5,edge(W4,P4,V4),U4] [is positive in false] [is acc in Y5] (meta V4)[is acc in false,X5,Y5,edge(W4,P4,V4),U4] [is positive in false] [is positive in edge(W4,P4,V4)] [is acc in V4] (fun ifxb6220reachxb62201>edge) (meta W4)[is acc in false,X5,Y5,edge(W4,P4,V4),U4] [is positive in false] [is positive in edge(W4,P4,V4)] [is acc in W4] (meta P4)[is acc in false,X5,Y5,edge(W4,P4,V4),U4] [is positive in false] [is positive in edge(W4,P4,V4)] [is acc in P4] (meta U4)[is acc in false,X5,Y5,edge(W4,P4,V4),U4] [is positive in false] [is positive in edge(W4,P4,V4)] [is acc in U4] >>True Checking (13) ifxb6220reachxb62202(true,X6,Y6,edge(W5,P5,V5),U5) => true (fun ifxb6220reachxb62202>true) >>True Checking (14) ifxb6220reachxb62202(false,X7,Y7,edge(W6,P6,V6),U6) => or(reach(X7,Y7,V6,U6),reach(P6,Y7,union(V6,U6),empty)) (fun ifxb6220reachxb62202>or) (fun ifxb6220reachxb62202>reach) (meta X7)[is acc in false,X7,Y7,edge(W6,P6,V6),U6] [is positive in false] [is acc in X7] (meta Y7)[is acc in false,X7,Y7,edge(W6,P6,V6),U6] [is positive in false] [is acc in Y7] (meta V6)[is acc in false,X7,Y7,edge(W6,P6,V6),U6] [is positive in false] [is positive in edge(W6,P6,V6)] [is acc in V6] (meta U6)[is acc in false,X7,Y7,edge(W6,P6,V6),U6] [is positive in false] [is positive in edge(W6,P6,V6)] [is acc in U6] (fun ifxb6220reachxb62202>reach) (meta P6)[is acc in false,X7,Y7,edge(W6,P6,V6),U6] [is positive in false] [is positive in edge(W6,P6,V6)] [is acc in P6] (meta Y7)[is acc in false,X7,Y7,edge(W6,P6,V6),U6] [is positive in false] [is acc in Y7] (fun ifxb6220reachxb62202>union) (meta V6)[is acc in false,X7,Y7,edge(W6,P6,V6),U6] [is positive in false] [is positive in edge(W6,P6,V6)] [is acc in V6] (meta U6)[is acc in false,X7,Y7,edge(W6,P6,V6),U6] [is positive in false] [is positive in edge(W6,P6,V6)] [is acc in U6] (fun ifxb6220reachxb62202>empty) >>True Checking (15) map(G7,nil) => nil (fun map>nil) >>True Checking (16) map(H7,cons(W7,P7)) => cons(H7[W7],map(H7,P7)) (fun map>cons) (meta H7)[is acc in H7,cons(W7,P7)] [is acc in H7] (meta W7)[is acc in H7,cons(W7,P7)] [is positive in cons(W7,P7)] [is acc in W7] (fun map=map) subterm comparison of args w. LR LR (meta H7)[is acc in H7,cons(W7,P7)] [is acc in H7] (meta P7)[is acc in H7,cons(W7,P7)] [is positive in cons(W7,P7)] [is acc in P7] >>True Checking (17) filter(F8,nil) => nil (fun filter>nil) >>True Checking (18) filter(Z8,cons(U8,V8)) => filter2(Z8[U8],Z8,U8,V8) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (meta Z8)[is acc in Z8,cons(U8,V8)] [is acc in Z8] (meta U8)[is acc in Z8,cons(U8,V8)] [is positive in cons(U8,V8)] [is acc in U8] (meta Z8)[is acc in Z8,cons(U8,V8)] [is acc in Z8] (meta U8)[is acc in Z8,cons(U8,V8)] [is positive in cons(U8,V8)] [is acc in U8] (meta V8)[is acc in Z8,cons(U8,V8)] [is positive in cons(U8,V8)] [is acc in V8] >>True Checking (19) filter2(true,I8,P8,X9) => cons(P8,filter(I8,X9)) (fun filter2>cons) (meta P8)[is acc in true,I8,P8,X9] [is positive in true] [is acc in P8] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta I8)[is acc in true,I8,P8,X9] [is positive in true] [is acc in I8] (meta X9)[is acc in true,I8,P8,X9] [is positive in true] [is acc in X9] >>True Checking (20) filter2(false,Z9,U9,V9) => filter(Z9,V9) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta Z9)[is acc in false,Z9,U9,V9] [is positive in false] [is acc in Z9] (meta V9)[is acc in false,Z9,U9,V9] [is positive in false] [is acc in V9] >>True #SN! ******** Signature ******** 0 : a cons : (d,e) -> e edge : (a,a,b) -> b empty : b eq : (a,a) -> c false : c filter : ((d -> c),e) -> e filter2 : (c,(d -> c),d,e) -> e ifxb6220reachxb62201 : (c,a,a,b,b) -> c ifxb6220reachxb62202 : (c,a,a,b,b) -> c map : ((d -> d),e) -> e nil : e or : (c,c) -> c reach : (a,a,b,b) -> c s : a -> a true : c union : (b,b) -> b ******** 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) or(true,W) => true (6) or(false,P) => P (7) union(empty,X1) => X1 (8) union(edge(V1,W1,U1),Y1) => edge(V1,W1,union(U1,Y1)) (9) reach(X2,Y2,empty,P1) => false (10) reach(X3,Y3,edge(W2,P2,V2),U2) => ifxb6220reachxb62201(eq(X3,W2),X3,Y3,edge(W2,P2,V2),U2) (11) ifxb6220reachxb62201(true,X4,Y4,edge(W3,P3,V3),U3) => ifxb6220reachxb62202(eq(Y4,P3),X4,Y4,edge(W3,P3,V3),U3) (12) ifxb6220reachxb62201(false,X5,Y5,edge(W4,P4,V4),U4) => reach(X5,Y5,V4,edge(W4,P4,U4)) (13) ifxb6220reachxb62202(true,X6,Y6,edge(W5,P5,V5),U5) => true (14) ifxb6220reachxb62202(false,X7,Y7,edge(W6,P6,V6),U6) => or(reach(X7,Y7,V6,U6),reach(P6,Y7,union(V6,U6),empty)) (15) map(G7,nil) => nil (16) map(H7,cons(W7,P7)) => cons(H7[W7],map(H7,P7)) (17) filter(F8,nil) => nil (18) filter(Z8,cons(U8,V8)) => filter2(Z8[U8],Z8,U8,V8) (19) filter2(true,I8,P8,X9) => cons(P8,filter(I8,X9)) (20) filter2(false,Z9,U9,V9) => filter(Z9,V9) YES