WORST_CASE(?,O(n^1)) * Step 1: InnermostRuleRemoval WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: 2nd(cons(X,n__cons(Y,Z))) -> activate(Y) activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(n__s(X))) from(X) -> n__from(X) s(X) -> n__s(X) - Signature: {2nd/1,activate/1,cons/2,from/1,s/1} / {n__cons/2,n__from/1,n__s/1} - Obligation: innermost runtime complexity wrt. defined symbols {2nd,activate,cons,from,s} and constructors {n__cons ,n__from,n__s} + Applied Processor: InnermostRuleRemoval + Details: Arguments of following rules are not normal-forms. 2nd(cons(X,n__cons(Y,Z))) -> activate(Y) 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__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(n__s(X))) from(X) -> n__from(X) s(X) -> n__s(X) - Signature: {2nd/1,activate/1,cons/2,from/1,s/1} / {n__cons/2,n__from/1,n__s/1} - Obligation: innermost runtime complexity wrt. defined symbols {2nd,activate,cons,from,s} and constructors {n__cons ,n__from,n__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__from(X)) -> c_3(from#(activate(X))) activate#(n__s(X)) -> c_4(s#(activate(X))) cons#(X1,X2) -> c_5() from#(X) -> c_6(cons#(X,n__from(n__s(X)))) from#(X) -> c_7() s#(X) -> c_8() 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__from(X)) -> c_3(from#(activate(X))) activate#(n__s(X)) -> c_4(s#(activate(X))) cons#(X1,X2) -> c_5() from#(X) -> c_6(cons#(X,n__from(n__s(X)))) from#(X) -> c_7() s#(X) -> c_8() - Strict TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(n__s(X))) from(X) -> n__from(X) s(X) -> n__s(X) - Signature: {2nd/1,activate/1,cons/2,from/1,s/1,2nd#/1,activate#/1,cons#/2,from#/1,s#/1} / {n__cons/2,n__from/1,n__s/1 ,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0,c_6/1,c_7/0,c_8/0} - Obligation: innermost runtime complexity wrt. defined symbols {2nd#,activate#,cons#,from#,s#} and constructors {n__cons ,n__from,n__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(from) = {1}, uargs(s) = {1}, uargs(cons#) = {1}, uargs(from#) = {1}, uargs(s#) = {1}, uargs(c_2) = {1}, uargs(c_3) = {1}, uargs(c_4) = {1}, uargs(c_6) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(2nd) = [0] p(activate) = [2] x1 + [2] p(cons) = [1] x1 + [9] p(from) = [1] x1 + [11] p(n__cons) = [1] x1 + [8] p(n__from) = [1] x1 + [8] p(n__s) = [1] x1 + [2] p(s) = [1] x1 + [3] p(2nd#) = [1] p(activate#) = [2] x1 + [2] p(cons#) = [1] x1 + [0] p(from#) = [1] x1 + [2] p(s#) = [1] x1 + [4] p(c_1) = [0] p(c_2) = [1] x1 + [1] p(c_3) = [1] x1 + [0] p(c_4) = [1] x1 + [0] p(c_5) = [1] p(c_6) = [1] x1 + [0] p(c_7) = [0] p(c_8) = [1] Following rules are strictly oriented: activate#(X) = [2] X + [2] > [0] = c_1() activate#(n__cons(X1,X2)) = [2] X1 + [18] > [2] X1 + [3] = c_2(cons#(activate(X1),X2)) activate#(n__from(X)) = [2] X + [18] > [2] X + [4] = c_3(from#(activate(X))) from#(X) = [1] X + [2] > [1] X + [0] = c_6(cons#(X,n__from(n__s(X)))) from#(X) = [1] X + [2] > [0] = c_7() s#(X) = [1] X + [4] > [1] = c_8() activate(X) = [2] X + [2] > [1] X + [0] = X activate(n__cons(X1,X2)) = [2] X1 + [18] > [2] X1 + [11] = cons(activate(X1),X2) activate(n__from(X)) = [2] X + [18] > [2] X + [13] = from(activate(X)) activate(n__s(X)) = [2] X + [6] > [2] X + [5] = s(activate(X)) cons(X1,X2) = [1] X1 + [9] > [1] X1 + [8] = n__cons(X1,X2) from(X) = [1] X + [11] > [1] X + [9] = cons(X,n__from(n__s(X))) from(X) = [1] X + [11] > [1] X + [8] = n__from(X) s(X) = [1] X + [3] > [1] X + [2] = n__s(X) Following rules are (at-least) weakly oriented: activate#(n__s(X)) = [2] X + [6] >= [2] X + [6] = c_4(s#(activate(X))) cons#(X1,X2) = [1] X1 + [0] >= [1] = c_5() 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#(n__s(X)) -> c_4(s#(activate(X))) cons#(X1,X2) -> c_5() - Weak DPs: activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__from(X)) -> c_3(from#(activate(X))) from#(X) -> c_6(cons#(X,n__from(n__s(X)))) from#(X) -> c_7() s#(X) -> c_8() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(n__s(X))) from(X) -> n__from(X) s(X) -> n__s(X) - Signature: {2nd/1,activate/1,cons/2,from/1,s/1,2nd#/1,activate#/1,cons#/2,from#/1,s#/1} / {n__cons/2,n__from/1,n__s/1 ,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0,c_6/1,c_7/0,c_8/0} - Obligation: innermost runtime complexity wrt. defined symbols {2nd#,activate#,cons#,from#,s#} and constructors {n__cons ,n__from,n__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#(n__s(X)) -> c_4(s#(activate(X))) 2: cons#(X1,X2) -> c_5() 3: activate#(X) -> c_1() 4: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) 5: activate#(n__from(X)) -> c_3(from#(activate(X))) 6: from#(X) -> c_6(cons#(X,n__from(n__s(X)))) 7: from#(X) -> c_7() 8: s#(X) -> c_8() * Step 5: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_5() - Weak DPs: activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__from(X)) -> c_3(from#(activate(X))) activate#(n__s(X)) -> c_4(s#(activate(X))) from#(X) -> c_6(cons#(X,n__from(n__s(X)))) from#(X) -> c_7() s#(X) -> c_8() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(n__s(X))) from(X) -> n__from(X) s(X) -> n__s(X) - Signature: {2nd/1,activate/1,cons/2,from/1,s/1,2nd#/1,activate#/1,cons#/2,from#/1,s#/1} / {n__cons/2,n__from/1,n__s/1 ,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0,c_6/1,c_7/0,c_8/0} - Obligation: innermost runtime complexity wrt. defined symbols {2nd#,activate#,cons#,from#,s#} and constructors {n__cons ,n__from,n__s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:cons#(X1,X2) -> c_5() 2:W:activate#(X) -> c_1() 3:W:activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) -->_1 cons#(X1,X2) -> c_5():1 4:W:activate#(n__from(X)) -> c_3(from#(activate(X))) -->_1 from#(X) -> c_6(cons#(X,n__from(n__s(X)))):6 -->_1 from#(X) -> c_7():7 5:W:activate#(n__s(X)) -> c_4(s#(activate(X))) -->_1 s#(X) -> c_8():8 6:W:from#(X) -> c_6(cons#(X,n__from(n__s(X)))) -->_1 cons#(X1,X2) -> c_5():1 7:W:from#(X) -> c_7() 8:W:s#(X) -> c_8() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 5: activate#(n__s(X)) -> c_4(s#(activate(X))) 8: s#(X) -> c_8() 7: from#(X) -> c_7() 2: activate#(X) -> c_1() * Step 6: Trivial WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_5() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) activate#(n__from(X)) -> c_3(from#(activate(X))) from#(X) -> c_6(cons#(X,n__from(n__s(X)))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(n__s(X))) from(X) -> n__from(X) s(X) -> n__s(X) - Signature: {2nd/1,activate/1,cons/2,from/1,s/1,2nd#/1,activate#/1,cons#/2,from#/1,s#/1} / {n__cons/2,n__from/1,n__s/1 ,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0,c_6/1,c_7/0,c_8/0} - Obligation: innermost runtime complexity wrt. defined symbols {2nd#,activate#,cons#,from#,s#} and constructors {n__cons ,n__from,n__s} + Applied Processor: Trivial + Details: Consider the dependency graph 1:S:cons#(X1,X2) -> c_5() 3:W:activate#(n__cons(X1,X2)) -> c_2(cons#(activate(X1),X2)) -->_1 cons#(X1,X2) -> c_5():1 4:W:activate#(n__from(X)) -> c_3(from#(activate(X))) -->_1 from#(X) -> c_6(cons#(X,n__from(n__s(X)))):6 6:W:from#(X) -> c_6(cons#(X,n__from(n__s(X)))) -->_1 cons#(X1,X2) -> c_5():1 The dependency graph contains no loops, we remove all dependency pairs. * Step 7: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(activate(X1),X2) activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(n__s(X))) from(X) -> n__from(X) s(X) -> n__s(X) - Signature: {2nd/1,activate/1,cons/2,from/1,s/1,2nd#/1,activate#/1,cons#/2,from#/1,s#/1} / {n__cons/2,n__from/1,n__s/1 ,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0,c_6/1,c_7/0,c_8/0} - Obligation: innermost runtime complexity wrt. defined symbols {2nd#,activate#,cons#,from#,s#} and constructors {n__cons ,n__from,n__s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))