WORST_CASE(?,O(1)) * Step 1: Sum WORST_CASE(?,O(1)) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__filter(X1,X2)) -> filter(X1,X2) activate(n__from(X)) -> from(X) cons(X1,X2) -> n__cons(X1,X2) filter(X1,X2) -> n__filter(X1,X2) filter(s(s(X)),cons(Y,Z)) -> if(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) head(cons(X,Y)) -> X if(false(),X,Y) -> activate(Y) if(true(),X,Y) -> activate(X) primes() -> sieve(from(s(s(0())))) sieve(cons(X,Y)) -> cons(X,n__filter(X,sieve(activate(Y)))) tail(cons(X,Y)) -> activate(Y) - Signature: {activate/1,cons/2,filter/2,from/1,head/1,if/3,primes/0,sieve/1,tail/1} / {0/0,divides/2,false/0,n__cons/2 ,n__filter/2,n__from/1,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate,cons,filter,from,head,if,primes,sieve ,tail} and constructors {0,divides,false,n__cons,n__filter,n__from,s,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: DependencyPairs WORST_CASE(?,O(1)) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__filter(X1,X2)) -> filter(X1,X2) activate(n__from(X)) -> from(X) cons(X1,X2) -> n__cons(X1,X2) filter(X1,X2) -> n__filter(X1,X2) filter(s(s(X)),cons(Y,Z)) -> if(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) head(cons(X,Y)) -> X if(false(),X,Y) -> activate(Y) if(true(),X,Y) -> activate(X) primes() -> sieve(from(s(s(0())))) sieve(cons(X,Y)) -> cons(X,n__filter(X,sieve(activate(Y)))) tail(cons(X,Y)) -> activate(Y) - Signature: {activate/1,cons/2,filter/2,from/1,head/1,if/3,primes/0,sieve/1,tail/1} / {0/0,divides/2,false/0,n__cons/2 ,n__filter/2,n__from/1,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate,cons,filter,from,head,if,primes,sieve ,tail} and constructors {0,divides,false,n__cons,n__filter,n__from,s,true} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) activate#(n__from(X)) -> c_4(from#(X)) cons#(X1,X2) -> c_5() filter#(X1,X2) -> c_6() filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) from#(X) -> c_8(cons#(X,n__from(s(X)))) from#(X) -> c_9() head#(cons(X,Y)) -> c_10() if#(false(),X,Y) -> c_11(activate#(Y)) if#(true(),X,Y) -> c_12(activate#(X)) primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) tail#(cons(X,Y)) -> c_15(activate#(Y)) Weak DPs and mark the set of starting terms. * Step 3: PredecessorEstimation WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) activate#(n__from(X)) -> c_4(from#(X)) cons#(X1,X2) -> c_5() filter#(X1,X2) -> c_6() filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) from#(X) -> c_8(cons#(X,n__from(s(X)))) from#(X) -> c_9() head#(cons(X,Y)) -> c_10() if#(false(),X,Y) -> c_11(activate#(Y)) if#(true(),X,Y) -> c_12(activate#(X)) primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) tail#(cons(X,Y)) -> c_15(activate#(Y)) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__filter(X1,X2)) -> filter(X1,X2) activate(n__from(X)) -> from(X) cons(X1,X2) -> n__cons(X1,X2) filter(X1,X2) -> n__filter(X1,X2) filter(s(s(X)),cons(Y,Z)) -> if(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) head(cons(X,Y)) -> X if(false(),X,Y) -> activate(Y) if(true(),X,Y) -> activate(X) primes() -> sieve(from(s(s(0())))) sieve(cons(X,Y)) -> cons(X,n__filter(X,sieve(activate(Y)))) tail(cons(X,Y)) -> activate(Y) - Signature: {activate/1,cons/2,filter/2,from/1,head/1,if/3,primes/0,sieve/1,tail/1,activate#/1,cons#/2,filter#/2,from#/1 ,head#/1,if#/3,primes#/0,sieve#/1,tail#/1} / {0/0,divides/2,false/0,n__cons/2,n__filter/2,n__from/1,s/1 ,true/0,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0,c_6/0,c_7/3,c_8/1,c_9/0,c_10/0,c_11/1,c_12/1,c_13/2,c_14/3,c_15/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,filter#,from#,head#,if#,primes#,sieve# ,tail#} and constructors {0,divides,false,n__cons,n__filter,n__from,s,true} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,5,6,7,9,10,14,15} by application of Pre({1,5,6,7,9,10,14,15}) = {2,3,4,8,11,12,13}. Here rules are labelled as follows: 1: activate#(X) -> c_1() 2: activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) 3: activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) 4: activate#(n__from(X)) -> c_4(from#(X)) 5: cons#(X1,X2) -> c_5() 6: filter#(X1,X2) -> c_6() 7: filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) 8: from#(X) -> c_8(cons#(X,n__from(s(X)))) 9: from#(X) -> c_9() 10: head#(cons(X,Y)) -> c_10() 11: if#(false(),X,Y) -> c_11(activate#(Y)) 12: if#(true(),X,Y) -> c_12(activate#(X)) 13: primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) 14: sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) 15: tail#(cons(X,Y)) -> c_15(activate#(Y)) * Step 4: PredecessorEstimation WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) activate#(n__from(X)) -> c_4(from#(X)) from#(X) -> c_8(cons#(X,n__from(s(X)))) if#(false(),X,Y) -> c_11(activate#(Y)) if#(true(),X,Y) -> c_12(activate#(X)) primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) - Weak DPs: activate#(X) -> c_1() cons#(X1,X2) -> c_5() filter#(X1,X2) -> c_6() filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) from#(X) -> c_9() head#(cons(X,Y)) -> c_10() sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) tail#(cons(X,Y)) -> c_15(activate#(Y)) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__filter(X1,X2)) -> filter(X1,X2) activate(n__from(X)) -> from(X) cons(X1,X2) -> n__cons(X1,X2) filter(X1,X2) -> n__filter(X1,X2) filter(s(s(X)),cons(Y,Z)) -> if(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) head(cons(X,Y)) -> X if(false(),X,Y) -> activate(Y) if(true(),X,Y) -> activate(X) primes() -> sieve(from(s(s(0())))) sieve(cons(X,Y)) -> cons(X,n__filter(X,sieve(activate(Y)))) tail(cons(X,Y)) -> activate(Y) - Signature: {activate/1,cons/2,filter/2,from/1,head/1,if/3,primes/0,sieve/1,tail/1,activate#/1,cons#/2,filter#/2,from#/1 ,head#/1,if#/3,primes#/0,sieve#/1,tail#/1} / {0/0,divides/2,false/0,n__cons/2,n__filter/2,n__from/1,s/1 ,true/0,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0,c_6/0,c_7/3,c_8/1,c_9/0,c_10/0,c_11/1,c_12/1,c_13/2,c_14/3,c_15/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,filter#,from#,head#,if#,primes#,sieve# ,tail#} and constructors {0,divides,false,n__cons,n__filter,n__from,s,true} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,2,4} by application of Pre({1,2,4}) = {3,5,6,7}. Here rules are labelled as follows: 1: activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) 2: activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) 3: activate#(n__from(X)) -> c_4(from#(X)) 4: from#(X) -> c_8(cons#(X,n__from(s(X)))) 5: if#(false(),X,Y) -> c_11(activate#(Y)) 6: if#(true(),X,Y) -> c_12(activate#(X)) 7: primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) 8: activate#(X) -> c_1() 9: cons#(X1,X2) -> c_5() 10: filter#(X1,X2) -> c_6() 11: filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) 12: from#(X) -> c_9() 13: head#(cons(X,Y)) -> c_10() 14: sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) 15: tail#(cons(X,Y)) -> c_15(activate#(Y)) * Step 5: PredecessorEstimation WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: activate#(n__from(X)) -> c_4(from#(X)) if#(false(),X,Y) -> c_11(activate#(Y)) if#(true(),X,Y) -> c_12(activate#(X)) primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) - Weak DPs: activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) cons#(X1,X2) -> c_5() filter#(X1,X2) -> c_6() filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) from#(X) -> c_8(cons#(X,n__from(s(X)))) from#(X) -> c_9() head#(cons(X,Y)) -> c_10() sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) tail#(cons(X,Y)) -> c_15(activate#(Y)) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__filter(X1,X2)) -> filter(X1,X2) activate(n__from(X)) -> from(X) cons(X1,X2) -> n__cons(X1,X2) filter(X1,X2) -> n__filter(X1,X2) filter(s(s(X)),cons(Y,Z)) -> if(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) head(cons(X,Y)) -> X if(false(),X,Y) -> activate(Y) if(true(),X,Y) -> activate(X) primes() -> sieve(from(s(s(0())))) sieve(cons(X,Y)) -> cons(X,n__filter(X,sieve(activate(Y)))) tail(cons(X,Y)) -> activate(Y) - Signature: {activate/1,cons/2,filter/2,from/1,head/1,if/3,primes/0,sieve/1,tail/1,activate#/1,cons#/2,filter#/2,from#/1 ,head#/1,if#/3,primes#/0,sieve#/1,tail#/1} / {0/0,divides/2,false/0,n__cons/2,n__filter/2,n__from/1,s/1 ,true/0,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0,c_6/0,c_7/3,c_8/1,c_9/0,c_10/0,c_11/1,c_12/1,c_13/2,c_14/3,c_15/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,filter#,from#,head#,if#,primes#,sieve# ,tail#} and constructors {0,divides,false,n__cons,n__filter,n__from,s,true} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,4} by application of Pre({1,4}) = {2,3}. Here rules are labelled as follows: 1: activate#(n__from(X)) -> c_4(from#(X)) 2: if#(false(),X,Y) -> c_11(activate#(Y)) 3: if#(true(),X,Y) -> c_12(activate#(X)) 4: primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) 5: activate#(X) -> c_1() 6: activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) 7: activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) 8: cons#(X1,X2) -> c_5() 9: filter#(X1,X2) -> c_6() 10: filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) 11: from#(X) -> c_8(cons#(X,n__from(s(X)))) 12: from#(X) -> c_9() 13: head#(cons(X,Y)) -> c_10() 14: sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) 15: tail#(cons(X,Y)) -> c_15(activate#(Y)) * Step 6: PredecessorEstimation WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: if#(false(),X,Y) -> c_11(activate#(Y)) if#(true(),X,Y) -> c_12(activate#(X)) - Weak DPs: activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) activate#(n__from(X)) -> c_4(from#(X)) cons#(X1,X2) -> c_5() filter#(X1,X2) -> c_6() filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) from#(X) -> c_8(cons#(X,n__from(s(X)))) from#(X) -> c_9() head#(cons(X,Y)) -> c_10() primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) tail#(cons(X,Y)) -> c_15(activate#(Y)) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__filter(X1,X2)) -> filter(X1,X2) activate(n__from(X)) -> from(X) cons(X1,X2) -> n__cons(X1,X2) filter(X1,X2) -> n__filter(X1,X2) filter(s(s(X)),cons(Y,Z)) -> if(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) head(cons(X,Y)) -> X if(false(),X,Y) -> activate(Y) if(true(),X,Y) -> activate(X) primes() -> sieve(from(s(s(0())))) sieve(cons(X,Y)) -> cons(X,n__filter(X,sieve(activate(Y)))) tail(cons(X,Y)) -> activate(Y) - Signature: {activate/1,cons/2,filter/2,from/1,head/1,if/3,primes/0,sieve/1,tail/1,activate#/1,cons#/2,filter#/2,from#/1 ,head#/1,if#/3,primes#/0,sieve#/1,tail#/1} / {0/0,divides/2,false/0,n__cons/2,n__filter/2,n__from/1,s/1 ,true/0,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0,c_6/0,c_7/3,c_8/1,c_9/0,c_10/0,c_11/1,c_12/1,c_13/2,c_14/3,c_15/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,filter#,from#,head#,if#,primes#,sieve# ,tail#} and constructors {0,divides,false,n__cons,n__filter,n__from,s,true} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,2} by application of Pre({1,2}) = {}. Here rules are labelled as follows: 1: if#(false(),X,Y) -> c_11(activate#(Y)) 2: if#(true(),X,Y) -> c_12(activate#(X)) 3: activate#(X) -> c_1() 4: activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) 5: activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) 6: activate#(n__from(X)) -> c_4(from#(X)) 7: cons#(X1,X2) -> c_5() 8: filter#(X1,X2) -> c_6() 9: filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) 10: from#(X) -> c_8(cons#(X,n__from(s(X)))) 11: from#(X) -> c_9() 12: head#(cons(X,Y)) -> c_10() 13: primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) 14: sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) 15: tail#(cons(X,Y)) -> c_15(activate#(Y)) * Step 7: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) activate#(n__from(X)) -> c_4(from#(X)) cons#(X1,X2) -> c_5() filter#(X1,X2) -> c_6() filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) from#(X) -> c_8(cons#(X,n__from(s(X)))) from#(X) -> c_9() head#(cons(X,Y)) -> c_10() if#(false(),X,Y) -> c_11(activate#(Y)) if#(true(),X,Y) -> c_12(activate#(X)) primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) tail#(cons(X,Y)) -> c_15(activate#(Y)) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__filter(X1,X2)) -> filter(X1,X2) activate(n__from(X)) -> from(X) cons(X1,X2) -> n__cons(X1,X2) filter(X1,X2) -> n__filter(X1,X2) filter(s(s(X)),cons(Y,Z)) -> if(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) head(cons(X,Y)) -> X if(false(),X,Y) -> activate(Y) if(true(),X,Y) -> activate(X) primes() -> sieve(from(s(s(0())))) sieve(cons(X,Y)) -> cons(X,n__filter(X,sieve(activate(Y)))) tail(cons(X,Y)) -> activate(Y) - Signature: {activate/1,cons/2,filter/2,from/1,head/1,if/3,primes/0,sieve/1,tail/1,activate#/1,cons#/2,filter#/2,from#/1 ,head#/1,if#/3,primes#/0,sieve#/1,tail#/1} / {0/0,divides/2,false/0,n__cons/2,n__filter/2,n__from/1,s/1 ,true/0,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0,c_6/0,c_7/3,c_8/1,c_9/0,c_10/0,c_11/1,c_12/1,c_13/2,c_14/3,c_15/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,filter#,from#,head#,if#,primes#,sieve# ,tail#} and constructors {0,divides,false,n__cons,n__filter,n__from,s,true} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:W:activate#(X) -> c_1() 2:W:activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) -->_1 cons#(X1,X2) -> c_5():5 3:W:activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) -->_1 filter#(X1,X2) -> c_6():6 4:W:activate#(n__from(X)) -> c_4(from#(X)) -->_1 from#(X) -> c_8(cons#(X,n__from(s(X)))):8 -->_1 from#(X) -> c_9():9 5:W:cons#(X1,X2) -> c_5() 6:W:filter#(X1,X2) -> c_6() 7:W:filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) 8:W:from#(X) -> c_8(cons#(X,n__from(s(X)))) -->_1 cons#(X1,X2) -> c_5():5 9:W:from#(X) -> c_9() 10:W:head#(cons(X,Y)) -> c_10() 11:W:if#(false(),X,Y) -> c_11(activate#(Y)) -->_1 activate#(n__from(X)) -> c_4(from#(X)):4 -->_1 activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)):3 -->_1 activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)):2 -->_1 activate#(X) -> c_1():1 12:W:if#(true(),X,Y) -> c_12(activate#(X)) -->_1 activate#(n__from(X)) -> c_4(from#(X)):4 -->_1 activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)):3 -->_1 activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)):2 -->_1 activate#(X) -> c_1():1 13:W:primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) -->_2 from#(X) -> c_9():9 -->_2 from#(X) -> c_8(cons#(X,n__from(s(X)))):8 14:W:sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) 15:W:tail#(cons(X,Y)) -> c_15(activate#(Y)) The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 15: tail#(cons(X,Y)) -> c_15(activate#(Y)) 14: sieve#(cons(X,Y)) -> c_14(cons#(X,n__filter(X,sieve(activate(Y)))),sieve#(activate(Y)),activate#(Y)) 13: primes#() -> c_13(sieve#(from(s(s(0())))),from#(s(s(0())))) 12: if#(true(),X,Y) -> c_12(activate#(X)) 11: if#(false(),X,Y) -> c_11(activate#(Y)) 10: head#(cons(X,Y)) -> c_10() 7: filter#(s(s(X)),cons(Y,Z)) -> c_7(if#(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) ,activate#(Z) ,sieve#(Y)) 4: activate#(n__from(X)) -> c_4(from#(X)) 9: from#(X) -> c_9() 8: from#(X) -> c_8(cons#(X,n__from(s(X)))) 3: activate#(n__filter(X1,X2)) -> c_3(filter#(X1,X2)) 6: filter#(X1,X2) -> c_6() 2: activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) 5: cons#(X1,X2) -> c_5() 1: activate#(X) -> c_1() * Step 8: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__filter(X1,X2)) -> filter(X1,X2) activate(n__from(X)) -> from(X) cons(X1,X2) -> n__cons(X1,X2) filter(X1,X2) -> n__filter(X1,X2) filter(s(s(X)),cons(Y,Z)) -> if(divides(s(s(X)),Y) ,n__filter(s(s(X)),activate(Z)) ,n__cons(Y,n__filter(X,sieve(Y)))) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) head(cons(X,Y)) -> X if(false(),X,Y) -> activate(Y) if(true(),X,Y) -> activate(X) primes() -> sieve(from(s(s(0())))) sieve(cons(X,Y)) -> cons(X,n__filter(X,sieve(activate(Y)))) tail(cons(X,Y)) -> activate(Y) - Signature: {activate/1,cons/2,filter/2,from/1,head/1,if/3,primes/0,sieve/1,tail/1,activate#/1,cons#/2,filter#/2,from#/1 ,head#/1,if#/3,primes#/0,sieve#/1,tail#/1} / {0/0,divides/2,false/0,n__cons/2,n__filter/2,n__from/1,s/1 ,true/0,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0,c_6/0,c_7/3,c_8/1,c_9/0,c_10/0,c_11/1,c_12/1,c_13/2,c_14/3,c_15/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,filter#,from#,head#,if#,primes#,sieve# ,tail#} and constructors {0,divides,false,n__cons,n__filter,n__from,s,true} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(1))