/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: half(0()) -> 0() 2: half(s(0())) -> 0() 3: half(s(s(X))) -> s(half(X)) 4: bits(0()) -> 0() 5: bits(s(Y)) -> s(bits(half(s(Y)))) 6: _(X1,X2) -> X1 7: _(X1,X2) -> X2 Number of strict rules: 7 Direct POLO(bPol) ... removes: 4 7 6 s w: x1 _ w: 2 * x1 + 2 * x2 + 1 half w: x1 0 w: 2998 bits w: x1 + 536 Number of strict rules: 4 Direct POLO(bPol) ... failed. Uncurrying half 1: half^1_0() -> 0() 2: half^1_s(0()) -> 0() 3: half^1_s(s(X)) -> s(half(X)) 5: bits(s(Y)) -> s(bits(half^1_s(Y))) 8: half(0()) ->= half^1_0() 9: half(s(_1)) ->= half^1_s(_1) Number of strict rules: 4 Direct POLO(bPol) ... removes: 9 s w: x1 + 1184 _ w: x1 + x2 half^1_s w: x1 half w: x1 0 w: 610 half^1_0 w: 610 bits w: x1 + 1847 Number of strict rules: 4 Direct POLO(bPol) ... removes: 8 1 3 5 2 s w: x1 + 1184 _ w: x1 + x2 half^1_s w: x1 + 3 half w: x1 + 2 0 w: 608 half^1_0 w: 609 bits w: 2 * x1 + 1847 Number of strict rules: 0 ... Input TRS: 1: half(0()) -> 0() 2: half(s(0())) -> 0() 3: half(s(s(X))) -> s(half(X)) 4: bits(0()) -> 0() 5: bits(s(Y)) -> s(bits(half(s(Y)))) 6: _(X1,X2) -> X1 7: _(X1,X2) -> X2 Number of strict rules: 7 Direct POLO(bPol) ... removes: 4 7 6 s w: x1 _ w: 2 * x1 + 2 * x2 + 1 half w: x1 0 w: 2998 bits w: x1 + 536 Number of strict rules: 4 Direct POLO(bPol) ... failed. Uncurrying half 1: half^1_0() -> 0() 2: half^1_s(0()) -> 0() 3: half^1_s(s(X)) -> s(half(X)) 5: bits(s(Y)) -> s(bits(half^1_s(Y))) 8: half(0()) ->= half^1_0() 9: half(s(_1)) ->= half^1_s(_1) Number of strict rules: 4 Direct POLO(bPol) ... removes: 9 s w: x1 + 1184 _ w: x1 + x2 half^1_s w: x1 half w: x1 0 w: 610 half^1_0 w: 610 bits w: x1 + 1847 Number of strict rules: 4 Direct POLO(bPol) ... removes: 8 1 3 5 2 s w: x1 + 1184 _ w: x1 + x2 half^1_s w: x1 + 3 half w: x1 + 2 0 w: 608 half^1_0 w: 609 bits w: 2 * x1 + 1847 Number of strict rules: 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 ******** (6) map(G,nil) => nil (7) map(H,cons(W,P)) => cons(H[W],map(H,P)) (8) filter(F1,nil) => nil (9) filter(Z1,cons(U1,V1)) => filter2(Z1[U1],Z1,U1,V1) (10) filter2(true,I1,P1,X2) => cons(P1,filter(I1,X2)) (11) filter2(false,Z2,U2,V2) => filter(Z2,V2) ******** 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) half(0) => 0 (fun half>0) >>True Checking (2) half(s(0)) => 0 (fun half>0) >>True Checking (3) half(s(s(X))) => s(half(X)) (fun half>s) (fun half=half) subterm comparison of args w. LR LR (meta X)[is acc in s(s(X))] [is positive in s(s(X))] [is positive in s(X)] [is acc in X] >>True Checking (4) bits(0) => 0 (fun bits>0) >>True Checking (5) bits(s(Y)) => s(bits(half(s(Y)))) (fun bits>s) (fun bits=bits) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) half(0) => 0 (fun half>0) >>True Checking (2) half(s(0)) => 0 (fun half>0) >>True Checking (3) half(s(s(X))) => s(half(X)) (fun half>s) (fun half=half) subterm comparison of args w. RL RL (meta X)[is acc in s(s(X))] [is positive in s(s(X))] [is positive in s(X)] [is acc in X] >>True Checking (4) bits(0) => 0 (fun bits>0) >>True Checking (5) bits(s(Y)) => s(bits(half(s(Y)))) (fun bits>s) (fun bits=bits) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) half(0) => 0 (fun half>0) >>True Checking (2) half(s(0)) => 0 (fun half>0) >>True Checking (3) half(s(s(X))) => s(half(X)) (fun half>s) (fun half=half) subterm comparison of args w. Mul Mul (meta X)[is acc in s(s(X))] [is positive in s(s(X))] [is positive in s(X)] [is acc in X] >>True Checking (4) bits(0) => 0 (fun bits>0) >>True Checking (5) bits(s(Y)) => s(bits(half(s(Y)))) (fun bits>s) (fun bits=bits) 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 (6) map(G,nil) => nil (fun map>nil) >>True Checking (7) map(H,cons(W,P)) => cons(H[W],map(H,P)) (fun map>cons) (meta H)[is acc in H,cons(W,P)] [is acc in H] (meta W)[is acc in H,cons(W,P)] [is positive in cons(W,P)] [is acc in W] (fun map=map) subterm comparison of args w. LR LR (meta H)[is acc in H,cons(W,P)] [is acc in H] (meta P)[is acc in H,cons(W,P)] [is positive in cons(W,P)] [is acc in P] >>True Checking (8) filter(F1,nil) => nil (fun filter>nil) >>True Checking (9) filter(Z1,cons(U1,V1)) => filter2(Z1[U1],Z1,U1,V1) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (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] (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] (meta V1)[is acc in Z1,cons(U1,V1)] [is positive in cons(U1,V1)] [is acc in V1] >>True Checking (10) filter2(true,I1,P1,X2) => cons(P1,filter(I1,X2)) (fun filter2>cons) (meta P1)[is acc in true,I1,P1,X2] [is positive in true] [is acc in P1] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta I1)[is acc in true,I1,P1,X2] [is positive in true] [is acc in I1] (meta X2)[is acc in true,I1,P1,X2] [is positive in true] [is acc in X2] >>True Checking (11) filter2(false,Z2,U2,V2) => filter(Z2,V2) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta Z2)[is acc in false,Z2,U2,V2] [is positive in false] [is acc in Z2] (meta V2)[is acc in false,Z2,U2,V2] [is positive in false] [is acc in V2] >>True #SN! ******** Signature ******** 0 : a bits : a -> a cons : (c,d) -> d false : b filter : ((c -> b),d) -> d filter2 : (b,(c -> b),c,d) -> d half : a -> a map : ((c -> c),d) -> d nil : d s : a -> a true : b ******** Computation Rules ******** (1) half(0) => 0 (2) half(s(0)) => 0 (3) half(s(s(X))) => s(half(X)) (4) bits(0) => 0 (5) bits(s(Y)) => s(bits(half(s(Y)))) (6) map(G,nil) => nil (7) map(H,cons(W,P)) => cons(H[W],map(H,P)) (8) filter(F1,nil) => nil (9) filter(Z1,cons(U1,V1)) => filter2(Z1[U1],Z1,U1,V1) (10) filter2(true,I1,P1,X2) => cons(P1,filter(I1,X2)) (11) filter2(false,Z2,U2,V2) => filter(Z2,V2) YES