MAYBE * Step 1: DependencyPairs MAYBE + Considered Problem: - Strict TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__from(X)) -> from(X) activate(n__nil()) -> nil() cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) length(n__cons(X,Y)) -> s(length1(activate(Y))) length(n__nil()) -> 0() length1(X) -> length(activate(X)) nil() -> n__nil() - Signature: {activate/1,cons/2,from/1,length/1,length1/1,nil/0} / {0/0,n__cons/2,n__from/1,n__nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,cons,from,length,length1 ,nil} and constructors {0,n__cons,n__from,n__nil,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#(X1,X2)) activate#(n__from(X)) -> c_3(from#(X)) activate#(n__nil()) -> c_4(nil#()) cons#(X1,X2) -> c_5() from#(X) -> c_6(cons#(X,n__from(s(X)))) from#(X) -> c_7() length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) length#(n__nil()) -> c_9() length1#(X) -> c_10(length#(activate(X))) nil#() -> c_11() Weak DPs and mark the set of starting terms. * Step 2: UsableRules MAYBE + Considered Problem: - Strict DPs: activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__from(X)) -> c_3(from#(X)) activate#(n__nil()) -> c_4(nil#()) cons#(X1,X2) -> c_5() from#(X) -> c_6(cons#(X,n__from(s(X)))) from#(X) -> c_7() length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) length#(n__nil()) -> c_9() length1#(X) -> c_10(length#(activate(X))) nil#() -> c_11() - Strict TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__from(X)) -> from(X) activate(n__nil()) -> nil() cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) length(n__cons(X,Y)) -> s(length1(activate(Y))) length(n__nil()) -> 0() length1(X) -> length(activate(X)) nil() -> n__nil() - Signature: {activate/1,cons/2,from/1,length/1,length1/1,nil/0,activate#/1,cons#/2,from#/1,length#/1,length1#/1 ,nil#/0} / {0/0,n__cons/2,n__from/1,n__nil/0,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/1,c_9/0 ,c_10/1,c_11/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,from#,length#,length1# ,nil#} and constructors {0,n__cons,n__from,n__nil,s} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__from(X)) -> from(X) activate(n__nil()) -> nil() cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) nil() -> n__nil() activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__from(X)) -> c_3(from#(X)) activate#(n__nil()) -> c_4(nil#()) cons#(X1,X2) -> c_5() from#(X) -> c_6(cons#(X,n__from(s(X)))) from#(X) -> c_7() length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) length#(n__nil()) -> c_9() length1#(X) -> c_10(length#(activate(X))) nil#() -> c_11() * Step 3: WeightGap MAYBE + Considered Problem: - Strict DPs: activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__from(X)) -> c_3(from#(X)) activate#(n__nil()) -> c_4(nil#()) cons#(X1,X2) -> c_5() from#(X) -> c_6(cons#(X,n__from(s(X)))) from#(X) -> c_7() length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) length#(n__nil()) -> c_9() length1#(X) -> c_10(length#(activate(X))) nil#() -> c_11() - Strict TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__from(X)) -> from(X) activate(n__nil()) -> nil() cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) nil() -> n__nil() - Signature: {activate/1,cons/2,from/1,length/1,length1/1,nil/0,activate#/1,cons#/2,from#/1,length#/1,length1#/1 ,nil#/0} / {0/0,n__cons/2,n__from/1,n__nil/0,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/1,c_9/0 ,c_10/1,c_11/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,from#,length#,length1# ,nil#} and constructors {0,n__cons,n__from,n__nil,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(length#) = {1}, uargs(length1#) = {1}, uargs(c_2) = {1}, uargs(c_3) = {1}, uargs(c_4) = {1}, uargs(c_6) = {1}, uargs(c_8) = {1}, uargs(c_10) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [0] p(activate) = [1] x1 + [14] p(cons) = [1] x2 + [2] p(from) = [1] x1 + [10] p(length) = [0] p(length1) = [0] p(n__cons) = [1] x2 + [1] p(n__from) = [1] x1 + [1] p(n__nil) = [1] p(nil) = [2] p(s) = [1] x1 + [5] p(activate#) = [4] x1 + [0] p(cons#) = [4] x2 + [0] p(from#) = [4] x1 + [0] p(length#) = [1] x1 + [0] p(length1#) = [1] x1 + [0] p(nil#) = [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) = [0] p(c_6) = [1] x1 + [0] p(c_7) = [0] p(c_8) = [1] x1 + [0] p(c_9) = [0] p(c_10) = [1] x1 + [0] p(c_11) = [2] Following rules are strictly oriented: activate#(n__cons(X1,X2)) = [4] X2 + [4] > [4] X2 + [0] = c_2(cons#(X1,X2)) activate#(n__from(X)) = [4] X + [4] > [4] X + [0] = c_3(from#(X)) activate#(n__nil()) = [4] > [0] = c_4(nil#()) length#(n__nil()) = [1] > [0] = c_9() activate(X) = [1] X + [14] > [1] X + [0] = X activate(n__cons(X1,X2)) = [1] X2 + [15] > [1] X2 + [2] = cons(X1,X2) activate(n__from(X)) = [1] X + [15] > [1] X + [10] = from(X) activate(n__nil()) = [15] > [2] = nil() cons(X1,X2) = [1] X2 + [2] > [1] X2 + [1] = n__cons(X1,X2) from(X) = [1] X + [10] > [1] X + [8] = cons(X,n__from(s(X))) from(X) = [1] X + [10] > [1] X + [1] = n__from(X) nil() = [2] > [1] = n__nil() Following rules are (at-least) weakly oriented: activate#(X) = [4] X + [0] >= [0] = c_1() cons#(X1,X2) = [4] X2 + [0] >= [0] = c_5() from#(X) = [4] X + [0] >= [4] X + [24] = c_6(cons#(X,n__from(s(X)))) from#(X) = [4] X + [0] >= [0] = c_7() length#(n__cons(X,Y)) = [1] Y + [1] >= [1] Y + [14] = c_8(length1#(activate(Y))) length1#(X) = [1] X + [0] >= [1] X + [14] = c_10(length#(activate(X))) nil#() = [0] >= [2] = c_11() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 4: PredecessorEstimation MAYBE + Considered Problem: - Strict DPs: activate#(X) -> c_1() cons#(X1,X2) -> c_5() from#(X) -> c_6(cons#(X,n__from(s(X)))) from#(X) -> c_7() length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) length1#(X) -> c_10(length#(activate(X))) nil#() -> c_11() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__from(X)) -> c_3(from#(X)) activate#(n__nil()) -> c_4(nil#()) length#(n__nil()) -> c_9() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__from(X)) -> from(X) activate(n__nil()) -> nil() cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) nil() -> n__nil() - Signature: {activate/1,cons/2,from/1,length/1,length1/1,nil/0,activate#/1,cons#/2,from#/1,length#/1,length1#/1 ,nil#/0} / {0/0,n__cons/2,n__from/1,n__nil/0,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/1,c_9/0 ,c_10/1,c_11/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,from#,length#,length1# ,nil#} and constructors {0,n__cons,n__from,n__nil,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_5() 3: from#(X) -> c_6(cons#(X,n__from(s(X)))) 4: from#(X) -> c_7() 5: length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) 6: length1#(X) -> c_10(length#(activate(X))) 7: nil#() -> c_11() 8: activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) 9: activate#(n__from(X)) -> c_3(from#(X)) 10: activate#(n__nil()) -> c_4(nil#()) 11: length#(n__nil()) -> c_9() * Step 5: RemoveWeakSuffixes MAYBE + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_5() from#(X) -> c_6(cons#(X,n__from(s(X)))) from#(X) -> c_7() length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) length1#(X) -> c_10(length#(activate(X))) nil#() -> c_11() - Weak DPs: activate#(X) -> c_1() activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__from(X)) -> c_3(from#(X)) activate#(n__nil()) -> c_4(nil#()) length#(n__nil()) -> c_9() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__from(X)) -> from(X) activate(n__nil()) -> nil() cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) nil() -> n__nil() - Signature: {activate/1,cons/2,from/1,length/1,length1/1,nil/0,activate#/1,cons#/2,from#/1,length#/1,length1#/1 ,nil#/0} / {0/0,n__cons/2,n__from/1,n__nil/0,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/1,c_9/0 ,c_10/1,c_11/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,from#,length#,length1# ,nil#} and constructors {0,n__cons,n__from,n__nil,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:cons#(X1,X2) -> c_5() 2:S:from#(X) -> c_6(cons#(X,n__from(s(X)))) -->_1 cons#(X1,X2) -> c_5():1 3:S:from#(X) -> c_7() 4:S:length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) -->_1 length1#(X) -> c_10(length#(activate(X))):5 5:S:length1#(X) -> c_10(length#(activate(X))) -->_1 length#(n__nil()) -> c_9():11 -->_1 length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))):4 6:S:nil#() -> c_11() 7:W:activate#(X) -> c_1() 8:W:activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) -->_1 cons#(X1,X2) -> c_5():1 9:W:activate#(n__from(X)) -> c_3(from#(X)) -->_1 from#(X) -> c_7():3 -->_1 from#(X) -> c_6(cons#(X,n__from(s(X)))):2 10:W:activate#(n__nil()) -> c_4(nil#()) -->_1 nil#() -> c_11():6 11:W:length#(n__nil()) -> c_9() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 7: activate#(X) -> c_1() 11: length#(n__nil()) -> c_9() * Step 6: RemoveHeads MAYBE + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_5() from#(X) -> c_6(cons#(X,n__from(s(X)))) from#(X) -> c_7() length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) length1#(X) -> c_10(length#(activate(X))) nil#() -> c_11() - Weak DPs: activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) activate#(n__from(X)) -> c_3(from#(X)) activate#(n__nil()) -> c_4(nil#()) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__from(X)) -> from(X) activate(n__nil()) -> nil() cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) nil() -> n__nil() - Signature: {activate/1,cons/2,from/1,length/1,length1/1,nil/0,activate#/1,cons#/2,from#/1,length#/1,length1#/1 ,nil#/0} / {0/0,n__cons/2,n__from/1,n__nil/0,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/1,c_9/0 ,c_10/1,c_11/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,from#,length#,length1# ,nil#} and constructors {0,n__cons,n__from,n__nil,s} + Applied Processor: RemoveHeads + Details: Consider the dependency graph 1:S:cons#(X1,X2) -> c_5() 2:S:from#(X) -> c_6(cons#(X,n__from(s(X)))) -->_1 cons#(X1,X2) -> c_5():1 3:S:from#(X) -> c_7() 4:S:length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) -->_1 length1#(X) -> c_10(length#(activate(X))):5 5:S:length1#(X) -> c_10(length#(activate(X))) -->_1 length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))):4 6:S:nil#() -> c_11() 8:W:activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2)) -->_1 cons#(X1,X2) -> c_5():1 9:W:activate#(n__from(X)) -> c_3(from#(X)) -->_1 from#(X) -> c_7():3 -->_1 from#(X) -> c_6(cons#(X,n__from(s(X)))):2 10:W:activate#(n__nil()) -> c_4(nil#()) -->_1 nil#() -> c_11():6 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). [(8,activate#(n__cons(X1,X2)) -> c_2(cons#(X1,X2))) ,(9,activate#(n__from(X)) -> c_3(from#(X))) ,(10,activate#(n__nil()) -> c_4(nil#()))] * Step 7: RemoveHeads MAYBE + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_5() from#(X) -> c_6(cons#(X,n__from(s(X)))) from#(X) -> c_7() length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) length1#(X) -> c_10(length#(activate(X))) nil#() -> c_11() - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__from(X)) -> from(X) activate(n__nil()) -> nil() cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) nil() -> n__nil() - Signature: {activate/1,cons/2,from/1,length/1,length1/1,nil/0,activate#/1,cons#/2,from#/1,length#/1,length1#/1 ,nil#/0} / {0/0,n__cons/2,n__from/1,n__nil/0,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/1,c_9/0 ,c_10/1,c_11/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,from#,length#,length1# ,nil#} and constructors {0,n__cons,n__from,n__nil,s} + Applied Processor: RemoveHeads + Details: Consider the dependency graph 1:S:cons#(X1,X2) -> c_5() 2:S:from#(X) -> c_6(cons#(X,n__from(s(X)))) -->_1 cons#(X1,X2) -> c_5():1 3:S:from#(X) -> c_7() 4:S:length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) -->_1 length1#(X) -> c_10(length#(activate(X))):5 5:S:length1#(X) -> c_10(length#(activate(X))) -->_1 length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))):4 6:S:nil#() -> c_11() 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). [(2,from#(X) -> c_6(cons#(X,n__from(s(X))))),(3,from#(X) -> c_7()),(6,nil#() -> c_11())] * Step 8: RemoveHeads MAYBE + Considered Problem: - Strict DPs: cons#(X1,X2) -> c_5() length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) length1#(X) -> c_10(length#(activate(X))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__from(X)) -> from(X) activate(n__nil()) -> nil() cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) nil() -> n__nil() - Signature: {activate/1,cons/2,from/1,length/1,length1/1,nil/0,activate#/1,cons#/2,from#/1,length#/1,length1#/1 ,nil#/0} / {0/0,n__cons/2,n__from/1,n__nil/0,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/1,c_9/0 ,c_10/1,c_11/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,from#,length#,length1# ,nil#} and constructors {0,n__cons,n__from,n__nil,s} + Applied Processor: RemoveHeads + Details: Consider the dependency graph 1:S:cons#(X1,X2) -> c_5() 4:S:length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) -->_1 length1#(X) -> c_10(length#(activate(X))):5 5:S:length1#(X) -> c_10(length#(activate(X))) -->_1 length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))):4 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). [(1,cons#(X1,X2) -> c_5())] * Step 9: Failure MAYBE + Considered Problem: - Strict DPs: length#(n__cons(X,Y)) -> c_8(length1#(activate(Y))) length1#(X) -> c_10(length#(activate(X))) - Weak TRS: activate(X) -> X activate(n__cons(X1,X2)) -> cons(X1,X2) activate(n__from(X)) -> from(X) activate(n__nil()) -> nil() cons(X1,X2) -> n__cons(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) nil() -> n__nil() - Signature: {activate/1,cons/2,from/1,length/1,length1/1,nil/0,activate#/1,cons#/2,from#/1,length#/1,length1#/1 ,nil#/0} / {0/0,n__cons/2,n__from/1,n__nil/0,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/1,c_9/0 ,c_10/1,c_11/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,cons#,from#,length#,length1# ,nil#} and constructors {0,n__cons,n__from,n__nil,s} + Applied Processor: EmptyProcessor + Details: The problem is still open. MAYBE