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