/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: f(s(X)) -> f(X) 2: g(cons(0(),Y)) -> g(Y) 3: g(cons(s(U),V)) -> s(U) 4: h(cons(W,P)) -> h(g(cons(W,P))) 5: _(X1,X2) -> X1 6: _(X1,X2) -> X2 Number of strict rules: 6 Direct POLO(bPol) ... removes: 1 3 5 6 2 h w: x1 + 8855 s w: 2 * x1 + 8366 _ w: 2 * x1 + 2 * x2 + 1 f w: 2 * x1 0 w: 1 cons w: 2 * x1 + x2 + 5854 g w: x1 Number of strict rules: 1 Direct POLO(bPol) ... failed. Uncurrying h 4: h^1_cons(W,P) -> h^1_g(cons(W,P)) 7: h(cons(_1,_2)) ->= h^1_cons(_1,_2) 8: h(g(_1)) ->= h^1_g(_1) Number of strict rules: 1 Direct POLO(bPol) ... removes: 4 8 7 h w: x1 + 3 s w: x1 h^1_g w: x1 _ w: x1 + x2 f w: x1 0 w: 0 cons w: 2 * x1 + x2 + 1 g w: 2 * x1 + 1 h^1_cons w: 2 * x1 + x2 + 3 Number of strict rules: 0 ... Input TRS: 1: f(s(X)) -> f(X) 2: g(cons(0(),Y)) -> g(Y) 3: g(cons(s(U),V)) -> s(U) 4: h(cons(W,P)) -> h(g(cons(W,P))) 5: _(X1,X2) -> X1 6: _(X1,X2) -> X2 Number of strict rules: 6 Direct POLO(bPol) ... removes: 1 3 5 6 2 h w: x1 + 8855 s w: 2 * x1 + 8366 _ w: 2 * x1 + 2 * x2 + 1 f w: 2 * x1 0 w: 1 cons w: 2 * x1 + x2 + 5854 g w: x1 Number of strict rules: 1 Direct POLO(bPol) ... failed. Uncurrying h 4: h^1_cons(W,P) -> h^1_g(cons(W,P)) 7: h(cons(_1,_2)) ->= h^1_cons(_1,_2) 8: h(g(_1)) ->= h^1_g(_1) Number of strict rules: 1 Direct POLO(bPol) ... removes: 4 8 7 h w: x1 + 3 s w: x1 h^1_g w: x1 _ w: x1 + x2 f w: x1 0 w: 0 cons w: 2 * x1 + x2 + 1 g w: 2 * x1 + 1 h^1_cons w: 2 * x1 + x2 + 3 Number of strict rules: 0 >>YES ******** Signature ******** map : ((d -> d),d) -> d nil : d cons : (d,d) -> d filter : ((d -> c),d) -> d filter2 : (c,(d -> c),d,d) -> d true : c false : c ******** Computation rules ******** (5) map(F1,nil) => nil (6) map(Z1,cons(U1,V1)) => cons(Z1[U1],map(Z1,V1)) (7) filter(I1,nil) => nil (8) filter(J1,cons(X2,Y2)) => filter2(J1[X2],J1,X2,Y2) (9) filter2(true,G2,V2,W2) => cons(V2,filter(G2,W2)) (10) filter2(false,J2,X3,Y3) => filter(J2,Y3) ******** 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) f(s(X)) => f(X) (fun f=f) subterm comparison of args w. LR LR (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] >>True Checking (2) g(cons(0,Y)) => g(Y) (fun g=g) subterm comparison of args w. LR LR (meta Y)[is acc in cons(0,Y)] [is positive in cons(0,Y)] [is acc in Y] >>True Checking (3) g(cons(s(U),V)) => s(U) (fun g>s) (meta U)[is acc in cons(s(U),V)] [is positive in cons(s(U),V)] [is positive in s(U)] [is acc in U] >>True Checking (4) h(cons(W,P)) => h(g(cons(W,P))) (fun h=h) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) f(s(X)) => f(X) (fun f=f) subterm comparison of args w. RL RL (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] >>True Checking (2) g(cons(0,Y)) => g(Y) (fun g=g) subterm comparison of args w. RL RL (meta Y)[is acc in cons(0,Y)] [is positive in cons(0,Y)] [is acc in Y] >>True Checking (3) g(cons(s(U),V)) => s(U) (fun g>s) (meta U)[is acc in cons(s(U),V)] [is positive in cons(s(U),V)] [is positive in s(U)] [is acc in U] >>True Checking (4) h(cons(W,P)) => h(g(cons(W,P))) (fun h=h) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) f(s(X)) => f(X) (fun f=f) subterm comparison of args w. Mul Mul (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] >>True Checking (2) g(cons(0,Y)) => g(Y) (fun g=g) subterm comparison of args w. Mul Mul (meta Y)[is acc in cons(0,Y)] [is positive in cons(0,Y)] [is acc in Y] >>True Checking (3) g(cons(s(U),V)) => s(U) (fun g>s) (meta U)[is acc in cons(s(U),V)] [is positive in cons(s(U),V)] [is positive in s(U)] [is acc in U] >>True Checking (4) h(cons(W,P)) => h(g(cons(W,P))) (fun h=h) 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 (5) map(F1,nil) => nil (fun map>nil) >>True Checking (6) map(Z1,cons(U1,V1)) => cons(Z1[U1],map(Z1,V1)) (fun map>cons) (meta Z1)[is acc in Z1,cons(U1,V1)] [is acc in Z1] (meta U1)[is acc in Z1,cons(U1,V1)] [is positive in cons(U1,V1)] [is acc in U1] (fun map=map) subterm comparison of args w. LR LR (meta Z1)[is acc in Z1,cons(U1,V1)] [is acc in Z1] (meta V1)[is acc in Z1,cons(U1,V1)] [is positive in cons(U1,V1)] [is acc in V1] >>True Checking (7) filter(I1,nil) => nil (fun filter>nil) >>True Checking (8) filter(J1,cons(X2,Y2)) => filter2(J1[X2],J1,X2,Y2) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (meta J1)[is acc in J1,cons(X2,Y2)] [is acc in J1] (meta X2)[is acc in J1,cons(X2,Y2)] [is positive in cons(X2,Y2)] [is acc in X2] (meta J1)[is acc in J1,cons(X2,Y2)] [is acc in J1] (meta X2)[is acc in J1,cons(X2,Y2)] [is positive in cons(X2,Y2)] [is acc in X2] (meta Y2)[is acc in J1,cons(X2,Y2)] [is positive in cons(X2,Y2)] [is acc in Y2] >>True Checking (9) filter2(true,G2,V2,W2) => cons(V2,filter(G2,W2)) (fun filter2>cons) (meta V2)[is acc in true,G2,V2,W2] [is positive in true] [is acc in V2] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta G2)[is acc in true,G2,V2,W2] [is positive in true] [is acc in G2] (meta W2)[is acc in true,G2,V2,W2] [is positive in true] [is acc in W2] >>True Checking (10) filter2(false,J2,X3,Y3) => filter(J2,Y3) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta J2)[is acc in false,J2,X3,Y3] [is positive in false] [is acc in J2] (meta Y3)[is acc in false,J2,X3,Y3] [is positive in false] [is acc in Y3] >>True #SN! ******** Signature ******** 0 : d cons : (d,d) -> d f : d -> a false : c filter : ((d -> c),d) -> d filter2 : (c,(d -> c),d,d) -> d g : d -> d h : d -> b map : ((d -> d),d) -> d nil : d s : d -> d true : c ******** Computation Rules ******** (1) f(s(X)) => f(X) (2) g(cons(0,Y)) => g(Y) (3) g(cons(s(U),V)) => s(U) (4) h(cons(W,P)) => h(g(cons(W,P))) (5) map(F1,nil) => nil (6) map(Z1,cons(U1,V1)) => cons(Z1[U1],map(Z1,V1)) (7) filter(I1,nil) => nil (8) filter(J1,cons(X2,Y2)) => filter2(J1[X2],J1,X2,Y2) (9) filter2(true,G2,V2,W2) => cons(V2,filter(G2,W2)) (10) filter2(false,J2,X3,Y3) => filter(J2,Y3) YES