* Step 1: Sum WORST_CASE(Omega(n^1),O(n^1)) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__f(X1,X2)) -> f(activate(X1),X2) activate(n__g(X)) -> g(activate(X)) f(X1,X2) -> n__f(X1,X2) f(g(X),Y) -> f(X,n__f(n__g(X),activate(Y))) g(X) -> n__g(X) - Signature: {activate/1,f/2,g/1} / {n__f/2,n__g/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,f,g} and constructors {n__f,n__g} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__f(X1,X2)) -> f(activate(X1),X2) activate(n__g(X)) -> g(activate(X)) f(X1,X2) -> n__f(X1,X2) f(g(X),Y) -> f(X,n__f(n__g(X),activate(Y))) g(X) -> n__g(X) - Signature: {activate/1,f/2,g/1} / {n__f/2,n__g/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,f,g} and constructors {n__f,n__g} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: activate(x){x -> n__f(x,y)} = activate(n__f(x,y)) ->^+ f(activate(x),y) = C[activate(x) = activate(x){}] ** Step 1.b:1: InnermostRuleRemoval WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__f(X1,X2)) -> f(activate(X1),X2) activate(n__g(X)) -> g(activate(X)) f(X1,X2) -> n__f(X1,X2) f(g(X),Y) -> f(X,n__f(n__g(X),activate(Y))) g(X) -> n__g(X) - Signature: {activate/1,f/2,g/1} / {n__f/2,n__g/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,f,g} and constructors {n__f,n__g} + Applied Processor: InnermostRuleRemoval + Details: Arguments of following rules are not normal-forms. f(g(X),Y) -> f(X,n__f(n__g(X),activate(Y))) All above mentioned rules can be savely removed. ** Step 1.b:2: Bounds WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__f(X1,X2)) -> f(activate(X1),X2) activate(n__g(X)) -> g(activate(X)) f(X1,X2) -> n__f(X1,X2) g(X) -> n__g(X) - Signature: {activate/1,f/2,g/1} / {n__f/2,n__g/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,f,g} and constructors {n__f,n__g} + Applied Processor: Bounds {initialAutomaton = minimal, enrichment = match} + Details: The problem is match-bounded by 2. The enriched problem is compatible with follwoing automaton. activate_0(2) -> 1 activate_1(2) -> 3 f_0(2,2) -> 1 f_1(3,2) -> 1 f_1(3,2) -> 3 g_0(2) -> 1 g_1(3) -> 1 g_1(3) -> 3 n__f_0(2,2) -> 1 n__f_0(2,2) -> 2 n__f_0(2,2) -> 3 n__f_1(2,2) -> 1 n__f_2(3,2) -> 1 n__f_2(3,2) -> 3 n__g_0(2) -> 1 n__g_0(2) -> 2 n__g_0(2) -> 3 n__g_1(2) -> 1 n__g_2(3) -> 1 n__g_2(3) -> 3 2 -> 1 2 -> 3 ** Step 1.b:3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__f(X1,X2)) -> f(activate(X1),X2) activate(n__g(X)) -> g(activate(X)) f(X1,X2) -> n__f(X1,X2) g(X) -> n__g(X) - Signature: {activate/1,f/2,g/1} / {n__f/2,n__g/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,f,g} and constructors {n__f,n__g} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(Omega(n^1),O(n^1))