/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(X,0()) -> X 2: minus(s(Y),s(U)) -> minus(Y,U) 3: minus(minus(V,W),P) -> minus(V,plus(W,P)) 4: quot(0(),s(X1)) -> 0() 5: quot(s(Y1),s(U1)) -> s(quot(minus(Y1,U1),s(U1))) 6: plus(0(),V1) -> V1 7: plus(s(W1),P1) -> s(plus(W1,P1)) 8: app(nil(),X2) -> X2 9: app(Y2,nil()) -> Y2 10: app(cons(W2,V2),U2) -> cons(W2,app(V2,U2)) 11: sum(cons(P2,nil())) -> cons(P2,nil()) 12: sum(cons(Y3,cons(U3,X3))) -> sum(cons(plus(Y3,U3),X3)) 13: sum(app(W3,cons(P3,cons(X4,V3)))) -> sum(app(W3,sum(cons(P3,cons(X4,V3))))) 14: _(X1,X2) -> X1 15: _(X1,X2) -> X2 Number of strict rules: 15 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #minus(s(Y),s(U)) -> #minus(Y,U) #2: #sum(app(W3,cons(P3,cons(X4,V3)))) -> #sum(app(W3,sum(cons(P3,cons(X4,V3))))) #3: #sum(app(W3,cons(P3,cons(X4,V3)))) -> #app(W3,sum(cons(P3,cons(X4,V3)))) #4: #sum(app(W3,cons(P3,cons(X4,V3)))) -> #sum(cons(P3,cons(X4,V3))) #5: #sum(cons(Y3,cons(U3,X3))) -> #sum(cons(plus(Y3,U3),X3)) #6: #sum(cons(Y3,cons(U3,X3))) -> #plus(Y3,U3) #7: #plus(s(W1),P1) -> #plus(W1,P1) #8: #app(cons(W2,V2),U2) -> #app(V2,U2) #9: #quot(s(Y1),s(U1)) -> #quot(minus(Y1,U1),s(U1)) #10: #quot(s(Y1),s(U1)) -> #minus(Y1,U1) #11: #minus(minus(V,W),P) -> #minus(V,plus(W,P)) #12: #minus(minus(V,W),P) -> #plus(W,P) Number of SCCs: 6, DPs: 7 SCC { #7 } POLO(Sum)... succeeded. s w: x1 + 1 minus w: 0 #plus w: x1 _ w: 0 sum w: 0 0 w: 0 quot w: 0 nil w: 0 #app w: 0 #minus w: 0 #_ w: 0 plus w: 0 cons w: 0 #quot w: 0 #sum w: 0 app w: 0 USABLE RULES: { } Removed DPs: #7 Number of SCCs: 5, DPs: 6 SCC { #8 } POLO(Sum)... succeeded. s w: 1 minus w: 0 #plus w: 0 _ w: 0 sum w: 0 0 w: 0 quot w: 0 nil w: 0 #app w: x1 #minus w: 0 #_ w: 0 plus w: 0 cons w: x2 + 1 #quot w: 0 #sum w: 0 app w: 0 USABLE RULES: { } Removed DPs: #8 Number of SCCs: 4, DPs: 5 SCC { #9 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + 1 #plus w: 0 _ w: 0 sum w: 0 0 w: 8856 quot w: 0 nil w: 0 #app w: 0 #minus w: 0 #_ w: 0 plus w: x1 + x2 + 2438 cons w: 1 #quot w: x1 #sum w: 0 app w: 0 USABLE RULES: { 1..3 6 7 } Removed DPs: #9 Number of SCCs: 3, DPs: 4 SCC { #5 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + 1 #plus w: 0 _ w: 0 sum w: 0 0 w: 5854 quot w: 0 nil w: 0 #app w: 0 #minus w: 0 #_ w: 0 plus w: x1 + x2 + 8099 cons w: x1 + x2 + 9242 #quot w: x1 #sum w: x1 app w: 0 USABLE RULES: { 1..3 6 7 } Removed DPs: #5 Number of SCCs: 2, DPs: 3 SCC { #2 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + 1 #plus w: 0 _ w: 0 sum w: 33224 0 w: 1654 quot w: 0 nil w: 9726 #app w: 0 #minus w: 0 #_ w: 0 plus w: x1 + x2 + 1889 cons w: x2 + 21052 #quot w: x1 #sum w: x1 app w: x1 + x2 + 8457 USABLE RULES: { 1..3 6..12 } Removed DPs: #2 Number of SCCs: 1, DPs: 2 SCC { #1 #11 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + x2 + 9482 #plus w: 0 _ w: 0 sum w: 3 0 w: 0 quot w: 0 nil w: 1 #app w: 0 #minus w: x1 + x2 #_ w: 0 plus w: x1 + x2 + 7887 cons w: x2 + 1 #quot w: x1 #sum w: x1 app w: x1 + x2 + 9532 USABLE RULES: { 1..3 6..12 } Removed DPs: #1 #11 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: minus(X,0()) -> X 2: minus(s(Y),s(U)) -> minus(Y,U) 3: minus(minus(V,W),P) -> minus(V,plus(W,P)) 4: quot(0(),s(X1)) -> 0() 5: quot(s(Y1),s(U1)) -> s(quot(minus(Y1,U1),s(U1))) 6: plus(0(),V1) -> V1 7: plus(s(W1),P1) -> s(plus(W1,P1)) 8: app(nil(),X2) -> X2 9: app(Y2,nil()) -> Y2 10: app(cons(W2,V2),U2) -> cons(W2,app(V2,U2)) 11: sum(cons(P2,nil())) -> cons(P2,nil()) 12: sum(cons(Y3,cons(U3,X3))) -> sum(cons(plus(Y3,U3),X3)) 13: sum(app(W3,cons(P3,cons(X4,V3)))) -> sum(app(W3,sum(cons(P3,cons(X4,V3))))) 14: _(X1,X2) -> X1 15: _(X1,X2) -> X2 Number of strict rules: 15 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #minus(s(Y),s(U)) -> #minus(Y,U) #2: #sum(app(W3,cons(P3,cons(X4,V3)))) -> #sum(app(W3,sum(cons(P3,cons(X4,V3))))) #3: #sum(app(W3,cons(P3,cons(X4,V3)))) -> #app(W3,sum(cons(P3,cons(X4,V3)))) #4: #sum(app(W3,cons(P3,cons(X4,V3)))) -> #sum(cons(P3,cons(X4,V3))) #5: #sum(cons(Y3,cons(U3,X3))) -> #sum(cons(plus(Y3,U3),X3)) #6: #sum(cons(Y3,cons(U3,X3))) -> #plus(Y3,U3) #7: #plus(s(W1),P1) -> #plus(W1,P1) #8: #app(cons(W2,V2),U2) -> #app(V2,U2) #9: #quot(s(Y1),s(U1)) -> #quot(minus(Y1,U1),s(U1)) #10: #quot(s(Y1),s(U1)) -> #minus(Y1,U1) #11: #minus(minus(V,W),P) -> #minus(V,plus(W,P)) #12: #minus(minus(V,W),P) -> #plus(W,P) Number of SCCs: 6, DPs: 7 SCC { #7 } POLO(Sum)... succeeded. s w: x1 + 1 minus w: 0 #plus w: x1 _ w: 0 sum w: 0 0 w: 0 quot w: 0 nil w: 0 #app w: 0 #minus w: 0 #_ w: 0 plus w: 0 cons w: 0 #quot w: 0 #sum w: 0 app w: 0 USABLE RULES: { } Removed DPs: #7 Number of SCCs: 5, DPs: 6 SCC { #8 } POLO(Sum)... succeeded. s w: 1 minus w: 0 #plus w: 0 _ w: 0 sum w: 0 0 w: 0 quot w: 0 nil w: 0 #app w: x1 #minus w: 0 #_ w: 0 plus w: 0 cons w: x2 + 1 #quot w: 0 #sum w: 0 app w: 0 USABLE RULES: { } Removed DPs: #8 Number of SCCs: 4, DPs: 5 SCC { #9 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + 1 #plus w: 0 _ w: 0 sum w: 0 0 w: 8856 quot w: 0 nil w: 0 #app w: 0 #minus w: 0 #_ w: 0 plus w: x1 + x2 + 2438 cons w: 1 #quot w: x1 #sum w: 0 app w: 0 USABLE RULES: { 1..3 6 7 } Removed DPs: #9 Number of SCCs: 3, DPs: 4 SCC { #5 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + 1 #plus w: 0 _ w: 0 sum w: 0 0 w: 5854 quot w: 0 nil w: 0 #app w: 0 #minus w: 0 #_ w: 0 plus w: x1 + x2 + 8099 cons w: x1 + x2 + 9242 #quot w: x1 #sum w: x1 app w: 0 USABLE RULES: { 1..3 6 7 } Removed DPs: #5 Number of SCCs: 2, DPs: 3 SCC { #2 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + 1 #plus w: 0 _ w: 0 sum w: 33224 0 w: 1654 quot w: 0 nil w: 9726 #app w: 0 #minus w: 0 #_ w: 0 plus w: x1 + x2 + 1889 cons w: x2 + 21052 #quot w: x1 #sum w: x1 app w: x1 + x2 + 8457 USABLE RULES: { 1..3 6..12 } Removed DPs: #2 Number of SCCs: 1, DPs: 2 SCC { #1 #11 } POLO(Sum)... succeeded. s w: x1 + 2 minus w: x1 + x2 + 9482 #plus w: 0 _ w: 0 sum w: 3 0 w: 0 quot w: 0 nil w: 1 #app w: 0 #minus w: x1 + x2 #_ w: 0 plus w: x1 + x2 + 7887 cons w: x2 + 1 #quot w: x1 #sum w: x1 app w: x1 + x2 + 9532 USABLE RULES: { 1..3 6..12 } Removed DPs: #1 #11 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 ******** (14) map(Z4,nil) => nil (15) map(G4,cons(V4,W4)) => cons(G4[V4],map(G4,W4)) (16) filter(J4,nil) => nil (17) filter(F5,cons(Y5,U5)) => filter2(F5[Y5],F5,Y5,U5) (18) filter2(true,H5,W5,P5) => cons(W5,filter(H5,P5)) (19) filter2(false,F6,Y6,U6) => filter(F6,U6) ******** 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) minus(minus(V,W),P) => minus(V,W + P) (fun minus=minus) subterm comparison of args w. LR LR (meta V)[is acc in minus(V,W),P] [is positive in minus(V,W)] [is acc in V] (fun minus>plus) (meta W)[is acc in minus(V,W),P] [is positive in minus(V,W)] [is acc in W] (meta P)[is acc in minus(V,W),P] [is positive in minus(V,W)] [is acc in P] >>True Checking (4) quot(0,s(X1)) => 0 (fun quot>0) >>True Checking (5) quot(s(Y1),s(U1)) => s(quot(minus(Y1,U1),s(U1))) (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) minus(minus(V,W),P) => minus(V,W + P) (fun minus=minus) 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) minus(minus(V,W),P) => minus(V,W + P) (fun minus=minus) 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 (14) map(Z4,nil) => nil (fun map>nil) >>True Checking (15) map(G4,cons(V4,W4)) => cons(G4[V4],map(G4,W4)) (fun map>cons) (meta G4)[is acc in G4,cons(V4,W4)] [is acc in G4] (meta V4)[is acc in G4,cons(V4,W4)] [is positive in cons(V4,W4)] [is acc in V4] (fun map=map) subterm comparison of args w. LR LR (meta G4)[is acc in G4,cons(V4,W4)] [is acc in G4] (meta W4)[is acc in G4,cons(V4,W4)] [is positive in cons(V4,W4)] [is acc in W4] >>True Checking (16) filter(J4,nil) => nil (fun filter>nil) >>True Checking (17) filter(F5,cons(Y5,U5)) => filter2(F5[Y5],F5,Y5,U5) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (meta F5)[is acc in F5,cons(Y5,U5)] [is acc in F5] (meta Y5)[is acc in F5,cons(Y5,U5)] [is positive in cons(Y5,U5)] [is acc in Y5] (meta F5)[is acc in F5,cons(Y5,U5)] [is acc in F5] (meta Y5)[is acc in F5,cons(Y5,U5)] [is positive in cons(Y5,U5)] [is acc in Y5] (meta U5)[is acc in F5,cons(Y5,U5)] [is positive in cons(Y5,U5)] [is acc in U5] >>True Checking (18) filter2(true,H5,W5,P5) => cons(W5,filter(H5,P5)) (fun filter2>cons) (meta W5)[is acc in true,H5,W5,P5] [is positive in true] [is acc in W5] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta H5)[is acc in true,H5,W5,P5] [is positive in true] [is acc in H5] (meta P5)[is acc in true,H5,W5,P5] [is positive in true] [is acc in P5] >>True Checking (19) filter2(false,F6,Y6,U6) => filter(F6,U6) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta F6)[is acc in false,F6,Y6,U6] [is positive in false] [is acc in F6] (meta U6)[is acc in false,F6,Y6,U6] [is positive in false] [is acc in U6] >>True #SN! ******** Signature ******** 0 : b app : (c,c) -> c cons : (b,c) -> c false : a filter : ((b -> a),c) -> c filter2 : (a,(b -> a),b,c) -> c map : ((b -> b),c) -> c minus : (b,b) -> b nil : c plus : (b,b) -> b quot : (b,b) -> b s : b -> b sum : c -> c true : a ******** Computation Rules ******** (1) minus(X,0) => X (2) minus(s(Y),s(U)) => minus(Y,U) (3) minus(minus(V,W),P) => minus(V,W + P) (4) quot(0,s(X1)) => 0 (5) quot(s(Y1),s(U1)) => s(quot(minus(Y1,U1),s(U1))) (6) 0 + V1 => V1 (7) s(W1) + P1 => s(W1 + P1) (8) nil@X2 => X2 (9) Y2@nil => Y2 (10) cons(W2,V2)@U2 => cons(W2,V2@U2) (11) sum(cons(P2,nil)) => cons(P2,nil) (12) sum(cons(Y3,cons(U3,X3))) => sum(cons(Y3 + U3,X3)) (13) sum(W3@cons(P3,cons(X4,V3))) => sum(W3@sum(cons(P3,cons(X4,V3)))) (14) map(Z4,nil) => nil (15) map(G4,cons(V4,W4)) => cons(G4[V4],map(G4,W4)) (16) filter(J4,nil) => nil (17) filter(F5,cons(Y5,U5)) => filter2(F5[Y5],F5,Y5,U5) (18) filter2(true,H5,W5,P5) => cons(W5,filter(H5,P5)) (19) filter2(false,F6,Y6,U6) => filter(F6,U6) YES