WORST_CASE(?,O(n^1)) * Step 1: InnermostRuleRemoval WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) incr(cons(X,XS)) -> cons(s(X),n__incr(activate(XS))) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(cons(X,XS)) -> cons(X,n__cons(X,n__repItems(activate(XS)))) repItems(nil()) -> nil() tail(cons(X,XS)) -> activate(XS) take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(cons(X,XS),cons(Y,YS)) -> cons(pair(X,Y),n__zip(activate(XS),activate(YS))) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2} / {0/0,n__cons/2,n__incr/1 ,n__oddNs/0,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,cons,incr,oddNs,pairNs,repItems,tail,take ,zip} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: InnermostRuleRemoval + Details: Arguments of following rules are not normal-forms. incr(cons(X,XS)) -> cons(s(X),n__incr(activate(XS))) repItems(cons(X,XS)) -> cons(X,n__cons(X,n__repItems(activate(XS)))) tail(cons(X,XS)) -> activate(XS) take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) zip(cons(X,XS),cons(Y,YS)) -> cons(pair(X,Y),n__zip(activate(XS),activate(YS))) All above mentioned rules can be savely removed. * Step 2: DependencyPairs WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2} / {0/0,n__cons/2,n__incr/1 ,n__oddNs/0,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,cons,incr,oddNs,pairNs,repItems,tail,take ,zip} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: DependencyPairs {dpKind_ = WIDP} + Details: We add the following weak innermost dependency pairs: Strict DPs activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__oddNs()) -> c_4(oddNs#()) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) cons#(X1,X2) -> c_8() incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) oddNs#() -> c_11() pairNs#() -> c_12(cons#(0(),n__incr(n__oddNs()))) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() Weak DPs and mark the set of starting terms. * Step 3: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__oddNs()) -> c_4(oddNs#()) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) cons#(X1,X2) -> c_8() incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) oddNs#() -> c_11() pairNs#() -> c_12(cons#(0(),n__incr(n__oddNs()))) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Strict TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnTrs} + Details: The weightgap principle applies using the following constant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(cons) = {1}, uargs(incr) = {1}, uargs(repItems) = {1}, uargs(take) = {1,2}, uargs(zip) = {1,2}, uargs(cons#) = {1}, uargs(incr#) = {1}, uargs(repItems#) = {1}, uargs(take#) = {1,2}, uargs(zip#) = {1,2}, uargs(c_2) = {1}, uargs(c_3) = {1}, uargs(c_4) = {1}, uargs(c_5) = {1}, uargs(c_6) = {1}, uargs(c_7) = {1}, uargs(c_10) = {1}, uargs(c_12) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [0] p(activate) = [4] x1 + [1] p(cons) = [1] x1 + [2] p(incr) = [1] x1 + [2] p(n__cons) = [1] x1 + [1] p(n__incr) = [1] x1 + [1] p(n__oddNs) = [2] p(n__repItems) = [1] x1 + [3] p(n__take) = [1] x1 + [1] x2 + [2] p(n__zip) = [1] x1 + [1] x2 + [2] p(nil) = [0] p(oddNs) = [7] p(pair) = [1] x1 + [1] x2 + [0] p(pairNs) = [3] p(repItems) = [1] x1 + [4] p(s) = [1] x1 + [0] p(tail) = [0] p(take) = [1] x1 + [1] x2 + [4] p(zip) = [1] x1 + [1] x2 + [6] p(activate#) = [4] x1 + [0] p(cons#) = [1] x1 + [0] p(incr#) = [1] x1 + [0] p(oddNs#) = [0] p(pairNs#) = [0] p(repItems#) = [1] x1 + [0] p(tail#) = [0] p(take#) = [1] x1 + [1] x2 + [0] p(zip#) = [1] x1 + [1] x2 + [0] p(c_1) = [0] p(c_2) = [1] x1 + [0] p(c_3) = [1] x1 + [0] p(c_4) = [1] x1 + [0] p(c_5) = [1] x1 + [1] p(c_6) = [1] x1 + [2] p(c_7) = [1] x1 + [4] p(c_8) = [0] p(c_9) = [0] p(c_10) = [1] x1 + [1] p(c_11) = [0] p(c_12) = [1] x1 + [0] p(c_13) = [0] p(c_14) = [0] p(c_15) = [0] p(c_16) = [0] p(c_17) = [0] p(c_18) = [0] p(c_19) = [0] Following rules are strictly oriented: activate#(n__cons(X1,X2)) = [4] X1 + [4] > [4] X1 + [1] = c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) = [4] X + [4] > [4] X + [1] = c_3(incr#(activate(X))) activate#(n__oddNs()) = [8] > [0] = c_4(oddNs#()) activate#(n__repItems(X)) = [4] X + [12] > [4] X + [2] = c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) = [4] X1 + [4] X2 + [8] > [4] X1 + [4] X2 + [4] = c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) = [4] X1 + [4] X2 + [8] > [4] X1 + [4] X2 + [6] = c_7(zip#(activate(X1),activate(X2))) activate(X) = [4] X + [1] > [1] X + [0] = X activate(n__cons(X1,X2)) = [4] X1 + [5] > [4] X1 + [3] = cons(activate(X1),X2) activate(n__incr(X)) = [4] X + [5] > [4] X + [3] = incr(activate(X)) activate(n__oddNs()) = [9] > [7] = oddNs() activate(n__repItems(X)) = [4] X + [13] > [4] X + [5] = repItems(activate(X)) activate(n__take(X1,X2)) = [4] X1 + [4] X2 + [9] > [4] X1 + [4] X2 + [6] = take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) = [4] X1 + [4] X2 + [9] > [4] X1 + [4] X2 + [8] = zip(activate(X1),activate(X2)) cons(X1,X2) = [1] X1 + [2] > [1] X1 + [1] = n__cons(X1,X2) incr(X) = [1] X + [2] > [1] X + [1] = n__incr(X) oddNs() = [7] > [5] = incr(pairNs()) oddNs() = [7] > [2] = n__oddNs() pairNs() = [3] > [2] = cons(0(),n__incr(n__oddNs())) repItems(X) = [1] X + [4] > [1] X + [3] = n__repItems(X) repItems(nil()) = [4] > [0] = nil() take(X1,X2) = [1] X1 + [1] X2 + [4] > [1] X1 + [1] X2 + [2] = n__take(X1,X2) take(0(),XS) = [1] XS + [4] > [0] = nil() zip(X,nil()) = [1] X + [6] > [0] = nil() zip(X1,X2) = [1] X1 + [1] X2 + [6] > [1] X1 + [1] X2 + [2] = n__zip(X1,X2) zip(nil(),XS) = [1] XS + [6] > [0] = nil() Following rules are (at-least) weakly oriented: activate#(X) = [4] X + [0] >= [0] = c_1() cons#(X1,X2) = [1] X1 + [0] >= [0] = c_8() incr#(X) = [1] X + [0] >= [0] = c_9() oddNs#() = [0] >= [4] = c_10(incr#(pairNs())) oddNs#() = [0] >= [0] = c_11() pairNs#() = [0] >= [0] = c_12(cons#(0(),n__incr(n__oddNs()))) repItems#(X) = [1] X + [0] >= [0] = c_13() repItems#(nil()) = [0] >= [0] = c_14() take#(X1,X2) = [1] X1 + [1] X2 + [0] >= [0] = c_15() take#(0(),XS) = [1] XS + [0] >= [0] = c_16() zip#(X,nil()) = [1] X + [0] >= [0] = c_17() zip#(X1,X2) = [1] X1 + [1] X2 + [0] >= [0] = c_18() zip#(nil(),XS) = [1] XS + [0] >= [0] = c_19() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 4: PredecessorEstimation WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: activate#(X) -> c_1() cons#(X1,X2) -> c_8() incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) oddNs#() -> c_11() pairNs#() -> c_12(cons#(0(),n__incr(n__oddNs()))) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__oddNs()) -> c_4(oddNs#()) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1} by application of Pre({1}) = {}. Here rules are labelled as follows: 1: activate#(X) -> c_1() 2: cons#(X1,X2) -> c_8() 3: incr#(X) -> c_9() 4: oddNs#() -> c_10(incr#(pairNs())) 5: oddNs#() -> c_11() 6: pairNs#() -> c_12(cons#(0(),n__incr(n__oddNs()))) 7: repItems#(X) -> c_13() 8: repItems#(nil()) -> c_14() 9: take#(X1,X2) -> c_15() 10: take#(0(),XS) -> c_16() 11: zip#(X,nil()) -> c_17() 12: zip#(X1,X2) -> c_18() 13: zip#(nil(),XS) -> c_19() 14: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) 15: activate#(n__incr(X)) -> c_3(incr#(activate(X))) 16: activate#(n__oddNs()) -> c_4(oddNs#()) 17: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) 18: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) 19: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) * Step 5: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_8() incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) oddNs#() -> c_11() pairNs#() -> c_12(cons#(0(),n__incr(n__oddNs()))) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__oddNs()) -> c_4(oddNs#()) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:cons#(X1,X2) -> c_8() 2:S:incr#(X) -> c_9() 3:S:oddNs#() -> c_10(incr#(pairNs())) -->_1 incr#(X) -> c_9():2 4:S:oddNs#() -> c_11() 5:S:pairNs#() -> c_12(cons#(0(),n__incr(n__oddNs()))) -->_1 cons#(X1,X2) -> c_8():1 6:S:repItems#(X) -> c_13() 7:S:repItems#(nil()) -> c_14() 8:S:take#(X1,X2) -> c_15() 9:S:take#(0(),XS) -> c_16() 10:S:zip#(X,nil()) -> c_17() 11:S:zip#(X1,X2) -> c_18() 12:S:zip#(nil(),XS) -> c_19() 13:W:activate#(X) -> c_1() 14:W:activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) -->_1 cons#(X1,X2) -> c_8():1 15:W:activate#(n__incr(X)) -> c_3(incr#(activate(X))) -->_1 incr#(X) -> c_9():2 16:W:activate#(n__oddNs()) -> c_4(oddNs#()) -->_1 oddNs#() -> c_11():4 -->_1 oddNs#() -> c_10(incr#(pairNs())):3 17:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(nil()) -> c_14():7 -->_1 repItems#(X) -> c_13():6 18:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(0(),XS) -> c_16():9 -->_1 take#(X1,X2) -> c_15():8 19:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(nil(),XS) -> c_19():12 -->_1 zip#(X1,X2) -> c_18():11 -->_1 zip#(X,nil()) -> c_17():10 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 13: activate#(X) -> c_1() * Step 6: RemoveHeads WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_8() incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) oddNs#() -> c_11() pairNs#() -> c_12(cons#(0(),n__incr(n__oddNs()))) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__oddNs()) -> c_4(oddNs#()) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveHeads + Details: Consider the dependency graph 1:S:cons#(X1,X2) -> c_8() 2:S:incr#(X) -> c_9() 3:S:oddNs#() -> c_10(incr#(pairNs())) -->_1 incr#(X) -> c_9():2 4:S:oddNs#() -> c_11() 5:S:pairNs#() -> c_12(cons#(0(),n__incr(n__oddNs()))) -->_1 cons#(X1,X2) -> c_8():1 6:S:repItems#(X) -> c_13() 7:S:repItems#(nil()) -> c_14() 8:S:take#(X1,X2) -> c_15() 9:S:take#(0(),XS) -> c_16() 10:S:zip#(X,nil()) -> c_17() 11:S:zip#(X1,X2) -> c_18() 12:S:zip#(nil(),XS) -> c_19() 14:W:activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) -->_1 cons#(X1,X2) -> c_8():1 15:W:activate#(n__incr(X)) -> c_3(incr#(activate(X))) -->_1 incr#(X) -> c_9():2 16:W:activate#(n__oddNs()) -> c_4(oddNs#()) -->_1 oddNs#() -> c_11():4 -->_1 oddNs#() -> c_10(incr#(pairNs())):3 17:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(nil()) -> c_14():7 -->_1 repItems#(X) -> c_13():6 18:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(0(),XS) -> c_16():9 -->_1 take#(X1,X2) -> c_15():8 19:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(nil(),XS) -> c_19():12 -->_1 zip#(X1,X2) -> c_18():11 -->_1 zip#(X,nil()) -> c_17():10 Following roots of the dependency graph are removed, as the considered set of starting terms is closed under reduction with respect to these rules (modulo compound contexts). [(5,pairNs#() -> c_12(cons#(0(),n__incr(n__oddNs())))),(16,activate#(n__oddNs()) -> c_4(oddNs#()))] * Step 7: RemoveHeads WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_8() incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) oddNs#() -> c_11() repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveHeads + Details: Consider the dependency graph 1:S:cons#(X1,X2) -> c_8() 2:S:incr#(X) -> c_9() 3:S:oddNs#() -> c_10(incr#(pairNs())) -->_1 incr#(X) -> c_9():2 4:S:oddNs#() -> c_11() 6:S:repItems#(X) -> c_13() 7:S:repItems#(nil()) -> c_14() 8:S:take#(X1,X2) -> c_15() 9:S:take#(0(),XS) -> c_16() 10:S:zip#(X,nil()) -> c_17() 11:S:zip#(X1,X2) -> c_18() 12:S:zip#(nil(),XS) -> c_19() 14:W:activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) -->_1 cons#(X1,X2) -> c_8():1 15:W:activate#(n__incr(X)) -> c_3(incr#(activate(X))) -->_1 incr#(X) -> c_9():2 17:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(nil()) -> c_14():7 -->_1 repItems#(X) -> c_13():6 18:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(0(),XS) -> c_16():9 -->_1 take#(X1,X2) -> c_15():8 19:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(nil(),XS) -> c_19():12 -->_1 zip#(X1,X2) -> c_18():11 -->_1 zip#(X,nil()) -> c_17():10 Following roots of the dependency graph are removed, as the considered set of starting terms is closed under reduction with respect to these rules (modulo compound contexts). [(4,oddNs#() -> c_11())] * Step 8: Decompose WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_8() incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Decompose {onSelection = all cycle independent sub-graph, withBound = RelativeAdd} + Details: We analyse the complexity of following sub-problems (R) and (S). Problem (S) is obtained from the input problem by shifting strict rules from (R) into the weak component. Problem (R) - Strict DPs: cons#(X1,X2) -> c_8() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} Problem (S) - Strict DPs: incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) cons#(X1,X2) -> c_8() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} ** Step 8.a:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_8() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:cons#(X1,X2) -> c_8() 2:W:incr#(X) -> c_9() 3:W:oddNs#() -> c_10(incr#(pairNs())) -->_1 incr#(X) -> c_9():2 6:W:repItems#(X) -> c_13() 7:W:repItems#(nil()) -> c_14() 8:W:take#(X1,X2) -> c_15() 9:W:take#(0(),XS) -> c_16() 10:W:zip#(X,nil()) -> c_17() 11:W:zip#(X1,X2) -> c_18() 12:W:zip#(nil(),XS) -> c_19() 14:W:activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) -->_1 cons#(X1,X2) -> c_8():1 15:W:activate#(n__incr(X)) -> c_3(incr#(activate(X))) -->_1 incr#(X) -> c_9():2 17:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(X) -> c_13():6 -->_1 repItems#(nil()) -> c_14():7 18:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(X1,X2) -> c_15():8 -->_1 take#(0(),XS) -> c_16():9 19:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X,nil()) -> c_17():10 -->_1 zip#(X1,X2) -> c_18():11 -->_1 zip#(nil(),XS) -> c_19():12 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 19: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) 18: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) 17: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) 15: activate#(n__incr(X)) -> c_3(incr#(activate(X))) 12: zip#(nil(),XS) -> c_19() 11: zip#(X1,X2) -> c_18() 10: zip#(X,nil()) -> c_17() 9: take#(0(),XS) -> c_16() 8: take#(X1,X2) -> c_15() 7: repItems#(nil()) -> c_14() 6: repItems#(X) -> c_13() 3: oddNs#() -> c_10(incr#(pairNs())) 2: incr#(X) -> c_9() ** Step 8.a:2: Trivial WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_8() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Trivial + Details: Consider the dependency graph 1:S:cons#(X1,X2) -> c_8() 14:W:activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) -->_1 cons#(X1,X2) -> c_8():1 The dependency graph contains no loops, we remove all dependency pairs. ** Step 8.a:3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). ** Step 8.b:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) cons#(X1,X2) -> c_8() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:incr#(X) -> c_9() 2:S:oddNs#() -> c_10(incr#(pairNs())) -->_1 incr#(X) -> c_9():1 3:S:repItems#(X) -> c_13() 4:S:repItems#(nil()) -> c_14() 5:S:take#(X1,X2) -> c_15() 6:S:take#(0(),XS) -> c_16() 7:S:zip#(X,nil()) -> c_17() 8:S:zip#(X1,X2) -> c_18() 9:S:zip#(nil(),XS) -> c_19() 10:W:activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) -->_1 cons#(X1,X2) -> c_8():15 11:W:activate#(n__incr(X)) -> c_3(incr#(activate(X))) -->_1 incr#(X) -> c_9():1 12:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(nil()) -> c_14():4 -->_1 repItems#(X) -> c_13():3 13:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(0(),XS) -> c_16():6 -->_1 take#(X1,X2) -> c_15():5 14:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(nil(),XS) -> c_19():9 -->_1 zip#(X1,X2) -> c_18():8 -->_1 zip#(X,nil()) -> c_17():7 15:W:cons#(X1,X2) -> c_8() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 10: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) 15: cons#(X1,X2) -> c_8() ** Step 8.b:2: Decompose WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Decompose {onSelection = all cycle independent sub-graph, withBound = RelativeAdd} + Details: We analyse the complexity of following sub-problems (R) and (S). Problem (S) is obtained from the input problem by shifting strict rules from (R) into the weak component. Problem (R) - Strict DPs: incr#(X) -> c_9() - Weak DPs: activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) oddNs#() -> c_10(incr#(pairNs())) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} Problem (S) - Strict DPs: oddNs#() -> c_10(incr#(pairNs())) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) incr#(X) -> c_9() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} *** Step 8.b:2.a:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: incr#(X) -> c_9() - Weak DPs: activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) oddNs#() -> c_10(incr#(pairNs())) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:incr#(X) -> c_9() 2:W:oddNs#() -> c_10(incr#(pairNs())) -->_1 incr#(X) -> c_9():1 3:W:repItems#(X) -> c_13() 4:W:repItems#(nil()) -> c_14() 5:W:take#(X1,X2) -> c_15() 6:W:take#(0(),XS) -> c_16() 7:W:zip#(X,nil()) -> c_17() 8:W:zip#(X1,X2) -> c_18() 9:W:zip#(nil(),XS) -> c_19() 11:W:activate#(n__incr(X)) -> c_3(incr#(activate(X))) -->_1 incr#(X) -> c_9():1 12:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(X) -> c_13():3 -->_1 repItems#(nil()) -> c_14():4 13:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(X1,X2) -> c_15():5 -->_1 take#(0(),XS) -> c_16():6 14:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X,nil()) -> c_17():7 -->_1 zip#(X1,X2) -> c_18():8 -->_1 zip#(nil(),XS) -> c_19():9 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 14: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) 13: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) 12: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) 9: zip#(nil(),XS) -> c_19() 8: zip#(X1,X2) -> c_18() 7: zip#(X,nil()) -> c_17() 6: take#(0(),XS) -> c_16() 5: take#(X1,X2) -> c_15() 4: repItems#(nil()) -> c_14() 3: repItems#(X) -> c_13() *** Step 8.b:2.a:2: Trivial WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: incr#(X) -> c_9() - Weak DPs: activate#(n__incr(X)) -> c_3(incr#(activate(X))) oddNs#() -> c_10(incr#(pairNs())) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Trivial + Details: Consider the dependency graph 1:S:incr#(X) -> c_9() 2:W:oddNs#() -> c_10(incr#(pairNs())) -->_1 incr#(X) -> c_9():1 11:W:activate#(n__incr(X)) -> c_3(incr#(activate(X))) -->_1 incr#(X) -> c_9():1 The dependency graph contains no loops, we remove all dependency pairs. *** Step 8.b:2.a:3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). *** Step 8.b:2.b:1: PredecessorEstimation WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: oddNs#() -> c_10(incr#(pairNs())) repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) incr#(X) -> c_9() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1} by application of Pre({1}) = {}. Here rules are labelled as follows: 1: oddNs#() -> c_10(incr#(pairNs())) 2: repItems#(X) -> c_13() 3: repItems#(nil()) -> c_14() 4: take#(X1,X2) -> c_15() 5: take#(0(),XS) -> c_16() 6: zip#(X,nil()) -> c_17() 7: zip#(X1,X2) -> c_18() 8: zip#(nil(),XS) -> c_19() 9: activate#(n__incr(X)) -> c_3(incr#(activate(X))) 10: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) 11: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) 12: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) 13: incr#(X) -> c_9() *** Step 8.b:2.b:2: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__incr(X)) -> c_3(incr#(activate(X))) activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) incr#(X) -> c_9() oddNs#() -> c_10(incr#(pairNs())) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:repItems#(X) -> c_13() 2:S:repItems#(nil()) -> c_14() 3:S:take#(X1,X2) -> c_15() 4:S:take#(0(),XS) -> c_16() 5:S:zip#(X,nil()) -> c_17() 6:S:zip#(X1,X2) -> c_18() 7:S:zip#(nil(),XS) -> c_19() 8:W:activate#(n__incr(X)) -> c_3(incr#(activate(X))) -->_1 incr#(X) -> c_9():12 9:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(nil()) -> c_14():2 -->_1 repItems#(X) -> c_13():1 10:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(0(),XS) -> c_16():4 -->_1 take#(X1,X2) -> c_15():3 11:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(nil(),XS) -> c_19():7 -->_1 zip#(X1,X2) -> c_18():6 -->_1 zip#(X,nil()) -> c_17():5 12:W:incr#(X) -> c_9() 13:W:oddNs#() -> c_10(incr#(pairNs())) -->_1 incr#(X) -> c_9():12 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 13: oddNs#() -> c_10(incr#(pairNs())) 8: activate#(n__incr(X)) -> c_3(incr#(activate(X))) 12: incr#(X) -> c_9() *** Step 8.b:2.b:3: Decompose WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: repItems#(X) -> c_13() repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Decompose {onSelection = all cycle independent sub-graph, withBound = RelativeAdd} + Details: We analyse the complexity of following sub-problems (R) and (S). Problem (S) is obtained from the input problem by shifting strict rules from (R) into the weak component. Problem (R) - Strict DPs: repItems#(X) -> c_13() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} Problem (S) - Strict DPs: repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) repItems#(X) -> c_13() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} **** Step 8.b:2.b:3.a:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: repItems#(X) -> c_13() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:repItems#(X) -> c_13() 2:W:repItems#(nil()) -> c_14() 3:W:take#(X1,X2) -> c_15() 4:W:take#(0(),XS) -> c_16() 5:W:zip#(X,nil()) -> c_17() 6:W:zip#(X1,X2) -> c_18() 7:W:zip#(nil(),XS) -> c_19() 9:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(X) -> c_13():1 -->_1 repItems#(nil()) -> c_14():2 10:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(X1,X2) -> c_15():3 -->_1 take#(0(),XS) -> c_16():4 11:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X,nil()) -> c_17():5 -->_1 zip#(X1,X2) -> c_18():6 -->_1 zip#(nil(),XS) -> c_19():7 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 11: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) 10: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) 7: zip#(nil(),XS) -> c_19() 6: zip#(X1,X2) -> c_18() 5: zip#(X,nil()) -> c_17() 4: take#(0(),XS) -> c_16() 3: take#(X1,X2) -> c_15() 2: repItems#(nil()) -> c_14() **** Step 8.b:2.b:3.a:2: Trivial WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: repItems#(X) -> c_13() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Trivial + Details: Consider the dependency graph 1:S:repItems#(X) -> c_13() 9:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(X) -> c_13():1 The dependency graph contains no loops, we remove all dependency pairs. **** Step 8.b:2.b:3.a:3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). **** Step 8.b:2.b:3.b:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) repItems#(X) -> c_13() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:repItems#(nil()) -> c_14() 2:S:take#(X1,X2) -> c_15() 3:S:take#(0(),XS) -> c_16() 4:S:zip#(X,nil()) -> c_17() 5:S:zip#(X1,X2) -> c_18() 6:S:zip#(nil(),XS) -> c_19() 7:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(X) -> c_13():10 -->_1 repItems#(nil()) -> c_14():1 8:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(0(),XS) -> c_16():3 -->_1 take#(X1,X2) -> c_15():2 9:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(nil(),XS) -> c_19():6 -->_1 zip#(X1,X2) -> c_18():5 -->_1 zip#(X,nil()) -> c_17():4 10:W:repItems#(X) -> c_13() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 10: repItems#(X) -> c_13() **** Step 8.b:2.b:3.b:2: Decompose WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: repItems#(nil()) -> c_14() take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Decompose {onSelection = all cycle independent sub-graph, withBound = RelativeAdd} + Details: We analyse the complexity of following sub-problems (R) and (S). Problem (S) is obtained from the input problem by shifting strict rules from (R) into the weak component. Problem (R) - Strict DPs: repItems#(nil()) -> c_14() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} Problem (S) - Strict DPs: take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) repItems#(nil()) -> c_14() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} ***** Step 8.b:2.b:3.b:2.a:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: repItems#(nil()) -> c_14() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:repItems#(nil()) -> c_14() 2:W:take#(X1,X2) -> c_15() 3:W:take#(0(),XS) -> c_16() 4:W:zip#(X,nil()) -> c_17() 5:W:zip#(X1,X2) -> c_18() 6:W:zip#(nil(),XS) -> c_19() 7:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(nil()) -> c_14():1 8:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(X1,X2) -> c_15():2 -->_1 take#(0(),XS) -> c_16():3 9:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X,nil()) -> c_17():4 -->_1 zip#(X1,X2) -> c_18():5 -->_1 zip#(nil(),XS) -> c_19():6 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 9: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) 8: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) 6: zip#(nil(),XS) -> c_19() 5: zip#(X1,X2) -> c_18() 4: zip#(X,nil()) -> c_17() 3: take#(0(),XS) -> c_16() 2: take#(X1,X2) -> c_15() ***** Step 8.b:2.b:3.b:2.a:2: Trivial WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: repItems#(nil()) -> c_14() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Trivial + Details: Consider the dependency graph 1:S:repItems#(nil()) -> c_14() 7:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(nil()) -> c_14():1 The dependency graph contains no loops, we remove all dependency pairs. ***** Step 8.b:2.b:3.b:2.a:3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). ***** Step 8.b:2.b:3.b:2.b:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) repItems#(nil()) -> c_14() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:take#(X1,X2) -> c_15() 2:S:take#(0(),XS) -> c_16() 3:S:zip#(X,nil()) -> c_17() 4:S:zip#(X1,X2) -> c_18() 5:S:zip#(nil(),XS) -> c_19() 6:W:activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) -->_1 repItems#(nil()) -> c_14():9 7:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(0(),XS) -> c_16():2 -->_1 take#(X1,X2) -> c_15():1 8:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(nil(),XS) -> c_19():5 -->_1 zip#(X1,X2) -> c_18():4 -->_1 zip#(X,nil()) -> c_17():3 9:W:repItems#(nil()) -> c_14() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 6: activate#(n__repItems(X)) -> c_5(repItems#(activate(X))) 9: repItems#(nil()) -> c_14() ***** Step 8.b:2.b:3.b:2.b:2: Decompose WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: take#(X1,X2) -> c_15() take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Decompose {onSelection = all cycle independent sub-graph, withBound = RelativeAdd} + Details: We analyse the complexity of following sub-problems (R) and (S). Problem (S) is obtained from the input problem by shifting strict rules from (R) into the weak component. Problem (R) - Strict DPs: take#(X1,X2) -> c_15() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} Problem (S) - Strict DPs: take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) take#(X1,X2) -> c_15() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} ****** Step 8.b:2.b:3.b:2.b:2.a:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: take#(X1,X2) -> c_15() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:take#(X1,X2) -> c_15() 2:W:take#(0(),XS) -> c_16() 3:W:zip#(X,nil()) -> c_17() 4:W:zip#(X1,X2) -> c_18() 5:W:zip#(nil(),XS) -> c_19() 7:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(X1,X2) -> c_15():1 -->_1 take#(0(),XS) -> c_16():2 8:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X,nil()) -> c_17():3 -->_1 zip#(X1,X2) -> c_18():4 -->_1 zip#(nil(),XS) -> c_19():5 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 8: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) 5: zip#(nil(),XS) -> c_19() 4: zip#(X1,X2) -> c_18() 3: zip#(X,nil()) -> c_17() 2: take#(0(),XS) -> c_16() ****** Step 8.b:2.b:3.b:2.b:2.a:2: Trivial WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: take#(X1,X2) -> c_15() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Trivial + Details: Consider the dependency graph 1:S:take#(X1,X2) -> c_15() 7:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(X1,X2) -> c_15():1 The dependency graph contains no loops, we remove all dependency pairs. ****** Step 8.b:2.b:3.b:2.b:2.a:3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). ****** Step 8.b:2.b:3.b:2.b:2.b:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) take#(X1,X2) -> c_15() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:take#(0(),XS) -> c_16() 2:S:zip#(X,nil()) -> c_17() 3:S:zip#(X1,X2) -> c_18() 4:S:zip#(nil(),XS) -> c_19() 5:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(X1,X2) -> c_15():7 -->_1 take#(0(),XS) -> c_16():1 6:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(nil(),XS) -> c_19():4 -->_1 zip#(X1,X2) -> c_18():3 -->_1 zip#(X,nil()) -> c_17():2 7:W:take#(X1,X2) -> c_15() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 7: take#(X1,X2) -> c_15() ****** Step 8.b:2.b:3.b:2.b:2.b:2: Decompose WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: take#(0(),XS) -> c_16() zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Decompose {onSelection = all cycle independent sub-graph, withBound = RelativeAdd} + Details: We analyse the complexity of following sub-problems (R) and (S). Problem (S) is obtained from the input problem by shifting strict rules from (R) into the weak component. Problem (R) - Strict DPs: take#(0(),XS) -> c_16() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} Problem (S) - Strict DPs: zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) take#(0(),XS) -> c_16() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} ******* Step 8.b:2.b:3.b:2.b:2.b:2.a:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: take#(0(),XS) -> c_16() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:take#(0(),XS) -> c_16() 2:W:zip#(X,nil()) -> c_17() 3:W:zip#(X1,X2) -> c_18() 4:W:zip#(nil(),XS) -> c_19() 5:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(0(),XS) -> c_16():1 6:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X,nil()) -> c_17():2 -->_1 zip#(X1,X2) -> c_18():3 -->_1 zip#(nil(),XS) -> c_19():4 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 6: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) 4: zip#(nil(),XS) -> c_19() 3: zip#(X1,X2) -> c_18() 2: zip#(X,nil()) -> c_17() ******* Step 8.b:2.b:3.b:2.b:2.b:2.a:2: Trivial WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: take#(0(),XS) -> c_16() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Trivial + Details: Consider the dependency graph 1:S:take#(0(),XS) -> c_16() 5:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(0(),XS) -> c_16():1 The dependency graph contains no loops, we remove all dependency pairs. ******* Step 8.b:2.b:3.b:2.b:2.b:2.a:3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). ******* Step 8.b:2.b:3.b:2.b:2.b:2.b:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) take#(0(),XS) -> c_16() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:zip#(X,nil()) -> c_17() 2:S:zip#(X1,X2) -> c_18() 3:S:zip#(nil(),XS) -> c_19() 4:W:activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) -->_1 take#(0(),XS) -> c_16():6 5:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(nil(),XS) -> c_19():3 -->_1 zip#(X1,X2) -> c_18():2 -->_1 zip#(X,nil()) -> c_17():1 6:W:take#(0(),XS) -> c_16() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 4: activate#(n__take(X1,X2)) -> c_6(take#(activate(X1),activate(X2))) 6: take#(0(),XS) -> c_16() ******* Step 8.b:2.b:3.b:2.b:2.b:2.b:2: Decompose WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: zip#(X,nil()) -> c_17() zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Decompose {onSelection = all cycle independent sub-graph, withBound = RelativeAdd} + Details: We analyse the complexity of following sub-problems (R) and (S). Problem (S) is obtained from the input problem by shifting strict rules from (R) into the weak component. Problem (R) - Strict DPs: zip#(X,nil()) -> c_17() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} Problem (S) - Strict DPs: zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) zip#(X,nil()) -> c_17() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} ******** Step 8.b:2.b:3.b:2.b:2.b:2.b:2.a:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: zip#(X,nil()) -> c_17() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:zip#(X,nil()) -> c_17() 2:W:zip#(X1,X2) -> c_18() 3:W:zip#(nil(),XS) -> c_19() 5:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X,nil()) -> c_17():1 -->_1 zip#(X1,X2) -> c_18():2 -->_1 zip#(nil(),XS) -> c_19():3 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 3: zip#(nil(),XS) -> c_19() 2: zip#(X1,X2) -> c_18() ******** Step 8.b:2.b:3.b:2.b:2.b:2.b:2.a:2: Trivial WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: zip#(X,nil()) -> c_17() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Trivial + Details: Consider the dependency graph 1:S:zip#(X,nil()) -> c_17() 5:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X,nil()) -> c_17():1 The dependency graph contains no loops, we remove all dependency pairs. ******** Step 8.b:2.b:3.b:2.b:2.b:2.b:2.a:3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). ******** Step 8.b:2.b:3.b:2.b:2.b:2.b:2.b:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) zip#(X,nil()) -> c_17() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:zip#(X1,X2) -> c_18() 2:S:zip#(nil(),XS) -> c_19() 3:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X,nil()) -> c_17():4 -->_1 zip#(nil(),XS) -> c_19():2 -->_1 zip#(X1,X2) -> c_18():1 4:W:zip#(X,nil()) -> c_17() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 4: zip#(X,nil()) -> c_17() ******** Step 8.b:2.b:3.b:2.b:2.b:2.b:2.b:2: Decompose WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: zip#(X1,X2) -> c_18() zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Decompose {onSelection = all cycle independent sub-graph, withBound = RelativeAdd} + Details: We analyse the complexity of following sub-problems (R) and (S). Problem (S) is obtained from the input problem by shifting strict rules from (R) into the weak component. Problem (R) - Strict DPs: zip#(X1,X2) -> c_18() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} Problem (S) - Strict DPs: zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) zip#(X1,X2) -> c_18() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0 ,n__repItems/1,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0 ,c_10/1,c_11/0,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} ********* Step 8.b:2.b:3.b:2.b:2.b:2.b:2.b:2.a:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: zip#(X1,X2) -> c_18() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) zip#(nil(),XS) -> c_19() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:zip#(X1,X2) -> c_18() 2:W:zip#(nil(),XS) -> c_19() 3:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X1,X2) -> c_18():1 -->_1 zip#(nil(),XS) -> c_19():2 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 2: zip#(nil(),XS) -> c_19() ********* Step 8.b:2.b:3.b:2.b:2.b:2.b:2.b:2.a:2: Trivial WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: zip#(X1,X2) -> c_18() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Trivial + Details: Consider the dependency graph 1:S:zip#(X1,X2) -> c_18() 3:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X1,X2) -> c_18():1 The dependency graph contains no loops, we remove all dependency pairs. ********* Step 8.b:2.b:3.b:2.b:2.b:2.b:2.b:2.a:3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). ********* Step 8.b:2.b:3.b:2.b:2.b:2.b:2.b:2.b:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) zip#(X1,X2) -> c_18() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:zip#(nil(),XS) -> c_19() 2:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(X1,X2) -> c_18():3 -->_1 zip#(nil(),XS) -> c_19():1 3:W:zip#(X1,X2) -> c_18() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 3: zip#(X1,X2) -> c_18() ********* Step 8.b:2.b:3.b:2.b:2.b:2.b:2.b:2.b:2: Trivial WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: zip#(nil(),XS) -> c_19() - Weak DPs: activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: Trivial + Details: Consider the dependency graph 1:S:zip#(nil(),XS) -> c_19() 2:W:activate#(n__zip(X1,X2)) -> c_7(zip#(activate(X1),activate(X2))) -->_1 zip#(nil(),XS) -> c_19():1 The dependency graph contains no loops, we remove all dependency pairs. ********* Step 8.b:2.b:3.b:2.b:2.b:2.b:2.b:2.b:3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__incr(X)) -> incr(activate(X)) activate(n__oddNs()) -> oddNs() activate(n__repItems(X)) -> repItems(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(n__zip(X1,X2)) -> zip(activate(X1),activate(X2)) cons(X1,X2) -> n__cons(X1,X2) incr(X) -> n__incr(X) oddNs() -> incr(pairNs()) oddNs() -> n__oddNs() pairNs() -> cons(0(),n__incr(n__oddNs())) repItems(X) -> n__repItems(X) repItems(nil()) -> nil() take(X1,X2) -> n__take(X1,X2) take(0(),XS) -> nil() zip(X,nil()) -> nil() zip(X1,X2) -> n__zip(X1,X2) zip(nil(),XS) -> nil() - Signature: {activate/1,cons/2,incr/1,oddNs/0,pairNs/0,repItems/1,tail/1,take/2,zip/2,activate#/1,cons#/2,incr#/1 ,oddNs#/0,pairNs#/0,repItems#/1,tail#/1,take#/2,zip#/2} / {0/0,n__cons/2,n__incr/1,n__oddNs/0,n__repItems/1 ,n__take/2,n__zip/2,nil/0,pair/2,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/0,c_10/1,c_11/0 ,c_12/1,c_13/0,c_14/0,c_15/0,c_16/0,c_17/0,c_18/0,c_19/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,incr#,oddNs#,pairNs#,repItems#,tail# ,take#,zip#} and constructors {0,n__cons,n__incr,n__oddNs,n__repItems,n__take,n__zip,nil,pair,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))