YES(?,O(n^1)) We are left with following problem, upon which TcT provides the certificate YES(?,O(n^1)). Strict Trs: { 2nd(cons1(X, cons(Y, Z))) -> Y , 2nd(cons(X, X1)) -> 2nd(cons1(X, activate(X1))) , activate(X) -> X , activate(n__from(X)) -> from(activate(X)) , activate(n__s(X)) -> s(activate(X)) , from(X) -> cons(X, n__from(n__s(X))) , from(X) -> n__from(X) , s(X) -> n__s(X) } Obligation: innermost runtime complexity Answer: YES(?,O(n^1)) We add following dependency tuples: Strict DPs: { 2nd^#(cons1(X, cons(Y, Z))) -> c_1() , 2nd^#(cons(X, X1)) -> c_2(2nd^#(cons1(X, activate(X1))), activate^#(X1)) , activate^#(X) -> c_3() , activate^#(n__from(X)) -> c_4(from^#(activate(X)), activate^#(X)) , activate^#(n__s(X)) -> c_5(s^#(activate(X)), activate^#(X)) , from^#(X) -> c_6() , from^#(X) -> c_7() , s^#(X) -> c_8() } and mark the set of starting terms. We are left with following problem, upon which TcT provides the certificate YES(?,O(n^1)). Strict DPs: { 2nd^#(cons1(X, cons(Y, Z))) -> c_1() , 2nd^#(cons(X, X1)) -> c_2(2nd^#(cons1(X, activate(X1))), activate^#(X1)) , activate^#(X) -> c_3() , activate^#(n__from(X)) -> c_4(from^#(activate(X)), activate^#(X)) , activate^#(n__s(X)) -> c_5(s^#(activate(X)), activate^#(X)) , from^#(X) -> c_6() , from^#(X) -> c_7() , s^#(X) -> c_8() } Weak Trs: { 2nd(cons1(X, cons(Y, Z))) -> Y , 2nd(cons(X, X1)) -> 2nd(cons1(X, activate(X1))) , activate(X) -> X , activate(n__from(X)) -> from(activate(X)) , activate(n__s(X)) -> s(activate(X)) , from(X) -> cons(X, n__from(n__s(X))) , from(X) -> n__from(X) , s(X) -> n__s(X) } Obligation: innermost runtime complexity Answer: YES(?,O(n^1)) We estimate the number of application of {1,3,6,7,8} by applications of Pre({1,3,6,7,8}) = {2,4,5}. Here rules are labeled as follows: DPs: { 1: 2nd^#(cons1(X, cons(Y, Z))) -> c_1() , 2: 2nd^#(cons(X, X1)) -> c_2(2nd^#(cons1(X, activate(X1))), activate^#(X1)) , 3: activate^#(X) -> c_3() , 4: activate^#(n__from(X)) -> c_4(from^#(activate(X)), activate^#(X)) , 5: activate^#(n__s(X)) -> c_5(s^#(activate(X)), activate^#(X)) , 6: from^#(X) -> c_6() , 7: from^#(X) -> c_7() , 8: s^#(X) -> c_8() } We are left with following problem, upon which TcT provides the certificate YES(?,O(n^1)). Strict DPs: { 2nd^#(cons(X, X1)) -> c_2(2nd^#(cons1(X, activate(X1))), activate^#(X1)) , activate^#(n__from(X)) -> c_4(from^#(activate(X)), activate^#(X)) , activate^#(n__s(X)) -> c_5(s^#(activate(X)), activate^#(X)) } Weak DPs: { 2nd^#(cons1(X, cons(Y, Z))) -> c_1() , activate^#(X) -> c_3() , from^#(X) -> c_6() , from^#(X) -> c_7() , s^#(X) -> c_8() } Weak Trs: { 2nd(cons1(X, cons(Y, Z))) -> Y , 2nd(cons(X, X1)) -> 2nd(cons1(X, activate(X1))) , activate(X) -> X , activate(n__from(X)) -> from(activate(X)) , activate(n__s(X)) -> s(activate(X)) , from(X) -> cons(X, n__from(n__s(X))) , from(X) -> n__from(X) , s(X) -> n__s(X) } Obligation: innermost runtime complexity Answer: YES(?,O(n^1)) The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. { 2nd^#(cons1(X, cons(Y, Z))) -> c_1() , activate^#(X) -> c_3() , from^#(X) -> c_6() , from^#(X) -> c_7() , s^#(X) -> c_8() } We are left with following problem, upon which TcT provides the certificate YES(?,O(n^1)). Strict DPs: { 2nd^#(cons(X, X1)) -> c_2(2nd^#(cons1(X, activate(X1))), activate^#(X1)) , activate^#(n__from(X)) -> c_4(from^#(activate(X)), activate^#(X)) , activate^#(n__s(X)) -> c_5(s^#(activate(X)), activate^#(X)) } Weak Trs: { 2nd(cons1(X, cons(Y, Z))) -> Y , 2nd(cons(X, X1)) -> 2nd(cons1(X, activate(X1))) , activate(X) -> X , activate(n__from(X)) -> from(activate(X)) , activate(n__s(X)) -> s(activate(X)) , from(X) -> cons(X, n__from(n__s(X))) , from(X) -> n__from(X) , s(X) -> n__s(X) } Obligation: innermost runtime complexity Answer: YES(?,O(n^1)) Due to missing edges in the dependency-graph, the right-hand sides of following rules could be simplified: { 2nd^#(cons(X, X1)) -> c_2(2nd^#(cons1(X, activate(X1))), activate^#(X1)) , activate^#(n__from(X)) -> c_4(from^#(activate(X)), activate^#(X)) , activate^#(n__s(X)) -> c_5(s^#(activate(X)), activate^#(X)) } We are left with following problem, upon which TcT provides the certificate YES(?,O(n^1)). Strict DPs: { 2nd^#(cons(X, X1)) -> c_1(activate^#(X1)) , activate^#(n__from(X)) -> c_2(activate^#(X)) , activate^#(n__s(X)) -> c_3(activate^#(X)) } Weak Trs: { 2nd(cons1(X, cons(Y, Z))) -> Y , 2nd(cons(X, X1)) -> 2nd(cons1(X, activate(X1))) , activate(X) -> X , activate(n__from(X)) -> from(activate(X)) , activate(n__s(X)) -> s(activate(X)) , from(X) -> cons(X, n__from(n__s(X))) , from(X) -> n__from(X) , s(X) -> n__s(X) } Obligation: innermost runtime complexity Answer: YES(?,O(n^1)) No rule is usable, rules are removed from the input problem. We are left with following problem, upon which TcT provides the certificate YES(?,O(n^1)). Strict DPs: { 2nd^#(cons(X, X1)) -> c_1(activate^#(X1)) , activate^#(n__from(X)) -> c_2(activate^#(X)) , activate^#(n__s(X)) -> c_3(activate^#(X)) } Obligation: innermost runtime complexity Answer: YES(?,O(n^1)) Consider the dependency graph 1: 2nd^#(cons(X, X1)) -> c_1(activate^#(X1)) -->_1 activate^#(n__s(X)) -> c_3(activate^#(X)) :3 -->_1 activate^#(n__from(X)) -> c_2(activate^#(X)) :2 2: activate^#(n__from(X)) -> c_2(activate^#(X)) -->_1 activate^#(n__s(X)) -> c_3(activate^#(X)) :3 -->_1 activate^#(n__from(X)) -> c_2(activate^#(X)) :2 3: activate^#(n__s(X)) -> c_3(activate^#(X)) -->_1 activate^#(n__s(X)) -> c_3(activate^#(X)) :3 -->_1 activate^#(n__from(X)) -> c_2(activate^#(X)) :2 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). { 2nd^#(cons(X, X1)) -> c_1(activate^#(X1)) } We are left with following problem, upon which TcT provides the certificate YES(?,O(n^1)). Strict DPs: { activate^#(n__from(X)) -> c_2(activate^#(X)) , activate^#(n__s(X)) -> c_3(activate^#(X)) } Obligation: innermost runtime complexity Answer: YES(?,O(n^1)) The input was oriented with the instance of 'Small Polynomial Path Order (PS)' as induced by the safe mapping safe(n__from) = {1}, safe(n__s) = {1}, safe(activate^#) = {}, safe(c_2) = {}, safe(c_3) = {} and precedence empty . Following symbols are considered recursive: {activate^#} The recursion depth is 1. Further, following argument filtering is employed: pi(n__from) = [1], pi(n__s) = [1], pi(activate^#) = [1], pi(c_2) = [1], pi(c_3) = [1] Usable defined function symbols are a subset of: {activate^#} For your convenience, here are the satisfied ordering constraints: pi(activate^#(n__from(X))) = activate^#(n__from(; X);) > c_2(activate^#(X;);) = pi(c_2(activate^#(X))) pi(activate^#(n__s(X))) = activate^#(n__s(; X);) > c_3(activate^#(X;);) = pi(c_3(activate^#(X))) Hurray, we answered YES(?,O(n^1))