YES Input TRS: 1: active(filter(cons(X,Y),0(),M)) -> mark(cons(0(),filter(Y,M,M))) 2: active(filter(cons(X,Y),s(N),M)) -> mark(cons(X,filter(Y,N,M))) 3: active(sieve(cons(0(),Y))) -> mark(cons(0(),sieve(Y))) 4: active(sieve(cons(s(N),Y))) -> mark(cons(s(N),sieve(filter(Y,N,N)))) 5: active(nats(N)) -> mark(cons(N,nats(s(N)))) 6: active(zprimes()) -> mark(sieve(nats(s(s(0()))))) 7: active(filter(X1,X2,X3)) -> filter(active(X1),X2,X3) 8: active(filter(X1,X2,X3)) -> filter(X1,active(X2),X3) 9: active(filter(X1,X2,X3)) -> filter(X1,X2,active(X3)) 10: active(cons(X1,X2)) -> cons(active(X1),X2) 11: active(s(X)) -> s(active(X)) 12: active(sieve(X)) -> sieve(active(X)) 13: active(nats(X)) -> nats(active(X)) 14: filter(mark(X1),X2,X3) -> mark(filter(X1,X2,X3)) 15: filter(X1,mark(X2),X3) -> mark(filter(X1,X2,X3)) 16: filter(X1,X2,mark(X3)) -> mark(filter(X1,X2,X3)) 17: cons(mark(X1),X2) -> mark(cons(X1,X2)) 18: s(mark(X)) -> mark(s(X)) 19: sieve(mark(X)) -> mark(sieve(X)) 20: nats(mark(X)) -> mark(nats(X)) 21: proper(filter(X1,X2,X3)) -> filter(proper(X1),proper(X2),proper(X3)) 22: proper(cons(X1,X2)) -> cons(proper(X1),proper(X2)) 23: proper(0()) -> ok(0()) 24: proper(s(X)) -> s(proper(X)) 25: proper(sieve(X)) -> sieve(proper(X)) 26: proper(nats(X)) -> nats(proper(X)) 27: proper(zprimes()) -> ok(zprimes()) 28: filter(ok(X1),ok(X2),ok(X3)) -> ok(filter(X1,X2,X3)) 29: cons(ok(X1),ok(X2)) -> ok(cons(X1,X2)) 30: s(ok(X)) -> ok(s(X)) 31: sieve(ok(X)) -> ok(sieve(X)) 32: nats(ok(X)) -> ok(nats(X)) 33: top(mark(X)) -> top(proper(X)) 34: top(ok(X)) -> top(active(X)) Number of strict rules: 34 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #active(filter(cons(X,Y),s(N),M)) -> #cons(X,filter(Y,N,M)) #2: #active(filter(cons(X,Y),s(N),M)) -> #filter(Y,N,M) #3: #cons(ok(X1),ok(X2)) -> #cons(X1,X2) #4: #active(zprimes()) -> #sieve(nats(s(s(0())))) #5: #active(zprimes()) -> #nats(s(s(0()))) #6: #active(zprimes()) -> #s(s(0())) #7: #active(zprimes()) -> #s(0()) #8: #active(nats(X)) -> #nats(active(X)) #9: #active(nats(X)) -> #active(X) #10: #active(filter(X1,X2,X3)) -> #filter(X1,X2,active(X3)) #11: #active(filter(X1,X2,X3)) -> #active(X3) #12: #active(s(X)) -> #s(active(X)) #13: #active(s(X)) -> #active(X) #14: #proper(s(X)) -> #s(proper(X)) #15: #proper(s(X)) -> #proper(X) #16: #active(sieve(X)) -> #sieve(active(X)) #17: #active(sieve(X)) -> #active(X) #18: #sieve(ok(X)) -> #sieve(X) #19: #filter(mark(X1),X2,X3) -> #filter(X1,X2,X3) #20: #s(ok(X)) -> #s(X) #21: #proper(sieve(X)) -> #sieve(proper(X)) #22: #proper(sieve(X)) -> #proper(X) #23: #nats(mark(X)) -> #nats(X) #24: #active(filter(X1,X2,X3)) -> #filter(active(X1),X2,X3) #25: #active(filter(X1,X2,X3)) -> #active(X1) #26: #active(cons(X1,X2)) -> #cons(active(X1),X2) #27: #active(cons(X1,X2)) -> #active(X1) #28: #top(mark(X)) -> #top(proper(X)) #29: #top(mark(X)) -> #proper(X) #30: #active(nats(N)) -> #cons(N,nats(s(N))) #31: #active(nats(N)) -> #nats(s(N)) #32: #active(nats(N)) -> #s(N) #33: #filter(ok(X1),ok(X2),ok(X3)) -> #filter(X1,X2,X3) #34: #proper(cons(X1,X2)) -> #cons(proper(X1),proper(X2)) #35: #proper(cons(X1,X2)) -> #proper(X1) #36: #proper(cons(X1,X2)) -> #proper(X2) #37: #top(ok(X)) -> #top(active(X)) #38: #top(ok(X)) -> #active(X) #39: #cons(mark(X1),X2) -> #cons(X1,X2) #40: #nats(ok(X)) -> #nats(X) #41: #sieve(mark(X)) -> #sieve(X) #42: #proper(nats(X)) -> #nats(proper(X)) #43: #proper(nats(X)) -> #proper(X) #44: #proper(filter(X1,X2,X3)) -> #filter(proper(X1),proper(X2),proper(X3)) #45: #proper(filter(X1,X2,X3)) -> #proper(X1) #46: #proper(filter(X1,X2,X3)) -> #proper(X2) #47: #proper(filter(X1,X2,X3)) -> #proper(X3) #48: #filter(X1,X2,mark(X3)) -> #filter(X1,X2,X3) #49: #active(sieve(cons(0(),Y))) -> #cons(0(),sieve(Y)) #50: #active(sieve(cons(0(),Y))) -> #sieve(Y) #51: #active(filter(cons(X,Y),0(),M)) -> #cons(0(),filter(Y,M,M)) #52: #active(filter(cons(X,Y),0(),M)) -> #filter(Y,M,M) #53: #active(filter(X1,X2,X3)) -> #filter(X1,active(X2),X3) #54: #active(filter(X1,X2,X3)) -> #active(X2) #55: #filter(X1,mark(X2),X3) -> #filter(X1,X2,X3) #56: #active(sieve(cons(s(N),Y))) -> #cons(s(N),sieve(filter(Y,N,N))) #57: #active(sieve(cons(s(N),Y))) -> #sieve(filter(Y,N,N)) #58: #active(sieve(cons(s(N),Y))) -> #filter(Y,N,N) #59: #s(mark(X)) -> #s(X) Number of SCCs: 8, DPs: 29 SCC { #18 #41 } POLO(Sum)... succeeded. zprimes w: 0 #cons w: 0 #nats w: 0 s w: 0 #filter w: 0 top w: 0 #top w: 0 proper w: 0 ok w: x1 + 1 0 w: 0 #s w: 0 mark w: x1 + 1 sieve w: 0 #proper w: 0 nats w: 0 active w: 0 cons w: 0 #active w: 0 filter w: 0 #sieve w: x1 USABLE RULES: { } Removed DPs: #18 #41 Number of SCCs: 7, DPs: 27 SCC { #23 #40 } POLO(Sum)... succeeded. zprimes w: 0 #cons w: 0 #nats w: x1 s w: 0 #filter w: 0 top w: 0 #top w: 0 proper w: 0 ok w: x1 + 1 0 w: 0 #s w: 0 mark w: x1 + 1 sieve w: 0 #proper w: 0 nats w: 0 active w: 0 cons w: 0 #active w: 0 filter w: 0 #sieve w: 0 USABLE RULES: { } Removed DPs: #23 #40 Number of SCCs: 6, DPs: 25 SCC { #20 #59 } POLO(Sum)... succeeded. zprimes w: 0 #cons w: 0 #nats w: 0 s w: 0 #filter w: 0 top w: 0 #top w: 0 proper w: 0 ok w: x1 + 1 0 w: 0 #s w: x1 mark w: x1 + 1 sieve w: 0 #proper w: 0 nats w: 0 active w: 0 cons w: 0 #active w: 0 filter w: 0 #sieve w: 0 USABLE RULES: { } Removed DPs: #20 #59 Number of SCCs: 5, DPs: 23 SCC { #28 #37 } POLO(Sum)... succeeded. zprimes w: 7 #cons w: 0 #nats w: 0 s w: x1 + 1 #filter w: 0 top w: 0 #top w: x1 proper w: x1 ok w: x1 0 w: 1 #s w: 0 mark w: x1 + 1 sieve w: x1 + 1 #proper w: 0 nats w: x1 + 2 active w: x1 cons w: x1 + 1 #active w: 0 filter w: x1 + x2 + x3 + 1 #sieve w: 0 USABLE RULES: { 1..32 } Removed DPs: #28 Number of SCCs: 5, DPs: 22 SCC { #37 } POLO(Sum)... succeeded. zprimes w: 4 #cons w: 0 #nats w: 0 s w: x1 + 1 #filter w: 0 top w: 0 #top w: x1 proper w: x1 + 2 ok w: x1 + 2 0 w: 1 #s w: 0 mark w: x1 sieve w: x1 + 1 #proper w: 0 nats w: x1 + 1 active w: x1 + 1 cons w: x1 + 1 #active w: 0 filter w: x1 + 1 #sieve w: 0 USABLE RULES: { 1..32 } Removed DPs: #37 Number of SCCs: 4, DPs: 21 SCC { #3 #39 } POLO(Sum)... succeeded. zprimes w: 44388 #cons w: x1 + x2 #nats w: 0 s w: x1 + 3566 #filter w: 0 top w: 0 #top w: x1 proper w: x1 + 1 ok w: x1 + 1 0 w: 2 #s w: 0 mark w: x1 sieve w: x1 + 37254 #proper w: 0 nats w: x1 + 1 active w: x1 + 1 cons w: x1 + 1 #active w: 0 filter w: x1 + 1 #sieve w: 0 USABLE RULES: { 1..32 } Removed DPs: #3 Number of SCCs: 4, DPs: 20 SCC { #39 } POLO(Sum)... succeeded. zprimes w: 61690 #cons w: x1 #nats w: 0 s w: x1 + 1 #filter w: 0 top w: 0 #top w: 0 proper w: x1 + 1 ok w: x1 + 1 0 w: 1 #s w: 0 mark w: x1 + 2 sieve w: x1 + 61688 #proper w: 0 nats w: 1 active w: x1 + 1 cons w: x1 + 1 #active w: 0 filter w: x1 + 978 #sieve w: 0 USABLE RULES: { 1..4 17..19 23 27 29..31 } Removed DPs: #39 Number of SCCs: 3, DPs: 19 SCC { #19 #33 #48 #55 } POLO(Sum)... succeeded. zprimes w: 61694 #cons w: 0 #nats w: 0 s w: x1 + 3 #filter w: x1 + x2 + x3 top w: 0 #top w: 0 proper w: x1 + 3 ok w: x1 + 1 0 w: 4 #s w: 0 mark w: x1 + 3 sieve w: x1 + 2 #proper w: 0 nats w: 11495 active w: x1 + 1 cons w: x1 + 13927 #active w: 0 filter w: x1 + 6 #sieve w: 0 USABLE RULES: { 1..4 17..19 23 27 29..31 } Removed DPs: #19 #33 #48 #55 Number of SCCs: 2, DPs: 15 SCC { #9 #11 #13 #17 #25 #27 #54 } POLO(Sum)... succeeded. zprimes w: 7 #cons w: 0 #nats w: 0 s w: x1 + 1 #filter w: 0 top w: 0 #top w: 0 proper w: x1 ok w: x1 + 1 0 w: 1 #s w: 0 mark w: x1 sieve w: x1 + 1 #proper w: 0 nats w: x1 + 1 active w: x1 + 1 cons w: x1 + x2 + 1 #active w: x1 filter w: x1 + x2 + x3 + 1 #sieve w: 0 USABLE RULES: { 3 17..20 29..32 } Removed DPs: #9 #11 #13 #17 #25 #27 #54 Number of SCCs: 1, DPs: 8 SCC { #15 #22 #35 #36 #43 #45..47 } POLO(Sum)... succeeded. zprimes w: 6 #cons w: 0 #nats w: 0 s w: x1 + 1 #filter w: 0 top w: 0 #top w: 0 proper w: x1 ok w: x1 + 1 0 w: 1 #s w: 0 mark w: x1 sieve w: x1 + 1 #proper w: x1 nats w: x1 + 1 active w: x1 + 1 cons w: x1 + x2 + 1 #active w: 0 filter w: x1 + x2 + x3 + 1 #sieve w: 0 USABLE RULES: { 3 17..20 29..32 } Removed DPs: #15 #22 #35 #36 #43 #45..47 Number of SCCs: 0, DPs: 0