WORST_CASE(?,O(n^1)) * Step 1: Sum WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__first(X1,X2)) -> first(X1,X2) activate(n__from(X)) -> from(X) first(X1,X2) -> n__first(X1,X2) first(0(),Z) -> nil() first(s(X),cons(Y,Z)) -> cons(Y,n__first(X,activate(Z))) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) sel(0(),cons(X,Z)) -> X sel(s(X),cons(Y,Z)) -> sel(X,activate(Z)) - Signature: {activate/1,first/2,from/1,sel/2} / {0/0,cons/2,n__first/2,n__from/1,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,first,from,sel} and constructors {0,cons ,n__first,n__from,nil,s} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: NaturalPI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__first(X1,X2)) -> first(X1,X2) activate(n__from(X)) -> from(X) first(X1,X2) -> n__first(X1,X2) first(0(),Z) -> nil() first(s(X),cons(Y,Z)) -> cons(Y,n__first(X,activate(Z))) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) sel(0(),cons(X,Z)) -> X sel(s(X),cons(Y,Z)) -> sel(X,activate(Z)) - Signature: {activate/1,first/2,from/1,sel/2} / {0/0,cons/2,n__first/2,n__from/1,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,first,from,sel} and constructors {0,cons ,n__first,n__from,nil,s} + Applied Processor: NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a polynomial interpretation of kind constructor-based(linear): The following argument positions are considered usable: uargs(cons) = {2}, uargs(n__first) = {2}, uargs(sel) = {2} Following symbols are considered usable: {activate,first,from,sel} TcT has computed the following interpretation: p(0) = 1 p(activate) = x1 p(cons) = x1 + x2 p(first) = 8 + x2 p(from) = 4 + x1 p(n__first) = 8 + x2 p(n__from) = 4 + x1 p(nil) = 6 p(s) = 0 p(sel) = 1 + x2 Following rules are strictly oriented: first(0(),Z) = 8 + Z > 6 = nil() sel(0(),cons(X,Z)) = 1 + X + Z > X = X Following rules are (at-least) weakly oriented: activate(X) = X >= X = X activate(n__first(X1,X2)) = 8 + X2 >= 8 + X2 = first(X1,X2) activate(n__from(X)) = 4 + X >= 4 + X = from(X) first(X1,X2) = 8 + X2 >= 8 + X2 = n__first(X1,X2) first(s(X),cons(Y,Z)) = 8 + Y + Z >= 8 + Y + Z = cons(Y,n__first(X,activate(Z))) from(X) = 4 + X >= 4 + X = cons(X,n__from(s(X))) from(X) = 4 + X >= 4 + X = n__from(X) sel(s(X),cons(Y,Z)) = 1 + Y + Z >= 1 + Z = sel(X,activate(Z)) * Step 3: NaturalPI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__first(X1,X2)) -> first(X1,X2) activate(n__from(X)) -> from(X) first(X1,X2) -> n__first(X1,X2) first(s(X),cons(Y,Z)) -> cons(Y,n__first(X,activate(Z))) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) sel(s(X),cons(Y,Z)) -> sel(X,activate(Z)) - Weak TRS: first(0(),Z) -> nil() sel(0(),cons(X,Z)) -> X - Signature: {activate/1,first/2,from/1,sel/2} / {0/0,cons/2,n__first/2,n__from/1,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,first,from,sel} and constructors {0,cons ,n__first,n__from,nil,s} + Applied Processor: NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a polynomial interpretation of kind constructor-based(linear): The following argument positions are considered usable: uargs(cons) = {2}, uargs(n__first) = {2}, uargs(sel) = {2} Following symbols are considered usable: {activate,first,from,sel} TcT has computed the following interpretation: p(0) = 8 p(activate) = 1 + x1 p(cons) = 1 + x1 + x2 p(first) = 2 + x2 p(from) = 1 + x1 p(n__first) = 1 + x2 p(n__from) = x1 p(nil) = 1 p(s) = 0 p(sel) = 2*x2 Following rules are strictly oriented: activate(X) = 1 + X > X = X first(X1,X2) = 2 + X2 > 1 + X2 = n__first(X1,X2) from(X) = 1 + X > X = n__from(X) Following rules are (at-least) weakly oriented: activate(n__first(X1,X2)) = 2 + X2 >= 2 + X2 = first(X1,X2) activate(n__from(X)) = 1 + X >= 1 + X = from(X) first(0(),Z) = 2 + Z >= 1 = nil() first(s(X),cons(Y,Z)) = 3 + Y + Z >= 3 + Y + Z = cons(Y,n__first(X,activate(Z))) from(X) = 1 + X >= 1 + X = cons(X,n__from(s(X))) sel(0(),cons(X,Z)) = 2 + 2*X + 2*Z >= X = X sel(s(X),cons(Y,Z)) = 2 + 2*Y + 2*Z >= 2 + 2*Z = sel(X,activate(Z)) * Step 4: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(n__first(X1,X2)) -> first(X1,X2) activate(n__from(X)) -> from(X) first(s(X),cons(Y,Z)) -> cons(Y,n__first(X,activate(Z))) from(X) -> cons(X,n__from(s(X))) sel(s(X),cons(Y,Z)) -> sel(X,activate(Z)) - Weak TRS: activate(X) -> X first(X1,X2) -> n__first(X1,X2) first(0(),Z) -> nil() from(X) -> n__from(X) sel(0(),cons(X,Z)) -> X - Signature: {activate/1,first/2,from/1,sel/2} / {0/0,cons/2,n__first/2,n__from/1,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,first,from,sel} and constructors {0,cons ,n__first,n__from,nil,s} + Applied Processor: Ara {araHeuristics = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 5, araRuleShifting = Nothing} + Details: Signatures used: ---------------- 0 :: [] -(0)-> "A"(8) 0 :: [] -(0)-> "A"(10) activate :: ["A"(8)] -(5)-> "A"(8) cons :: ["A"(0) x "A"(8)] -(0)-> "A"(8) first :: ["A"(8) x "A"(8)] -(3)-> "A"(8) from :: ["A"(0)] -(4)-> "A"(8) n__first :: ["A"(8) x "A"(8)] -(0)-> "A"(8) n__from :: ["A"(0)] -(0)-> "A"(8) n__from :: ["A"(0)] -(0)-> "A"(14) nil :: [] -(0)-> "A"(14) s :: ["A"(8)] -(8)-> "A"(8) s :: ["A"(10)] -(10)-> "A"(10) s :: ["A"(0)] -(0)-> "A"(0) sel :: ["A"(10) x "A"(8)] -(12)-> "A"(0) Cost-free Signatures used: -------------------------- Base Constructor Signatures used: --------------------------------- "0_A" :: [] -(0)-> "A"(1) "cons_A" :: ["A"(0) x "A"(1)] -(0)-> "A"(1) "n__first_A" :: ["A"(0) x "A"(0)] -(0)-> "A"(1) "n__from_A" :: ["A"(0)] -(0)-> "A"(1) "nil_A" :: [] -(0)-> "A"(1) "s_A" :: ["A"(1)] -(1)-> "A"(1) WORST_CASE(?,O(n^1))