/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(0()) -> true() 2: f(1()) -> false() 3: f(s(X)) -> f(X) 4: if(true(),s(Y),s(U)) -> s(Y) 5: if(false(),s(V),s(W)) -> s(W) 6: g(P,c(X1)) -> c(g(P,X1)) 7: g(Y1,c(U1)) -> g(Y1,if(f(Y1),c(g(s(Y1),U1)),c(U1))) 8: _(X1,X2) -> X1 9: _(X1,X2) -> X2 Number of strict rules: 9 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #g(P,c(X1)) -> #g(P,X1) #2: #g(Y1,c(U1)) -> #g(Y1,if(f(Y1),c(g(s(Y1),U1)),c(U1))) #3: #g(Y1,c(U1)) -> #if(f(Y1),c(g(s(Y1),U1)),c(U1)) #4: #g(Y1,c(U1)) -> #f(Y1) #5: #g(Y1,c(U1)) -> #g(s(Y1),U1) #6: #f(s(X)) -> #f(X) Number of SCCs: 2, DPs: 3 SCC { #6 } POLO(Sum)... succeeded. 1 w: 0 s w: x1 + 1 false w: 0 c w: 0 _ w: 0 true w: 0 f w: 0 0 w: 0 if w: 0 #f w: x1 #g w: 0 #_ w: 0 #if w: 0 g w: 0 USABLE RULES: { } Removed DPs: #6 Number of SCCs: 1, DPs: 2 SCC { #1 #5 } POLO(Sum)... succeeded. 1 w: 0 s w: 1 false w: 0 c w: x1 + 1 _ w: 0 true w: 0 f w: 0 0 w: 0 if w: 0 #f w: 0 #g w: x2 #_ w: 0 #if w: 0 g w: 0 USABLE RULES: { } Removed DPs: #1 #5 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: f(0()) -> true() 2: f(1()) -> false() 3: f(s(X)) -> f(X) 4: if(true(),s(Y),s(U)) -> s(Y) 5: if(false(),s(V),s(W)) -> s(W) 6: g(P,c(X1)) -> c(g(P,X1)) 7: g(Y1,c(U1)) -> g(Y1,if(f(Y1),c(g(s(Y1),U1)),c(U1))) 8: _(X1,X2) -> X1 9: _(X1,X2) -> X2 Number of strict rules: 9 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #g(P,c(X1)) -> #g(P,X1) #2: #g(Y1,c(U1)) -> #g(Y1,if(f(Y1),c(g(s(Y1),U1)),c(U1))) #3: #g(Y1,c(U1)) -> #if(f(Y1),c(g(s(Y1),U1)),c(U1)) #4: #g(Y1,c(U1)) -> #f(Y1) #5: #g(Y1,c(U1)) -> #g(s(Y1),U1) #6: #f(s(X)) -> #f(X) Number of SCCs: 2, DPs: 3 SCC { #6 } POLO(Sum)... succeeded. 1 w: 0 s w: x1 + 1 false w: 0 c w: 0 _ w: 0 true w: 0 f w: 0 0 w: 0 if w: 0 #f w: x1 #g w: 0 #_ w: 0 #if w: 0 g w: 0 USABLE RULES: { } Removed DPs: #6 Number of SCCs: 1, DPs: 2 SCC { #1 #5 } POLO(Sum)... succeeded. 1 w: 0 s w: 1 false w: 0 c w: x1 + 1 _ w: 0 true w: 0 f w: 0 0 w: 0 if w: 0 #f w: 0 #g w: x2 #_ w: 0 #if w: 0 g w: 0 USABLE RULES: { } Removed DPs: #1 #5 Number of SCCs: 0, DPs: 0 >>YES ******** Signature ******** map : ((c -> c),d) -> d nil : d cons : (c,d) -> d filter : ((c -> a),d) -> d filter2 : (a,(c -> a),c,d) -> d true : a false : a ******** Computation rules ******** (8) map(H1,nil) => nil (9) map(I1,cons(P1,X2)) => cons(I1[P1],map(I1,X2)) (10) filter(Z2,nil) => nil (11) filter(G2,cons(V2,W2)) => filter2(G2[V2],G2,V2,W2) (12) filter2(true,J2,X3,Y3) => cons(X3,filter(J2,Y3)) (13) filter2(false,G3,V3,W3) => filter(G3,W3) ******** General Schema criterion ******** Found constructors: 0, 1, c, 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(0) => true (fun f>true) >>True Checking (2) f(1) => false (fun f>false) >>True Checking (3) 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 (4) if(true,s(Y),s(U)) => s(Y) (fun if>s) (meta Y)[is acc in true,s(Y),s(U)] [is positive in true] [is positive in s(Y)] [is acc in Y] >>True Checking (5) if(false,s(V),s(W)) => s(W) (fun if>s) (meta W)[is acc in false,s(V),s(W)] [is positive in false] [is positive in s(V)] [is positive in s(W)] [is acc in W] >>True Checking (6) g(P,c(X1)) => c(g(P,X1)) (fun g>c) (fun g=g) subterm comparison of args w. LR LR (meta P)[is acc in P,c(X1)] [is acc in P] (meta X1)[is acc in P,c(X1)] [is positive in c(X1)] [is acc in X1] >>True Checking (7) g(Y1,c(U1)) => g(Y1,if(f(Y1),c(g(s(Y1),U1)),c(U1))) (fun g=g) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) f(0) => true (fun f>true) >>True Checking (2) f(1) => false (fun f>false) >>True Checking (3) 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 (4) if(true,s(Y),s(U)) => s(Y) (fun if>s) (meta Y)[is acc in true,s(Y),s(U)] [is positive in true] [is positive in s(Y)] [is acc in Y] >>True Checking (5) if(false,s(V),s(W)) => s(W) (fun if>s) (meta W)[is acc in false,s(V),s(W)] [is positive in false] [is positive in s(V)] [is positive in s(W)] [is acc in W] >>True Checking (6) g(P,c(X1)) => c(g(P,X1)) (fun g>c) (fun g=g) subterm comparison of args w. RL RL (meta P)[is acc in P,c(X1)] [is acc in P] (meta X1)[is acc in P,c(X1)] [is positive in c(X1)] [is acc in X1] >>True Checking (7) g(Y1,c(U1)) => g(Y1,if(f(Y1),c(g(s(Y1),U1)),c(U1))) (fun g=g) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) f(0) => true (fun f>true) >>True Checking (2) f(1) => false (fun f>false) >>True Checking (3) 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 (4) if(true,s(Y),s(U)) => s(Y) (fun if>s) (meta Y)[is acc in true,s(Y),s(U)] [is positive in true] [is positive in s(Y)] [is acc in Y] >>True Checking (5) if(false,s(V),s(W)) => s(W) (fun if>s) (meta W)[is acc in false,s(V),s(W)] [is positive in false] [is positive in s(V)] [is positive in s(W)] [is acc in W] >>True Checking (6) g(P,c(X1)) => c(g(P,X1)) (fun g>c) (fun g=g) subterm comparison of args w. Mul Mul (meta P)[is acc in P,c(X1)] [is acc in P] (meta X1)[is acc in P,c(X1)] [is positive in c(X1)] [is acc in X1] >>True Checking (7) g(Y1,c(U1)) => g(Y1,if(f(Y1),c(g(s(Y1),U1)),c(U1))) (fun g=g) 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 (8) map(H1,nil) => nil (fun map>nil) >>True Checking (9) map(I1,cons(P1,X2)) => cons(I1[P1],map(I1,X2)) (fun map>cons) (meta I1)[is acc in I1,cons(P1,X2)] [is acc in I1] (meta P1)[is acc in I1,cons(P1,X2)] [is positive in cons(P1,X2)] [is acc in P1] (fun map=map) subterm comparison of args w. LR LR (meta I1)[is acc in I1,cons(P1,X2)] [is acc in I1] (meta X2)[is acc in I1,cons(P1,X2)] [is positive in cons(P1,X2)] [is acc in X2] >>True Checking (10) filter(Z2,nil) => nil (fun filter>nil) >>True Checking (11) filter(G2,cons(V2,W2)) => filter2(G2[V2],G2,V2,W2) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (meta G2)[is acc in G2,cons(V2,W2)] [is acc in G2] (meta V2)[is acc in G2,cons(V2,W2)] [is positive in cons(V2,W2)] [is acc in V2] (meta G2)[is acc in G2,cons(V2,W2)] [is acc in G2] (meta V2)[is acc in G2,cons(V2,W2)] [is positive in cons(V2,W2)] [is acc in V2] (meta W2)[is acc in G2,cons(V2,W2)] [is positive in cons(V2,W2)] [is acc in W2] >>True Checking (12) filter2(true,J2,X3,Y3) => cons(X3,filter(J2,Y3)) (fun filter2>cons) (meta X3)[is acc in true,J2,X3,Y3] [is positive in true] [is acc in X3] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta J2)[is acc in true,J2,X3,Y3] [is positive in true] [is acc in J2] (meta Y3)[is acc in true,J2,X3,Y3] [is positive in true] [is acc in Y3] >>True Checking (13) filter2(false,G3,V3,W3) => filter(G3,W3) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta G3)[is acc in false,G3,V3,W3] [is positive in false] [is acc in G3] (meta W3)[is acc in false,G3,V3,W3] [is positive in false] [is acc in W3] >>True #SN! ******** Signature ******** 0 : b 1 : b c : b -> b cons : (c,d) -> d f : b -> a false : a filter : ((c -> a),d) -> d filter2 : (a,(c -> a),c,d) -> d g : (b,b) -> b if : (a,b,b) -> b map : ((c -> c),d) -> d nil : d s : b -> b true : a ******** Computation Rules ******** (1) f(0) => true (2) f(1) => false (3) f(s(X)) => f(X) (4) if(true,s(Y),s(U)) => s(Y) (5) if(false,s(V),s(W)) => s(W) (6) g(P,c(X1)) => c(g(P,X1)) (7) g(Y1,c(U1)) => g(Y1,if(f(Y1),c(g(s(Y1),U1)),c(U1))) (8) map(H1,nil) => nil (9) map(I1,cons(P1,X2)) => cons(I1[P1],map(I1,X2)) (10) filter(Z2,nil) => nil (11) filter(G2,cons(V2,W2)) => filter2(G2[V2],G2,V2,W2) (12) filter2(true,J2,X3,Y3) => cons(X3,filter(J2,Y3)) (13) filter2(false,G3,V3,W3) => filter(G3,W3) YES