/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/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(W,0()) -> W 2: minus(s(P),s(X1)) -> minus(P,X1) 3: div(0(),s(Y1)) -> 0() 4: div(s(U1),s(V1)) -> s(div(minus(U1,V1),s(V1))) 5: _(X1,X2) -> X1 6: _(X1,X2) -> X2 Number of strict rules: 6 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #minus(s(P),s(X1)) -> #minus(P,X1) #2: #div(s(U1),s(V1)) -> #div(minus(U1,V1),s(V1)) #3: #div(s(U1),s(V1)) -> #minus(U1,V1) Number of SCCs: 2, DPs: 2 SCC { #1 } POLO(Sum)... succeeded. #div w: 0 s w: x1 + 1 minus w: 0 div w: 0 _ w: 0 0 w: 0 #minus w: x1 + x2 #_ w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 1, DPs: 1 SCC { #2 } POLO(Sum)... succeeded. #div w: x1 s w: x1 + 2 minus w: x1 + 1 div w: 0 _ w: 0 0 w: 1 #minus w: 0 #_ w: 0 USABLE RULES: { 1 2 } Removed DPs: #2 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: minus(W,0()) -> W 2: minus(s(P),s(X1)) -> minus(P,X1) 3: div(0(),s(Y1)) -> 0() 4: div(s(U1),s(V1)) -> s(div(minus(U1,V1),s(V1))) 5: _(X1,X2) -> X1 6: _(X1,X2) -> X2 Number of strict rules: 6 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #minus(s(P),s(X1)) -> #minus(P,X1) #2: #div(s(U1),s(V1)) -> #div(minus(U1,V1),s(V1)) #3: #div(s(U1),s(V1)) -> #minus(U1,V1) Number of SCCs: 2, DPs: 2 SCC { #1 } POLO(Sum)... succeeded. #div w: 0 s w: x1 + 1 minus w: 0 div w: 0 _ w: 0 0 w: 0 #minus w: x1 + x2 #_ w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 1, DPs: 1 SCC { #2 } POLO(Sum)... succeeded. #div w: x1 s w: x1 + 2 minus w: x1 + 1 div w: 0 _ w: 0 0 w: 1 #minus w: 0 #_ w: 0 USABLE RULES: { 1 2 } Removed DPs: #2 Number of SCCs: 0, DPs: 0 >>YES ******** Signature ******** map : ((a -> a),b) -> b nil : b cons : (a,b) -> b ******** Computation rules ******** (1) map(F,nil) => nil (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V)) ******** General Schema criterion ******** Found constructors: 0, cons, nil, s Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK Checking (1) map(F,nil) => nil (fun map>nil) >>True Checking (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V)) (fun map>cons) (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] (meta U)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in U] (fun map=map) subterm comparison of args w. LR LR (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] (meta V)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in V] >>True Checking (3) minus(W,0) => W (meta W)[is acc in W,0] [is acc in W] >>True Checking (4) minus(s(P),s(X1)) => minus(P,X1) (fun minus=minus) subterm comparison of args w. LR LR (meta P)[is acc in s(P),s(X1)] [is positive in s(P)] [is acc in P] (meta X1)[is acc in s(P),s(X1)] [is positive in s(P)] [is positive in s(X1)] [is acc in X1] >>True Checking (5) div(0,s(Y1)) => 0 (fun div>0) >>True Checking (6) div(s(U1),s(V1)) => s(div(minus(U1,V1),s(V1))) (fun div>s) (fun div=div) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) map(F,nil) => nil (fun map>nil) >>True Checking (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V)) (fun map>cons) (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] (meta U)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in U] (fun map=map) subterm comparison of args w. RL RL (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] (meta V)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in V] >>True Checking (3) minus(W,0) => W (meta W)[is acc in W,0] [is acc in W] >>True Checking (4) minus(s(P),s(X1)) => minus(P,X1) (fun minus=minus) subterm comparison of args w. RL RL (meta P)[is acc in s(P),s(X1)] [is positive in s(P)] [is acc in P] (meta X1)[is acc in s(P),s(X1)] [is positive in s(P)] [is positive in s(X1)] [is acc in X1] >>True Checking (5) div(0,s(Y1)) => 0 (fun div>0) >>True Checking (6) div(s(U1),s(V1)) => s(div(minus(U1,V1),s(V1))) (fun div>s) (fun div=div) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) map(F,nil) => nil (fun map>nil) >>True Checking (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V)) (fun map>cons) (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] (meta U)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in U] (fun map=map) subterm comparison of args w. Mul Mul (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] (meta V)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in V] >>True Checking (3) minus(W,0) => W (meta W)[is acc in W,0] [is acc in W] >>True Checking (4) minus(s(P),s(X1)) => minus(P,X1) (fun minus=minus) subterm comparison of args w. Mul Mul (meta P)[is acc in s(P),s(X1)] [is positive in s(P)] [is acc in P] (meta X1)[is acc in s(P),s(X1)] [is positive in s(P)] [is positive in s(X1)] [is acc in X1] >>True Checking (5) div(0,s(Y1)) => 0 (fun div>0) >>True Checking (6) div(s(U1),s(V1)) => s(div(minus(U1,V1),s(V1))) (fun div>s) (fun div=div) subterm comparison of args w. Mul Mul >>False Found constructors: nil, cons Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK Checking (1) map(F,nil) => nil (fun map>nil) >>True Checking (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V)) (fun map>cons) (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] (meta U)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in U] (fun map=map) subterm comparison of args w. LR LR (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] (meta V)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in V] >>True #SN! ******** Signature ******** 0 : c cons : (a,b) -> b div : (c,c) -> c map : ((a -> a),b) -> b minus : (c,c) -> c nil : b s : c -> c ******** Computation Rules ******** (1) map(F,nil) => nil (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V)) (3) minus(W,0) => W (4) minus(s(P),s(X1)) => minus(P,X1) (5) div(0,s(Y1)) => 0 (6) div(s(U1),s(V1)) => s(div(minus(U1,V1),s(V1))) YES