/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: quot(0(),s(V)) -> 0() 4: quot(s(W),s(P)) -> s(quot(minus(W,P),s(P))) 5: le(0(),X1) -> true() 6: le(s(Y1),0()) -> false() 7: le(s(U1),s(V1)) -> le(U1,V1) 8: app(nil(),W1) -> W1 9: app(add(P1,X2),Y2) -> add(P1,app(X2,Y2)) 10: low(U2,nil()) -> nil() 11: low(W2,add(V2,P2)) -> ifxb6220low(le(V2,W2),W2,add(V2,P2)) 12: ifxb6220low(true(),Y3,add(X3,U3)) -> add(X3,low(Y3,U3)) 13: ifxb6220low(false(),W3,add(V3,P3)) -> low(W3,P3) 14: high(X4,nil()) -> nil() 15: high(U4,add(Y4,V4)) -> ifxb6220high(le(Y4,U4),U4,add(Y4,V4)) 16: ifxb6220high(true(),P4,add(W4,X5)) -> high(P4,X5) 17: ifxb6220high(false(),U5,add(Y5,V5)) -> add(Y5,high(U5,V5)) 18: quicksort(nil()) -> nil() 19: quicksort(add(W5,P5)) -> app(quicksort(low(W5,P5)),add(W5,quicksort(high(W5,P5)))) 20: _(X1,X2) -> X1 21: _(X1,X2) -> X2 Number of strict rules: 21 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #minus(s(Y),s(U)) -> #minus(Y,U) #2: #ifxb6220low(false(),W3,add(V3,P3)) -> #low(W3,P3) #3: #app(add(P1,X2),Y2) -> #app(X2,Y2) #4: #low(W2,add(V2,P2)) -> #ifxb6220low(le(V2,W2),W2,add(V2,P2)) #5: #low(W2,add(V2,P2)) -> #le(V2,W2) #6: #ifxb6220low(true(),Y3,add(X3,U3)) -> #low(Y3,U3) #7: #le(s(U1),s(V1)) -> #le(U1,V1) #8: #ifxb6220high(false(),U5,add(Y5,V5)) -> #high(U5,V5) #9: #quicksort(add(W5,P5)) -> #app(quicksort(low(W5,P5)),add(W5,quicksort(high(W5,P5)))) #10: #quicksort(add(W5,P5)) -> #quicksort(low(W5,P5)) #11: #quicksort(add(W5,P5)) -> #low(W5,P5) #12: #quicksort(add(W5,P5)) -> #quicksort(high(W5,P5)) #13: #quicksort(add(W5,P5)) -> #high(W5,P5) #14: #ifxb6220high(true(),P4,add(W4,X5)) -> #high(P4,X5) #15: #high(U4,add(Y4,V4)) -> #ifxb6220high(le(Y4,U4),U4,add(Y4,V4)) #16: #high(U4,add(Y4,V4)) -> #le(Y4,U4) #17: #quot(s(W),s(P)) -> #quot(minus(W,P),s(P)) #18: #quot(s(W),s(P)) -> #minus(W,P) Number of SCCs: 7, DPs: 12 SCC { #1 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 1 #le w: 0 ifxb6220high w: 0 minus w: 0 #quicksort w: 0 #high w: 0 false w: 0 #ifxb6220high w: 0 _ w: 0 quicksort w: 0 true w: 0 0 w: 0 quot w: 0 high w: 0 nil w: 0 #app w: 0 #ifxb6220low w: 0 #minus w: x1 + x2 #_ w: 0 low w: 0 add w: 0 #quot w: 0 ifxb6220low w: 0 #low w: 0 app w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 6, DPs: 11 SCC { #3 } POLO(Sum)... succeeded. le w: 0 s w: 1 #le w: 0 ifxb6220high w: 0 minus w: 0 #quicksort w: 0 #high w: 0 false w: 0 #ifxb6220high w: 0 _ w: 0 quicksort w: 0 true w: 0 0 w: 0 quot w: 0 high w: 0 nil w: 0 #app w: x1 #ifxb6220low w: 0 #minus w: 0 #_ w: 0 low w: 0 add w: x2 + 1 #quot w: 0 ifxb6220low w: 0 #low w: 0 app w: 0 USABLE RULES: { } Removed DPs: #3 Number of SCCs: 5, DPs: 10 SCC { #7 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 1 #le w: x2 ifxb6220high w: 0 minus w: 0 #quicksort w: 0 #high w: 0 false w: 0 #ifxb6220high w: 0 _ w: 0 quicksort w: 0 true w: 0 0 w: 0 quot w: 0 high w: 0 nil w: 0 #app w: 0 #ifxb6220low w: 0 #minus w: 0 #_ w: 0 low w: 0 add w: 1 #quot w: 0 ifxb6220low w: 0 #low w: 0 app w: 0 USABLE RULES: { } Removed DPs: #7 Number of SCCs: 4, DPs: 9 SCC { #17 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 2 #le w: 0 ifxb6220high w: 0 minus w: x1 + 1 #quicksort w: 0 #high w: 0 false w: 0 #ifxb6220high w: 0 _ w: 0 quicksort w: 0 true w: 0 0 w: 1 quot w: 0 high w: 0 nil w: 0 #app w: 0 #ifxb6220low w: 0 #minus w: 0 #_ w: 0 low w: 0 add w: 1 #quot w: x1 ifxb6220low w: 0 #low w: 0 app w: 0 USABLE RULES: { 1 2 } Removed DPs: #17 Number of SCCs: 3, DPs: 8 SCC { #10 #12 } POLO(Sum)... succeeded. le w: x1 + x2 + 1 s w: x1 + 1 #le w: 0 ifxb6220high w: x3 + 252 minus w: x1 + 1 #quicksort w: x1 #high w: 0 false w: 4 #ifxb6220high w: 0 _ w: 0 quicksort w: 0 true w: 3 0 w: 1 quot w: 0 high w: x2 + 252 nil w: 8099 #app w: 0 #ifxb6220low w: 0 #minus w: 0 #_ w: 0 low w: x2 + 294 add w: x2 + 295 #quot w: x1 ifxb6220low w: x3 + 294 #low w: 0 app w: 0 USABLE RULES: { 1 2 10..17 } Removed DPs: #10 #12 Number of SCCs: 2, DPs: 6 SCC { #8 #14 #15 } POLO(Sum)... succeeded. le w: 140 s w: x1 + 5905 #le w: 0 ifxb6220high w: x3 + 252 minus w: x1 + 1 #quicksort w: x1 #high w: x1 + x2 + 141 false w: 23 #ifxb6220high w: x1 + x2 + x3 _ w: 0 quicksort w: 0 true w: 64 0 w: 0 quot w: 0 high w: x2 + 252 nil w: 8099 #app w: 0 #ifxb6220low w: 0 #minus w: 0 #_ w: 0 low w: x2 + 294 add w: x2 + 295 #quot w: x1 ifxb6220low w: x3 + 294 #low w: 0 app w: 0 USABLE RULES: { 1 2 5..7 10..17 } Removed DPs: #8 #14 #15 Number of SCCs: 1, DPs: 3 SCC { #2 #4 #6 } POLO(Sum)... succeeded. le w: 7895 s w: x1 + 841 #le w: 0 ifxb6220high w: x3 + 252 minus w: x1 + 1 #quicksort w: x1 #high w: 2 false w: 7895 #ifxb6220high w: x1 _ w: 0 quicksort w: 0 true w: 6907 0 w: 0 quot w: 0 high w: x2 + 252 nil w: 8099 #app w: 0 #ifxb6220low w: x1 + x2 + x3 #minus w: 0 #_ w: 0 low w: x2 + 294 add w: x2 + 2448 #quot w: x1 ifxb6220low w: x3 + 294 #low w: x1 + x2 + 7896 app w: 0 USABLE RULES: { 1 2 5..7 10..17 } Removed DPs: #2 #4 #6 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: minus(X,0()) -> X 2: minus(s(Y),s(U)) -> minus(Y,U) 3: quot(0(),s(V)) -> 0() 4: quot(s(W),s(P)) -> s(quot(minus(W,P),s(P))) 5: le(0(),X1) -> true() 6: le(s(Y1),0()) -> false() 7: le(s(U1),s(V1)) -> le(U1,V1) 8: app(nil(),W1) -> W1 9: app(add(P1,X2),Y2) -> add(P1,app(X2,Y2)) 10: low(U2,nil()) -> nil() 11: low(W2,add(V2,P2)) -> ifxb6220low(le(V2,W2),W2,add(V2,P2)) 12: ifxb6220low(true(),Y3,add(X3,U3)) -> add(X3,low(Y3,U3)) 13: ifxb6220low(false(),W3,add(V3,P3)) -> low(W3,P3) 14: high(X4,nil()) -> nil() 15: high(U4,add(Y4,V4)) -> ifxb6220high(le(Y4,U4),U4,add(Y4,V4)) 16: ifxb6220high(true(),P4,add(W4,X5)) -> high(P4,X5) 17: ifxb6220high(false(),U5,add(Y5,V5)) -> add(Y5,high(U5,V5)) 18: quicksort(nil()) -> nil() 19: quicksort(add(W5,P5)) -> app(quicksort(low(W5,P5)),add(W5,quicksort(high(W5,P5)))) 20: _(X1,X2) -> X1 21: _(X1,X2) -> X2 Number of strict rules: 21 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #minus(s(Y),s(U)) -> #minus(Y,U) #2: #ifxb6220low(false(),W3,add(V3,P3)) -> #low(W3,P3) #3: #app(add(P1,X2),Y2) -> #app(X2,Y2) #4: #low(W2,add(V2,P2)) -> #ifxb6220low(le(V2,W2),W2,add(V2,P2)) #5: #low(W2,add(V2,P2)) -> #le(V2,W2) #6: #ifxb6220low(true(),Y3,add(X3,U3)) -> #low(Y3,U3) #7: #le(s(U1),s(V1)) -> #le(U1,V1) #8: #ifxb6220high(false(),U5,add(Y5,V5)) -> #high(U5,V5) #9: #quicksort(add(W5,P5)) -> #app(quicksort(low(W5,P5)),add(W5,quicksort(high(W5,P5)))) #10: #quicksort(add(W5,P5)) -> #quicksort(low(W5,P5)) #11: #quicksort(add(W5,P5)) -> #low(W5,P5) #12: #quicksort(add(W5,P5)) -> #quicksort(high(W5,P5)) #13: #quicksort(add(W5,P5)) -> #high(W5,P5) #14: #ifxb6220high(true(),P4,add(W4,X5)) -> #high(P4,X5) #15: #high(U4,add(Y4,V4)) -> #ifxb6220high(le(Y4,U4),U4,add(Y4,V4)) #16: #high(U4,add(Y4,V4)) -> #le(Y4,U4) #17: #quot(s(W),s(P)) -> #quot(minus(W,P),s(P)) #18: #quot(s(W),s(P)) -> #minus(W,P) Number of SCCs: 7, DPs: 12 SCC { #1 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 1 #le w: 0 ifxb6220high w: 0 minus w: 0 #quicksort w: 0 #high w: 0 false w: 0 #ifxb6220high w: 0 _ w: 0 quicksort w: 0 true w: 0 0 w: 0 quot w: 0 high w: 0 nil w: 0 #app w: 0 #ifxb6220low w: 0 #minus w: x1 + x2 #_ w: 0 low w: 0 add w: 0 #quot w: 0 ifxb6220low w: 0 #low w: 0 app w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 6, DPs: 11 SCC { #3 } POLO(Sum)... succeeded. le w: 0 s w: 1 #le w: 0 ifxb6220high w: 0 minus w: 0 #quicksort w: 0 #high w: 0 false w: 0 #ifxb6220high w: 0 _ w: 0 quicksort w: 0 true w: 0 0 w: 0 quot w: 0 high w: 0 nil w: 0 #app w: x1 #ifxb6220low w: 0 #minus w: 0 #_ w: 0 low w: 0 add w: x2 + 1 #quot w: 0 ifxb6220low w: 0 #low w: 0 app w: 0 USABLE RULES: { } Removed DPs: #3 Number of SCCs: 5, DPs: 10 SCC { #7 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 1 #le w: x2 ifxb6220high w: 0 minus w: 0 #quicksort w: 0 #high w: 0 false w: 0 #ifxb6220high w: 0 _ w: 0 quicksort w: 0 true w: 0 0 w: 0 quot w: 0 high w: 0 nil w: 0 #app w: 0 #ifxb6220low w: 0 #minus w: 0 #_ w: 0 low w: 0 add w: 1 #quot w: 0 ifxb6220low w: 0 #low w: 0 app w: 0 USABLE RULES: { } Removed DPs: #7 Number of SCCs: 4, DPs: 9 SCC { #17 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 2 #le w: 0 ifxb6220high w: 0 minus w: x1 + 1 #quicksort w: 0 #high w: 0 false w: 0 #ifxb6220high w: 0 _ w: 0 quicksort w: 0 true w: 0 0 w: 1 quot w: 0 high w: 0 nil w: 0 #app w: 0 #ifxb6220low w: 0 #minus w: 0 #_ w: 0 low w: 0 add w: 1 #quot w: x1 ifxb6220low w: 0 #low w: 0 app w: 0 USABLE RULES: { 1 2 } Removed DPs: #17 Number of SCCs: 3, DPs: 8 SCC { #10 #12 } POLO(Sum)... succeeded. le w: x1 + x2 + 1 s w: x1 + 1 #le w: 0 ifxb6220high w: x3 + 252 minus w: x1 + 1 #quicksort w: x1 #high w: 0 false w: 4 #ifxb6220high w: 0 _ w: 0 quicksort w: 0 true w: 3 0 w: 1 quot w: 0 high w: x2 + 252 nil w: 8099 #app w: 0 #ifxb6220low w: 0 #minus w: 0 #_ w: 0 low w: x2 + 294 add w: x2 + 295 #quot w: x1 ifxb6220low w: x3 + 294 #low w: 0 app w: 0 USABLE RULES: { 1 2 10..17 } Removed DPs: #10 #12 Number of SCCs: 2, DPs: 6 SCC { #8 #14 #15 } POLO(Sum)... succeeded. le w: 140 s w: x1 + 5905 #le w: 0 ifxb6220high w: x3 + 252 minus w: x1 + 1 #quicksort w: x1 #high w: x1 + x2 + 141 false w: 23 #ifxb6220high w: x1 + x2 + x3 _ w: 0 quicksort w: 0 true w: 64 0 w: 0 quot w: 0 high w: x2 + 252 nil w: 8099 #app w: 0 #ifxb6220low w: 0 #minus w: 0 #_ w: 0 low w: x2 + 294 add w: x2 + 295 #quot w: x1 ifxb6220low w: x3 + 294 #low w: 0 app w: 0 USABLE RULES: { 1 2 5..7 10..17 } Removed DPs: #8 #14 #15 Number of SCCs: 1, DPs: 3 SCC { #2 #4 #6 } POLO(Sum)... succeeded. le w: 7895 s w: x1 + 841 #le w: 0 ifxb6220high w: x3 + 252 minus w: x1 + 1 #quicksort w: x1 #high w: 2 false w: 7895 #ifxb6220high w: x1 _ w: 0 quicksort w: 0 true w: 6907 0 w: 0 quot w: 0 high w: x2 + 252 nil w: 8099 #app w: 0 #ifxb6220low w: x1 + x2 + x3 #minus w: 0 #_ w: 0 low w: x2 + 294 add w: x2 + 2448 #quot w: x1 ifxb6220low w: x3 + 294 #low w: x1 + x2 + 7896 app w: 0 USABLE RULES: { 1 2 5..7 10..17 } Removed DPs: #2 #4 #6 Number of SCCs: 0, DPs: 0 >>YES ******** Signature ******** map : ((b -> b),c) -> c nil : c add : (b,c) -> c filter : ((b -> a),c) -> c filter2 : (a,(b -> a),b,c) -> c true : a false : a ******** Computation rules ******** (20) map(F6,nil) => nil (21) map(Z6,add(U6,V6)) => add(Z6[U6],map(Z6,V6)) (22) filter(I6,nil) => nil (23) filter(J6,add(X7,Y7)) => filter2(J6[X7],J6,X7,Y7) (24) filter2(true,G7,V7,W7) => add(V7,filter(G7,W7)) (25) filter2(false,J7,X8,Y8) => filter(J7,Y8) ******** General Schema criterion ******** Found constructors: 0, add, 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) quot(0,s(V)) => 0 (fun quot>0) >>True Checking (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (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) quot(0,s(V)) => 0 (fun quot>0) >>True Checking (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (fun quot>s) (fun quot=quot) 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) quot(0,s(V)) => 0 (fun quot>0) >>True Checking (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (fun quot>s) (fun quot=quot) subterm comparison of args w. Mul Mul >>False Found constructors: nil, add, true, false Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>Regared as equal: filter2, filter Checking (20) map(F6,nil) => nil (fun map>nil) >>True Checking (21) map(Z6,add(U6,V6)) => add(Z6[U6],map(Z6,V6)) (fun map>add) (meta Z6)[is acc in Z6,add(U6,V6)] [is acc in Z6] (meta U6)[is acc in Z6,add(U6,V6)] [is positive in add(U6,V6)] [is acc in U6] (fun map=map) subterm comparison of args w. LR LR (meta Z6)[is acc in Z6,add(U6,V6)] [is acc in Z6] (meta V6)[is acc in Z6,add(U6,V6)] [is positive in add(U6,V6)] [is acc in V6] >>True Checking (22) filter(I6,nil) => nil (fun filter>nil) >>True Checking (23) filter(J6,add(X7,Y7)) => filter2(J6[X7],J6,X7,Y7) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (meta J6)[is acc in J6,add(X7,Y7)] [is acc in J6] (meta X7)[is acc in J6,add(X7,Y7)] [is positive in add(X7,Y7)] [is acc in X7] (meta J6)[is acc in J6,add(X7,Y7)] [is acc in J6] (meta X7)[is acc in J6,add(X7,Y7)] [is positive in add(X7,Y7)] [is acc in X7] (meta Y7)[is acc in J6,add(X7,Y7)] [is positive in add(X7,Y7)] [is acc in Y7] >>True Checking (24) filter2(true,G7,V7,W7) => add(V7,filter(G7,W7)) (fun filter2>add) (meta V7)[is acc in true,G7,V7,W7] [is positive in true] [is acc in V7] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta G7)[is acc in true,G7,V7,W7] [is positive in true] [is acc in G7] (meta W7)[is acc in true,G7,V7,W7] [is positive in true] [is acc in W7] >>True Checking (25) filter2(false,J7,X8,Y8) => filter(J7,Y8) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta J7)[is acc in false,J7,X8,Y8] [is positive in false] [is acc in J7] (meta Y8)[is acc in false,J7,X8,Y8] [is positive in false] [is acc in Y8] >>True #SN! ******** Signature ******** 0 : b add : (b,c) -> c app : (c,c) -> c false : a filter : ((b -> a),c) -> c filter2 : (a,(b -> a),b,c) -> c high : (b,c) -> c ifxb6220high : (a,b,c) -> c ifxb6220low : (a,b,c) -> c le : (b,b) -> a low : (b,c) -> c map : ((b -> b),c) -> c minus : (b,b) -> b nil : c quicksort : c -> c quot : (b,b) -> b s : b -> b true : a ******** Computation Rules ******** (1) minus(X,0) => X (2) minus(s(Y),s(U)) => minus(Y,U) (3) quot(0,s(V)) => 0 (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (5) le(0,X1) => true (6) le(s(Y1),0) => false (7) le(s(U1),s(V1)) => le(U1,V1) (8) nil@W1 => W1 (9) add(P1,X2)@Y2 => add(P1,X2@Y2) (10) low(U2,nil) => nil (11) low(W2,add(V2,P2)) => ifxb6220low(le(V2,W2),W2,add(V2,P2)) (12) ifxb6220low(true,Y3,add(X3,U3)) => add(X3,low(Y3,U3)) (13) ifxb6220low(false,W3,add(V3,P3)) => low(W3,P3) (14) high(X4,nil) => nil (15) high(U4,add(Y4,V4)) => ifxb6220high(le(Y4,U4),U4,add(Y4,V4)) (16) ifxb6220high(true,P4,add(W4,X5)) => high(P4,X5) (17) ifxb6220high(false,U5,add(Y5,V5)) => add(Y5,high(U5,V5)) (18) quicksort(nil) => nil (19) quicksort(add(W5,P5)) => quicksort(low(W5,P5))@add(W5,quicksort(high(W5,P5))) (20) map(F6,nil) => nil (21) map(Z6,add(U6,V6)) => add(Z6[U6],map(Z6,V6)) (22) filter(I6,nil) => nil (23) filter(J6,add(X7,Y7)) => filter2(J6[X7],J6,X7,Y7) (24) filter2(true,G7,V7,W7) => add(V7,filter(G7,W7)) (25) filter2(false,J7,X8,Y8) => filter(J7,Y8) YES