/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: intlist(nil()) -> nil() 2: intlist(cons(X,Y)) -> cons(s(X),intlist(Y)) 3: int(0(),0()) -> cons(0(),nil()) 4: int(0(),s(U)) -> cons(0(),int(s(0()),s(U))) 5: int(s(V),0()) -> nil() 6: int(s(W),s(P)) -> intlist(int(W,P)) 7: _(X1,X2) -> X1 8: _(X1,X2) -> X2 Number of strict rules: 8 Direct POLO(bPol) ... removes: 8 3 5 7 s w: x1 _ w: x1 + 2 * x2 + 1 0 w: 0 nil w: 5921 intlist w: x1 int w: x1 + x2 + 6783 cons w: x1 + x2 Number of strict rules: 4 Direct POLO(bPol) ... removes: 1 s w: 2 * x1 _ w: x1 + 2 * x2 + 1 0 w: 0 nil w: 1 intlist w: 2 * x1 int w: x1 + x2 cons w: x1 + x2 Number of strict rules: 3 Direct POLO(bPol) ... failed. Uncurrying int 2: intlist(cons(X,Y)) -> cons(s(X),intlist(Y)) 4: int^1_0(s(U)) -> cons(0(),int^1_s(0(),s(U))) 6: int^1_s(W,s(P)) -> intlist(int(W,P)) 9: int(0(),_1) ->= int^1_0(_1) 10: int(s(_1),_2) ->= int^1_s(_1,_2) Number of strict rules: 3 Direct POLO(bPol) ... removes: 10 int^1_0 w: 2 * x1 + 1889 s w: 2 * x1 + 1889 _ w: x1 + x2 0 w: 0 nil w: 0 intlist w: 2 * x1 int w: x1 + 2 * x2 + 1889 cons w: x1 + x2 + 1889 int^1_s w: 2 * x1 + 2 * x2 Number of strict rules: 3 Direct POLO(bPol) ... failed. Dependency Pairs: #1: #intlist(cons(X,Y)) -> #intlist(Y) #2: #int^1_s(W,s(P)) -> #intlist(int(W,P)) #3: #int^1_s(W,s(P)) -> #int(W,P) #4: #int(0(),_1) ->? #int^1_0(_1) #5: #int^1_0(s(U)) -> #int^1_s(0(),s(U)) Number of SCCs: 2, DPs: 4 SCC { #1 } POLO(Sum)... succeeded. int^1_0 w: 0 #intlist w: x1 s w: 0 _ w: 0 0 w: 0 nil w: 0 intlist w: 0 #int^1_0 w: 0 int w: 0 cons w: x2 + 1 int^1_s w: 0 #int^1_s w: 0 #int w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 1, DPs: 3 SCC { #3..5 } POLO(Sum)... succeeded. int^1_0 w: 0 #intlist w: 0 s w: x1 + 3 _ w: 0 0 w: 1 nil w: 0 intlist w: 0 #int^1_0 w: x1 + 1 int w: 0 cons w: 1 int^1_s w: 0 #int^1_s w: x2 #int w: x2 + 2 USABLE RULES: { } Removed DPs: #3..5 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: intlist(nil()) -> nil() 2: intlist(cons(X,Y)) -> cons(s(X),intlist(Y)) 3: int(0(),0()) -> cons(0(),nil()) 4: int(0(),s(U)) -> cons(0(),int(s(0()),s(U))) 5: int(s(V),0()) -> nil() 6: int(s(W),s(P)) -> intlist(int(W,P)) 7: _(X1,X2) -> X1 8: _(X1,X2) -> X2 Number of strict rules: 8 Direct POLO(bPol) ... removes: 8 3 5 7 s w: x1 _ w: x1 + 2 * x2 + 1 0 w: 0 nil w: 5921 intlist w: x1 int w: x1 + x2 + 6783 cons w: x1 + x2 Number of strict rules: 4 Direct POLO(bPol) ... removes: 1 s w: 2 * x1 _ w: x1 + 2 * x2 + 1 0 w: 0 nil w: 1 intlist w: 2 * x1 int w: x1 + x2 cons w: x1 + x2 Number of strict rules: 3 Direct POLO(bPol) ... failed. Uncurrying int 2: intlist(cons(X,Y)) -> cons(s(X),intlist(Y)) 4: int^1_0(s(U)) -> cons(0(),int^1_s(0(),s(U))) 6: int^1_s(W,s(P)) -> intlist(int(W,P)) 9: int(0(),_1) ->= int^1_0(_1) 10: int(s(_1),_2) ->= int^1_s(_1,_2) Number of strict rules: 3 Direct POLO(bPol) ... removes: 10 int^1_0 w: 2 * x1 + 1889 s w: 2 * x1 + 1889 _ w: x1 + x2 0 w: 0 nil w: 0 intlist w: 2 * x1 int w: x1 + 2 * x2 + 1889 cons w: x1 + x2 + 1889 int^1_s w: 2 * x1 + 2 * x2 Number of strict rules: 3 Direct POLO(bPol) ... failed. Dependency Pairs: #1: #intlist(cons(X,Y)) -> #intlist(Y) #2: #int^1_s(W,s(P)) -> #intlist(int(W,P)) #3: #int^1_s(W,s(P)) -> #int(W,P) #4: #int(0(),_1) ->? #int^1_0(_1) #5: #int^1_0(s(U)) -> #int^1_s(0(),s(U)) Number of SCCs: 2, DPs: 4 SCC { #1 } POLO(Sum)... succeeded. int^1_0 w: 0 #intlist w: x1 s w: 0 _ w: 0 0 w: 0 nil w: 0 intlist w: 0 #int^1_0 w: 0 int w: 0 cons w: x2 + 1 int^1_s w: 0 #int^1_s w: 0 #int w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 1, DPs: 3 SCC { #3..5 } POLO(Sum)... succeeded. int^1_0 w: 0 #intlist w: 0 s w: x1 + 3 _ w: 0 0 w: 1 nil w: 0 intlist w: 0 #int^1_0 w: x1 + 1 int w: 0 cons w: 1 int^1_s w: 0 #int^1_s w: x2 #int w: x2 + 2 USABLE RULES: { } Removed DPs: #3..5 Number of SCCs: 0, DPs: 0 >>YES ******** Signature ******** map : ((b -> b),c) -> c nil : c cons : (b,c) -> c filter : ((b -> a),c) -> c filter2 : (a,(b -> a),b,c) -> c true : a false : a ******** Computation rules ******** (7) map(F1,nil) => nil (8) map(Z1,cons(U1,V1)) => cons(Z1[U1],map(Z1,V1)) (9) filter(I1,nil) => nil (10) filter(J1,cons(X2,Y2)) => filter2(J1[X2],J1,X2,Y2) (11) filter2(true,G2,V2,W2) => cons(V2,filter(G2,W2)) (12) filter2(false,J2,X3,Y3) => filter(J2,Y3) ******** 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) intlist(nil) => nil (fun intlist>nil) >>True Checking (2) intlist(cons(X,Y)) => cons(s(X),intlist(Y)) (fun intlist>cons) (fun intlist>s) (meta X)[is acc in cons(X,Y)] [is positive in cons(X,Y)] [is acc in X] (fun intlist=intlist) subterm comparison of args w. LR LR (meta Y)[is acc in cons(X,Y)] [is positive in cons(X,Y)] [is acc in Y] >>True Checking (3) int(0,0) => cons(0,nil) (fun int>cons) (fun int>0) (fun int>nil) >>True Checking (4) int(0,s(U)) => cons(0,int(s(0),s(U))) (fun int>cons) (fun int>0) (fun int=int) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) intlist(nil) => nil (fun intlist>nil) >>True Checking (2) intlist(cons(X,Y)) => cons(s(X),intlist(Y)) (fun intlist>cons) (fun intlist>s) (meta X)[is acc in cons(X,Y)] [is positive in cons(X,Y)] [is acc in X] (fun intlist=intlist) subterm comparison of args w. RL RL (meta Y)[is acc in cons(X,Y)] [is positive in cons(X,Y)] [is acc in Y] >>True Checking (3) int(0,0) => cons(0,nil) (fun int>cons) (fun int>0) (fun int>nil) >>True Checking (4) int(0,s(U)) => cons(0,int(s(0),s(U))) (fun int>cons) (fun int>0) (fun int=int) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) intlist(nil) => nil (fun intlist>nil) >>True Checking (2) intlist(cons(X,Y)) => cons(s(X),intlist(Y)) (fun intlist>cons) (fun intlist>s) (meta X)[is acc in cons(X,Y)] [is positive in cons(X,Y)] [is acc in X] (fun intlist=intlist) subterm comparison of args w. Mul Mul (meta Y)[is acc in cons(X,Y)] [is positive in cons(X,Y)] [is acc in Y] >>True Checking (3) int(0,0) => cons(0,nil) (fun int>cons) (fun int>0) (fun int>nil) >>True Checking (4) int(0,s(U)) => cons(0,int(s(0),s(U))) (fun int>cons) (fun int>0) (fun int=int) 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(F1,nil) => nil (fun map>nil) >>True Checking (8) map(Z1,cons(U1,V1)) => cons(Z1[U1],map(Z1,V1)) (fun map>cons) (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] (fun map=map) subterm comparison of args w. LR LR (meta Z1)[is acc in Z1,cons(U1,V1)] [is acc in Z1] (meta V1)[is acc in Z1,cons(U1,V1)] [is positive in cons(U1,V1)] [is acc in V1] >>True Checking (9) filter(I1,nil) => nil (fun filter>nil) >>True Checking (10) filter(J1,cons(X2,Y2)) => filter2(J1[X2],J1,X2,Y2) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (meta J1)[is acc in J1,cons(X2,Y2)] [is acc in J1] (meta X2)[is acc in J1,cons(X2,Y2)] [is positive in cons(X2,Y2)] [is acc in X2] (meta J1)[is acc in J1,cons(X2,Y2)] [is acc in J1] (meta X2)[is acc in J1,cons(X2,Y2)] [is positive in cons(X2,Y2)] [is acc in X2] (meta Y2)[is acc in J1,cons(X2,Y2)] [is positive in cons(X2,Y2)] [is acc in Y2] >>True Checking (11) filter2(true,G2,V2,W2) => cons(V2,filter(G2,W2)) (fun filter2>cons) (meta V2)[is acc in true,G2,V2,W2] [is positive in true] [is acc in V2] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta G2)[is acc in true,G2,V2,W2] [is positive in true] [is acc in G2] (meta W2)[is acc in true,G2,V2,W2] [is positive in true] [is acc in W2] >>True Checking (12) filter2(false,J2,X3,Y3) => filter(J2,Y3) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta J2)[is acc in false,J2,X3,Y3] [is positive in false] [is acc in J2] (meta Y3)[is acc in false,J2,X3,Y3] [is positive in false] [is acc in Y3] >>True #SN! ******** Signature ******** 0 : b cons : (b,c) -> c false : a filter : ((b -> a),c) -> c filter2 : (a,(b -> a),b,c) -> c int : (b,b) -> c intlist : c -> c map : ((b -> b),c) -> c nil : c s : b -> b true : a ******** Computation Rules ******** (1) intlist(nil) => nil (2) intlist(cons(X,Y)) => cons(s(X),intlist(Y)) (3) int(0,0) => cons(0,nil) (4) int(0,s(U)) => cons(0,int(s(0),s(U))) (5) int(s(V),0) => nil (6) int(s(W),s(P)) => intlist(int(W,P)) (7) map(F1,nil) => nil (8) map(Z1,cons(U1,V1)) => cons(Z1[U1],map(Z1,V1)) (9) filter(I1,nil) => nil (10) filter(J1,cons(X2,Y2)) => filter2(J1[X2],J1,X2,Y2) (11) filter2(true,G2,V2,W2) => cons(V2,filter(G2,W2)) (12) filter2(false,J2,X3,Y3) => filter(J2,Y3) YES