MAYBE * Step 1: DependencyPairs MAYBE + Considered Problem: - Strict TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib(N) -> sel(N,fib1(s(0()),s(0()))) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) sel(0(),cons(X,XS)) -> X sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2} / {0/0,cons/2,n__add/2,n__fib1/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,add,fib,fib1,sel} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs activate#(X) -> c_1() activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) add#(X1,X2) -> c_4() add#(0(),X) -> c_5() add#(s(X),Y) -> c_6(add#(X,Y)) fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0()))),fib1#(s(0()),s(0()))) fib1#(X,Y) -> c_8() fib1#(X1,X2) -> c_9() sel#(0(),cons(X,XS)) -> c_10() sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) Weak DPs and mark the set of starting terms. * Step 2: UsableRules MAYBE + Considered Problem: - Strict DPs: activate#(X) -> c_1() activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) add#(X1,X2) -> c_4() add#(0(),X) -> c_5() add#(s(X),Y) -> c_6(add#(X,Y)) fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0()))),fib1#(s(0()),s(0()))) fib1#(X,Y) -> c_8() fib1#(X1,X2) -> c_9() sel#(0(),cons(X,XS)) -> c_10() sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib(N) -> sel(N,fib1(s(0()),s(0()))) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) sel(0(),cons(X,XS)) -> X sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/3,c_4/0,c_5/0,c_6/1,c_7/2,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) activate#(X) -> c_1() activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) add#(X1,X2) -> c_4() add#(0(),X) -> c_5() add#(s(X),Y) -> c_6(add#(X,Y)) fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0()))),fib1#(s(0()),s(0()))) fib1#(X,Y) -> c_8() fib1#(X1,X2) -> c_9() sel#(0(),cons(X,XS)) -> c_10() sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) * Step 3: PredecessorEstimation MAYBE + Considered Problem: - Strict DPs: activate#(X) -> c_1() activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) add#(X1,X2) -> c_4() add#(0(),X) -> c_5() add#(s(X),Y) -> c_6(add#(X,Y)) fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0()))),fib1#(s(0()),s(0()))) fib1#(X,Y) -> c_8() fib1#(X1,X2) -> c_9() sel#(0(),cons(X,XS)) -> c_10() sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/3,c_4/0,c_5/0,c_6/1,c_7/2,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,4,5,8,9,10} by application of Pre({1,4,5,8,9,10}) = {2,3,6,7,11}. Here rules are labelled as follows: 1: activate#(X) -> c_1() 2: activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) 3: activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) 4: add#(X1,X2) -> c_4() 5: add#(0(),X) -> c_5() 6: add#(s(X),Y) -> c_6(add#(X,Y)) 7: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0()))),fib1#(s(0()),s(0()))) 8: fib1#(X,Y) -> c_8() 9: fib1#(X1,X2) -> c_9() 10: sel#(0(),cons(X,XS)) -> c_10() 11: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) * Step 4: RemoveWeakSuffixes MAYBE + Considered Problem: - Strict DPs: activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) add#(s(X),Y) -> c_6(add#(X,Y)) fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0()))),fib1#(s(0()),s(0()))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak DPs: activate#(X) -> c_1() add#(X1,X2) -> c_4() add#(0(),X) -> c_5() fib1#(X,Y) -> c_8() fib1#(X1,X2) -> c_9() sel#(0(),cons(X,XS)) -> c_10() - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/3,c_4/0,c_5/0,c_6/1,c_7/2,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) -->_1 add#(s(X),Y) -> c_6(add#(X,Y)):3 -->_3 activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):2 -->_2 activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):2 -->_1 add#(0(),X) -> c_5():8 -->_1 add#(X1,X2) -> c_4():7 -->_3 activate#(X) -> c_1():6 -->_2 activate#(X) -> c_1():6 -->_3 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):1 -->_2 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):1 2:S:activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) -->_1 fib1#(X1,X2) -> c_9():10 -->_1 fib1#(X,Y) -> c_8():9 -->_3 activate#(X) -> c_1():6 -->_2 activate#(X) -> c_1():6 -->_3 activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):2 -->_2 activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):2 -->_3 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):1 -->_2 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):1 3:S:add#(s(X),Y) -> c_6(add#(X,Y)) -->_1 add#(0(),X) -> c_5():8 -->_1 add#(X1,X2) -> c_4():7 -->_1 add#(s(X),Y) -> c_6(add#(X,Y)):3 4:S:fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0()))),fib1#(s(0()),s(0()))) -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)):5 -->_1 sel#(0(),cons(X,XS)) -> c_10():11 -->_2 fib1#(X1,X2) -> c_9():10 -->_2 fib1#(X,Y) -> c_8():9 5:S:sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) -->_1 sel#(0(),cons(X,XS)) -> c_10():11 -->_2 activate#(X) -> c_1():6 -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)):5 -->_2 activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):2 -->_2 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):1 6:W:activate#(X) -> c_1() 7:W:add#(X1,X2) -> c_4() 8:W:add#(0(),X) -> c_5() 9:W:fib1#(X,Y) -> c_8() 10:W:fib1#(X1,X2) -> c_9() 11:W:sel#(0(),cons(X,XS)) -> c_10() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 11: sel#(0(),cons(X,XS)) -> c_10() 6: activate#(X) -> c_1() 9: fib1#(X,Y) -> c_8() 10: fib1#(X1,X2) -> c_9() 7: add#(X1,X2) -> c_4() 8: add#(0(),X) -> c_5() * Step 5: SimplifyRHS MAYBE + Considered Problem: - Strict DPs: activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) add#(s(X),Y) -> c_6(add#(X,Y)) fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0()))),fib1#(s(0()),s(0()))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/3,c_4/0,c_5/0,c_6/1,c_7/2,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: SimplifyRHS + Details: Consider the dependency graph 1:S:activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) -->_1 add#(s(X),Y) -> c_6(add#(X,Y)):3 -->_3 activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):2 -->_2 activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):2 -->_3 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):1 -->_2 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):1 2:S:activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) -->_3 activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):2 -->_2 activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):2 -->_3 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):1 -->_2 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):1 3:S:add#(s(X),Y) -> c_6(add#(X,Y)) -->_1 add#(s(X),Y) -> c_6(add#(X,Y)):3 4:S:fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0()))),fib1#(s(0()),s(0()))) -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)):5 5:S:sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)):5 -->_2 activate#(n__fib1(X1,X2)) -> c_3(fib1#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):2 -->_2 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):1 Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified: activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)) fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) * Step 6: Decompose MAYBE + Considered Problem: - Strict DPs: activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)) add#(s(X),Y) -> c_6(add#(X,Y)) fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,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: activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)) add#(s(X),Y) -> c_6(add#(X,Y)) - Weak DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0 ,cons,n__add,n__fib1,s} Problem (S) - Strict DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak DPs: activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)) add#(s(X),Y) -> c_6(add#(X,Y)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0 ,cons,n__add,n__fib1,s} ** Step 6.a:1: DecomposeDG MAYBE + Considered Problem: - Strict DPs: activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)) add#(s(X),Y) -> c_6(add#(X,Y)) - Weak DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: DecomposeDG {onSelection = all below first cut in WDG, onUpper = Just someStrategy, onLower = Nothing} + Details: We decompose the input problem according to the dependency graph into the upper component fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) and a lower component activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)) add#(s(X),Y) -> c_6(add#(X,Y)) Further, following extension rules are added to the lower component. fib#(N) -> sel#(N,fib1(s(0()),s(0()))) sel#(s(N),cons(X,XS)) -> activate#(XS) sel#(s(N),cons(X,XS)) -> sel#(N,activate(XS)) *** Step 6.a:1.a:1: PredecessorEstimationCP WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: PredecessorEstimationCP {onSelectionCP = any intersect of rules of CDG leaf and strict-rules, withComplexityPair = NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Nothing}} + Details: We first use the processor NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Nothing} to orient following rules strictly: 1: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) Consider the set of all dependency pairs 1: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) 2: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) Processor NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Nothing}induces the complexity certificateTIME (?,O(n^1)) SPACE(?,?)on application of the dependency pairs {1} These cover all (indirect) predecessors of dependency pairs {1,2} their number of applications is equally bounded. The dependency pairs are shifted into the weak component. **** Step 6.a:1.a:1.a:1: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just first alternative for predecessorEstimation on any intersect of rules of CDG leaf and strict-rules} + Details: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(c_7) = {1}, uargs(c_11) = {1} Following symbols are considered usable: {activate#,add#,fib#,fib1#,sel#} TcT has computed the following interpretation: p(0) = [1] p(activate) = [0] p(add) = [8] x1 + [4] p(cons) = [8] p(fib) = [1] x1 + [0] p(fib1) = [3] x1 + [4] x2 + [3] p(n__add) = [1] x2 + [4] p(n__fib1) = [0] p(s) = [1] x1 + [2] p(sel) = [2] x1 + [1] x2 + [0] p(activate#) = [1] p(add#) = [1] x1 + [2] x2 + [0] p(fib#) = [8] x1 + [5] p(fib1#) = [2] x1 + [2] p(sel#) = [8] x1 + [4] p(c_1) = [1] p(c_2) = [1] x2 + [2] p(c_3) = [1] x1 + [4] p(c_4) = [0] p(c_5) = [0] p(c_6) = [1] p(c_7) = [1] x1 + [1] p(c_8) = [8] p(c_9) = [2] p(c_10) = [0] p(c_11) = [1] x1 + [2] x2 + [11] Following rules are strictly oriented: sel#(s(N),cons(X,XS)) = [8] N + [20] > [8] N + [17] = c_11(sel#(N,activate(XS)),activate#(XS)) Following rules are (at-least) weakly oriented: fib#(N) = [8] N + [5] >= [8] N + [5] = c_7(sel#(N,fib1(s(0()),s(0())))) **** Step 6.a:1.a:1.a:2: Assumption WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: Assumption {assumed = Certificate {spaceUB = Unknown, spaceLB = Unknown, timeUB = Poly (Just 0), timeLB = Unknown}} + Details: () **** Step 6.a:1.a:1.b:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:W:fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)):2 2:W:sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)):2 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 1: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) 2: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) **** Step 6.a:1.a:1.b:2: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). *** Step 6.a:1.b:1: Failure MAYBE + Considered Problem: - Strict DPs: activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)) add#(s(X),Y) -> c_6(add#(X,Y)) - Weak DPs: fib#(N) -> sel#(N,fib1(s(0()),s(0()))) sel#(s(N),cons(X,XS)) -> activate#(XS) sel#(s(N),cons(X,XS)) -> sel#(N,activate(XS)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: EmptyProcessor + Details: The problem is still open. ** Step 6.b:1: RemoveWeakSuffixes WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak DPs: activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)) add#(s(X),Y) -> c_6(add#(X,Y)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)):2 2:S:sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) -->_2 activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)):4 -->_2 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):3 -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)):2 3:W:activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) -->_1 add#(s(X),Y) -> c_6(add#(X,Y)):5 -->_3 activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)):4 -->_2 activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)):4 -->_3 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):3 -->_2 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):3 4:W:activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)) -->_2 activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)):4 -->_1 activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)):4 -->_2 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):3 -->_1 activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)):3 5:W:add#(s(X),Y) -> c_6(add#(X,Y)) -->_1 add#(s(X),Y) -> c_6(add#(X,Y)):5 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 4: activate#(n__fib1(X1,X2)) -> c_3(activate#(X1),activate#(X2)) 3: activate#(n__add(X1,X2)) -> c_2(add#(activate(X1),activate(X2)),activate#(X1),activate#(X2)) 5: add#(s(X),Y) -> c_6(add#(X,Y)) ** Step 6.b:2: SimplifyRHS WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/2} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: SimplifyRHS + Details: Consider the dependency graph 1:S:fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)):2 2:S:sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)):2 Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS))) ** Step 6.b:3: PredecessorEstimationCP WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS))) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: PredecessorEstimationCP {onSelectionCP = any intersect of rules of CDG leaf and strict-rules, withComplexityPair = NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Nothing}} + Details: We first use the processor NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Nothing} to orient following rules strictly: 2: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS))) Consider the set of all dependency pairs 1: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) 2: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS))) Processor NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Nothing}induces the complexity certificateTIME (?,O(n^1)) SPACE(?,?)on application of the dependency pairs {2} These cover all (indirect) predecessors of dependency pairs {1,2} their number of applications is equally bounded. The dependency pairs are shifted into the weak component. *** Step 6.b:3.a:1: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS))) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just first alternative for predecessorEstimation on any intersect of rules of CDG leaf and strict-rules} + Details: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(c_7) = {1}, uargs(c_11) = {1} Following symbols are considered usable: {activate#,add#,fib#,fib1#,sel#} TcT has computed the following interpretation: p(0) = [0] p(activate) = [3] p(add) = [1] p(cons) = [1] x2 + [0] p(fib) = [1] x1 + [1] p(fib1) = [1] x1 + [6] x2 + [2] p(n__add) = [2] p(n__fib1) = [15] p(s) = [1] x1 + [1] p(sel) = [8] x2 + [0] p(activate#) = [1] p(add#) = [2] x1 + [1] x2 + [2] p(fib#) = [4] x1 + [8] p(fib1#) = [1] p(sel#) = [2] x1 + [4] p(c_1) = [2] p(c_2) = [1] x1 + [1] x3 + [8] p(c_3) = [1] x1 + [2] x2 + [0] p(c_4) = [4] p(c_5) = [1] p(c_6) = [1] p(c_7) = [2] x1 + [0] p(c_8) = [1] p(c_9) = [0] p(c_10) = [2] p(c_11) = [1] x1 + [0] Following rules are strictly oriented: sel#(s(N),cons(X,XS)) = [2] N + [6] > [2] N + [4] = c_11(sel#(N,activate(XS))) Following rules are (at-least) weakly oriented: fib#(N) = [4] N + [8] >= [4] N + [8] = c_7(sel#(N,fib1(s(0()),s(0())))) *** Step 6.b:3.a:2: Assumption WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) - Weak DPs: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS))) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: Assumption {assumed = Certificate {spaceUB = Unknown, spaceLB = Unknown, timeUB = Poly (Just 0), timeLB = Unknown}} + Details: () *** Step 6.b:3.b:1: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS))) - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:W:fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS))):2 2:W:sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS))) -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS))):2 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 1: fib#(N) -> c_7(sel#(N,fib1(s(0()),s(0())))) 2: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS))) *** Step 6.b:3.b:2: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__add(X1,X2)) -> add(activate(X1),activate(X2)) activate(n__fib1(X1,X2)) -> fib1(activate(X1),activate(X2)) add(X1,X2) -> n__add(X1,X2) add(0(),X) -> X add(s(X),Y) -> s(add(X,Y)) fib1(X,Y) -> cons(X,n__fib1(Y,n__add(X,Y))) fib1(X1,X2) -> n__fib1(X1,X2) - Signature: {activate/1,add/2,fib/1,fib1/2,sel/2,activate#/1,add#/2,fib#/1,fib1#/2,sel#/2} / {0/0,cons/2,n__add/2 ,n__fib1/2,s/1,c_1/0,c_2/3,c_3/2,c_4/0,c_5/0,c_6/1,c_7/1,c_8/0,c_9/0,c_10/0,c_11/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,add#,fib#,fib1#,sel#} and constructors {0,cons ,n__add,n__fib1,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). MAYBE