/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: quot(0(),s(V)) -> 0() 4: quot(s(W),s(P)) -> s(quot(minus(W,P),s(P))) 5: log(s(0())) -> 0() 6: log(s(s(X1))) -> s(log(s(quot(X1,s(s(0())))))) 7: _(X1,X2) -> X1 8: _(X1,X2) -> X2 Number of strict rules: 8 Direct POLO(bPol) ... failed. Uncurrying log 1: minus(X,0()) -> X 2: minus(s(Y),s(U)) -> minus(Y,U) 3: quot(0(),s(V)) -> 0() 4: quot(s(W),s(P)) -> s(quot(minus(W,P),s(P))) 5: log^1_s(0()) -> 0() 6: log^1_s(s(X1)) -> s(log^1_s(quot(X1,s(s(0()))))) 7: _(X1,X2) -> X1 8: _(X1,X2) -> X2 9: log(s(_1)) ->= log^1_s(_1) Number of strict rules: 8 Direct POLO(bPol) ... failed. Dependency Pairs: #1: #minus(s(Y),s(U)) -> #minus(Y,U) #2: #log^1_s(s(X1)) -> #log^1_s(quot(X1,s(s(0())))) #3: #log^1_s(s(X1)) -> #quot(X1,s(s(0()))) #4: #log(s(_1)) ->? #log^1_s(_1) #5: #quot(s(W),s(P)) -> #quot(minus(W,P),s(P)) #6: #quot(s(W),s(P)) -> #minus(W,P) Number of SCCs: 3, DPs: 3 SCC { #1 } POLO(Sum)... succeeded. s w: x1 + 1 minus w: 0 #log^1_s w: 0 #log w: 0 _ w: 0 log w: 0 0 w: 0 quot w: 0 #minus w: x1 + x2 #_ w: 0 #quot w: 0 log^1_s w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 2, DPs: 2 SCC { #2 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 #log^1_s w: x1 #log w: 0 _ w: 0 log w: 0 0 w: 1 quot w: x1 + 1 #minus w: 0 #_ w: 0 #quot w: 0 log^1_s w: 0 USABLE RULES: { 1..4 } Removed DPs: #2 Number of SCCs: 1, DPs: 1 SCC { #5 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + 1 #log^1_s w: 0 #log w: 0 _ w: 0 log w: 0 0 w: 0 quot w: 450 #minus w: 0 #_ w: 0 #quot w: x1 log^1_s w: 0 USABLE RULES: { 1..3 } Removed DPs: #5 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: minus(X,0()) -> X 2: minus(s(Y),s(U)) -> minus(Y,U) 3: quot(0(),s(V)) -> 0() 4: quot(s(W),s(P)) -> s(quot(minus(W,P),s(P))) 5: log(s(0())) -> 0() 6: log(s(s(X1))) -> s(log(s(quot(X1,s(s(0())))))) 7: _(X1,X2) -> X1 8: _(X1,X2) -> X2 Number of strict rules: 8 Direct POLO(bPol) ... failed. Uncurrying log 1: minus(X,0()) -> X 2: minus(s(Y),s(U)) -> minus(Y,U) 3: quot(0(),s(V)) -> 0() 4: quot(s(W),s(P)) -> s(quot(minus(W,P),s(P))) 5: log^1_s(0()) -> 0() 6: log^1_s(s(X1)) -> s(log^1_s(quot(X1,s(s(0()))))) 7: _(X1,X2) -> X1 8: _(X1,X2) -> X2 9: log(s(_1)) ->= log^1_s(_1) Number of strict rules: 8 Direct POLO(bPol) ... failed. Dependency Pairs: #1: #minus(s(Y),s(U)) -> #minus(Y,U) #2: #log^1_s(s(X1)) -> #log^1_s(quot(X1,s(s(0())))) #3: #log^1_s(s(X1)) -> #quot(X1,s(s(0()))) #4: #log(s(_1)) ->? #log^1_s(_1) #5: #quot(s(W),s(P)) -> #quot(minus(W,P),s(P)) #6: #quot(s(W),s(P)) -> #minus(W,P) Number of SCCs: 3, DPs: 3 SCC { #1 } POLO(Sum)... succeeded. s w: x1 + 1 minus w: 0 #log^1_s w: 0 #log w: 0 _ w: 0 log w: 0 0 w: 0 quot w: 0 #minus w: x1 + x2 #_ w: 0 #quot w: 0 log^1_s w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 2, DPs: 2 SCC { #2 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 #log^1_s w: x1 #log w: 0 _ w: 0 log w: 0 0 w: 1 quot w: x1 + 1 #minus w: 0 #_ w: 0 #quot w: 0 log^1_s w: 0 USABLE RULES: { 1..4 } Removed DPs: #2 Number of SCCs: 1, DPs: 1 SCC { #5 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + 1 #log^1_s w: 0 #log w: 0 _ w: 0 log w: 0 0 w: 0 quot w: 450 #minus w: 0 #_ w: 0 #quot w: x1 log^1_s w: 0 USABLE RULES: { 1..3 } Removed DPs: #5 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 ******** (7) map(Z1,nil) => nil (8) map(G1,cons(V1,W1)) => cons(G1[V1],map(G1,W1)) (9) filter(J1,nil) => nil (10) filter(F2,cons(Y2,U2)) => filter2(F2[Y2],F2,Y2,U2) (11) filter2(true,H2,W2,P2) => cons(W2,filter(H2,P2)) (12) filter2(false,F3,Y3,U3) => filter(F3,U3) ******** 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) quot(0,s(V)) => 0 (fun quot>0) >>True Checking (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (fun quot>s) (fun quot=quot) 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) quot(0,s(V)) => 0 (fun quot>0) >>True Checking (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (fun quot>s) (fun quot=quot) 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) quot(0,s(V)) => 0 (fun quot>0) >>True Checking (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (fun quot>s) (fun quot=quot) 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 (7) map(Z1,nil) => nil (fun map>nil) >>True Checking (8) map(G1,cons(V1,W1)) => cons(G1[V1],map(G1,W1)) (fun map>cons) (meta G1)[is acc in G1,cons(V1,W1)] [is acc in G1] (meta V1)[is acc in G1,cons(V1,W1)] [is positive in cons(V1,W1)] [is acc in V1] (fun map=map) subterm comparison of args w. LR LR (meta G1)[is acc in G1,cons(V1,W1)] [is acc in G1] (meta W1)[is acc in G1,cons(V1,W1)] [is positive in cons(V1,W1)] [is acc in W1] >>True Checking (9) filter(J1,nil) => nil (fun filter>nil) >>True Checking (10) filter(F2,cons(Y2,U2)) => filter2(F2[Y2],F2,Y2,U2) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (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] (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] (meta U2)[is acc in F2,cons(Y2,U2)] [is positive in cons(Y2,U2)] [is acc in U2] >>True Checking (11) filter2(true,H2,W2,P2) => cons(W2,filter(H2,P2)) (fun filter2>cons) (meta W2)[is acc in true,H2,W2,P2] [is positive in true] [is acc in W2] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta H2)[is acc in true,H2,W2,P2] [is positive in true] [is acc in H2] (meta P2)[is acc in true,H2,W2,P2] [is positive in true] [is acc in P2] >>True Checking (12) filter2(false,F3,Y3,U3) => filter(F3,U3) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta F3)[is acc in false,F3,Y3,U3] [is positive in false] [is acc in F3] (meta U3)[is acc in false,F3,Y3,U3] [is positive in false] [is acc in U3] >>True #SN! ******** Signature ******** 0 : a cons : (c,d) -> d false : b filter : ((c -> b),d) -> d filter2 : (b,(c -> b),c,d) -> d log : a -> a map : ((c -> c),d) -> d minus : (a,a) -> a nil : d quot : (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) quot(0,s(V)) => 0 (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (5) log(s(0)) => 0 (6) log(s(s(X1))) => s(log(s(quot(X1,s(s(0)))))) (7) map(Z1,nil) => nil (8) map(G1,cons(V1,W1)) => cons(G1[V1],map(G1,W1)) (9) filter(J1,nil) => nil (10) filter(F2,cons(Y2,U2)) => filter2(F2[Y2],F2,Y2,U2) (11) filter2(true,H2,W2,P2) => cons(W2,filter(H2,P2)) (12) filter2(false,F3,Y3,U3) => filter(F3,U3) YES