* Step 1: DependencyPairs WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f(0(),y) -> 0() f(s(x),y) -> f(f(x,y),y) - Signature: {f/2} / {0/0,s/1} - Obligation: runtime complexity wrt. defined symbols {f} and constructors {0,s} + Applied Processor: DependencyPairs {dpKind_ = WIDP} + Details: We add the following weak dependency pairs: Strict DPs f#(0(),y) -> c_1() f#(s(x),y) -> c_2(f#(f(x,y),y)) Weak DPs and mark the set of starting terms. * Step 2: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: f#(0(),y) -> c_1() f#(s(x),y) -> c_2(f#(f(x,y),y)) - Strict TRS: f(0(),y) -> 0() f(s(x),y) -> f(f(x,y),y) - Signature: {f/2,f#/2} / {0/0,s/1,c_1/0,c_2/1} - Obligation: runtime complexity wrt. defined symbols {f#} and constructors {0,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(f) = {1}, uargs(f#) = {1}, uargs(c_2) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [2] p(f) = [1] x1 + [2] p(s) = [1] x1 + [3] p(f#) = [1] x1 + [0] p(c_1) = [0] p(c_2) = [1] x1 + [0] Following rules are strictly oriented: f#(0(),y) = [2] > [0] = c_1() f#(s(x),y) = [1] x + [3] > [1] x + [2] = c_2(f#(f(x,y),y)) f(0(),y) = [4] > [2] = 0() f(s(x),y) = [1] x + [5] > [1] x + [4] = f(f(x,y),y) Following rules are (at-least) weakly oriented: Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 3: RemoveWeakSuffixes WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: f#(0(),y) -> c_1() f#(s(x),y) -> c_2(f#(f(x,y),y)) - Weak TRS: f(0(),y) -> 0() f(s(x),y) -> f(f(x,y),y) - Signature: {f/2,f#/2} / {0/0,s/1,c_1/0,c_2/1} - Obligation: runtime complexity wrt. defined symbols {f#} and constructors {0,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:W:f#(0(),y) -> c_1() 2:W:f#(s(x),y) -> c_2(f#(f(x,y),y)) -->_1 f#(s(x),y) -> c_2(f#(f(x,y),y)):2 -->_1 f#(0(),y) -> c_1():1 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 2: f#(s(x),y) -> c_2(f#(f(x,y),y)) 1: f#(0(),y) -> c_1() * Step 4: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: f(0(),y) -> 0() f(s(x),y) -> f(f(x,y),y) - Signature: {f/2,f#/2} / {0/0,s/1,c_1/0,c_2/1} - Obligation: runtime complexity wrt. defined symbols {f#} and constructors {0,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))