WORST_CASE(?,O(n^2)) * Step 1: DependencyPairs WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: a__b() -> a() a__b() -> b() a__f(X1,X2,X3) -> f(X1,X2,X3) a__f(a(),X,X) -> a__f(X,a__b(),b()) mark(a()) -> a() mark(b()) -> a__b() mark(f(X1,X2,X3)) -> a__f(X1,mark(X2),X3) - Signature: {a__b/0,a__f/3,mark/1} / {a/0,b/0,f/3} - Obligation: innermost runtime complexity wrt. defined symbols {a__b,a__f,mark} and constructors {a,b,f} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs a__b#() -> c_1() a__b#() -> c_2() a__f#(X1,X2,X3) -> c_3() a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()) mark#(a()) -> c_5() mark#(b()) -> c_6(a__b#()) mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) Weak DPs and mark the set of starting terms. * Step 2: PredecessorEstimation WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: a__b#() -> c_1() a__b#() -> c_2() a__f#(X1,X2,X3) -> c_3() a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()) mark#(a()) -> c_5() mark#(b()) -> c_6(a__b#()) mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) - Weak TRS: a__b() -> a() a__b() -> b() a__f(X1,X2,X3) -> f(X1,X2,X3) a__f(a(),X,X) -> a__f(X,a__b(),b()) mark(a()) -> a() mark(b()) -> a__b() mark(f(X1,X2,X3)) -> a__f(X1,mark(X2),X3) - Signature: {a__b/0,a__f/3,mark/1,a__b#/0,a__f#/3,mark#/1} / {a/0,b/0,f/3,c_1/0,c_2/0,c_3/0,c_4/2,c_5/0,c_6/1,c_7/2} - Obligation: innermost runtime complexity wrt. defined symbols {a__b#,a__f#,mark#} and constructors {a,b,f} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,2,3,5} by application of Pre({1,2,3,5}) = {4,6,7}. Here rules are labelled as follows: 1: a__b#() -> c_1() 2: a__b#() -> c_2() 3: a__f#(X1,X2,X3) -> c_3() 4: a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()) 5: mark#(a()) -> c_5() 6: mark#(b()) -> c_6(a__b#()) 7: mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) * Step 3: PredecessorEstimation WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()) mark#(b()) -> c_6(a__b#()) mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) - Weak DPs: a__b#() -> c_1() a__b#() -> c_2() a__f#(X1,X2,X3) -> c_3() mark#(a()) -> c_5() - Weak TRS: a__b() -> a() a__b() -> b() a__f(X1,X2,X3) -> f(X1,X2,X3) a__f(a(),X,X) -> a__f(X,a__b(),b()) mark(a()) -> a() mark(b()) -> a__b() mark(f(X1,X2,X3)) -> a__f(X1,mark(X2),X3) - Signature: {a__b/0,a__f/3,mark/1,a__b#/0,a__f#/3,mark#/1} / {a/0,b/0,f/3,c_1/0,c_2/0,c_3/0,c_4/2,c_5/0,c_6/1,c_7/2} - Obligation: innermost runtime complexity wrt. defined symbols {a__b#,a__f#,mark#} and constructors {a,b,f} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {2} by application of Pre({2}) = {3}. Here rules are labelled as follows: 1: a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()) 2: mark#(b()) -> c_6(a__b#()) 3: mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) 4: a__b#() -> c_1() 5: a__b#() -> c_2() 6: a__f#(X1,X2,X3) -> c_3() 7: mark#(a()) -> c_5() * Step 4: RemoveWeakSuffixes WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()) mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) - Weak DPs: a__b#() -> c_1() a__b#() -> c_2() a__f#(X1,X2,X3) -> c_3() mark#(a()) -> c_5() mark#(b()) -> c_6(a__b#()) - Weak TRS: a__b() -> a() a__b() -> b() a__f(X1,X2,X3) -> f(X1,X2,X3) a__f(a(),X,X) -> a__f(X,a__b(),b()) mark(a()) -> a() mark(b()) -> a__b() mark(f(X1,X2,X3)) -> a__f(X1,mark(X2),X3) - Signature: {a__b/0,a__f/3,mark/1,a__b#/0,a__f#/3,mark#/1} / {a/0,b/0,f/3,c_1/0,c_2/0,c_3/0,c_4/2,c_5/0,c_6/1,c_7/2} - Obligation: innermost runtime complexity wrt. defined symbols {a__b#,a__f#,mark#} and constructors {a,b,f} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()) -->_1 a__f#(X1,X2,X3) -> c_3():5 -->_2 a__b#() -> c_2():4 -->_2 a__b#() -> c_1():3 -->_1 a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()):1 2:S:mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) -->_2 mark#(b()) -> c_6(a__b#()):7 -->_2 mark#(a()) -> c_5():6 -->_1 a__f#(X1,X2,X3) -> c_3():5 -->_2 mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)):2 -->_1 a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()):1 3:W:a__b#() -> c_1() 4:W:a__b#() -> c_2() 5:W:a__f#(X1,X2,X3) -> c_3() 6:W:mark#(a()) -> c_5() 7:W:mark#(b()) -> c_6(a__b#()) -->_1 a__b#() -> c_2():4 -->_1 a__b#() -> c_1():3 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 6: mark#(a()) -> c_5() 7: mark#(b()) -> c_6(a__b#()) 3: a__b#() -> c_1() 4: a__b#() -> c_2() 5: a__f#(X1,X2,X3) -> c_3() * Step 5: SimplifyRHS WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()) mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) - Weak TRS: a__b() -> a() a__b() -> b() a__f(X1,X2,X3) -> f(X1,X2,X3) a__f(a(),X,X) -> a__f(X,a__b(),b()) mark(a()) -> a() mark(b()) -> a__b() mark(f(X1,X2,X3)) -> a__f(X1,mark(X2),X3) - Signature: {a__b/0,a__f/3,mark/1,a__b#/0,a__f#/3,mark#/1} / {a/0,b/0,f/3,c_1/0,c_2/0,c_3/0,c_4/2,c_5/0,c_6/1,c_7/2} - Obligation: innermost runtime complexity wrt. defined symbols {a__b#,a__f#,mark#} and constructors {a,b,f} + Applied Processor: SimplifyRHS + Details: Consider the dependency graph 1:S:a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()) -->_1 a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()):1 2:S:mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) -->_2 mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)):2 -->_1 a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b()),a__b#()):1 Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified: a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b())) * Step 6: DecomposeDG WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b())) mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) - Weak TRS: a__b() -> a() a__b() -> b() a__f(X1,X2,X3) -> f(X1,X2,X3) a__f(a(),X,X) -> a__f(X,a__b(),b()) mark(a()) -> a() mark(b()) -> a__b() mark(f(X1,X2,X3)) -> a__f(X1,mark(X2),X3) - Signature: {a__b/0,a__f/3,mark/1,a__b#/0,a__f#/3,mark#/1} / {a/0,b/0,f/3,c_1/0,c_2/0,c_3/0,c_4/1,c_5/0,c_6/1,c_7/2} - Obligation: innermost runtime complexity wrt. defined symbols {a__b#,a__f#,mark#} and constructors {a,b,f} + Applied Processor: DecomposeDG {onSelection = all below first cut in WDG, onUpper = Nothing, onLower = Nothing} + Details: We decompose the input problem according to the dependency graph into the upper component mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) and a lower component a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b())) Further, following extension rules are added to the lower component. mark#(f(X1,X2,X3)) -> a__f#(X1,mark(X2),X3) mark#(f(X1,X2,X3)) -> mark#(X2) ** Step 6.a:1: SimplifyRHS WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) - Weak TRS: a__b() -> a() a__b() -> b() a__f(X1,X2,X3) -> f(X1,X2,X3) a__f(a(),X,X) -> a__f(X,a__b(),b()) mark(a()) -> a() mark(b()) -> a__b() mark(f(X1,X2,X3)) -> a__f(X1,mark(X2),X3) - Signature: {a__b/0,a__f/3,mark/1,a__b#/0,a__f#/3,mark#/1} / {a/0,b/0,f/3,c_1/0,c_2/0,c_3/0,c_4/1,c_5/0,c_6/1,c_7/2} - Obligation: innermost runtime complexity wrt. defined symbols {a__b#,a__f#,mark#} and constructors {a,b,f} + Applied Processor: SimplifyRHS + Details: Consider the dependency graph 1:S:mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)) -->_2 mark#(f(X1,X2,X3)) -> c_7(a__f#(X1,mark(X2),X3),mark#(X2)):1 Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified: mark#(f(X1,X2,X3)) -> c_7(mark#(X2)) ** Step 6.a:2: UsableRules WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: mark#(f(X1,X2,X3)) -> c_7(mark#(X2)) - Weak TRS: a__b() -> a() a__b() -> b() a__f(X1,X2,X3) -> f(X1,X2,X3) a__f(a(),X,X) -> a__f(X,a__b(),b()) mark(a()) -> a() mark(b()) -> a__b() mark(f(X1,X2,X3)) -> a__f(X1,mark(X2),X3) - Signature: {a__b/0,a__f/3,mark/1,a__b#/0,a__f#/3,mark#/1} / {a/0,b/0,f/3,c_1/0,c_2/0,c_3/0,c_4/1,c_5/0,c_6/1,c_7/1} - Obligation: innermost runtime complexity wrt. defined symbols {a__b#,a__f#,mark#} and constructors {a,b,f} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: mark#(f(X1,X2,X3)) -> c_7(mark#(X2)) ** Step 6.a:3: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: mark#(f(X1,X2,X3)) -> c_7(mark#(X2)) - Signature: {a__b/0,a__f/3,mark/1,a__b#/0,a__f#/3,mark#/1} / {a/0,b/0,f/3,c_1/0,c_2/0,c_3/0,c_4/1,c_5/0,c_6/1,c_7/1} - Obligation: innermost runtime complexity wrt. defined symbols {a__b#,a__f#,mark#} and constructors {a,b,f} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + 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(c_7) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(a) = [0] p(a__b) = [0] p(a__f) = [0] p(b) = [0] p(f) = [1] x1 + [1] x2 + [1] x3 + [3] p(mark) = [0] p(a__b#) = [0] p(a__f#) = [0] p(mark#) = [1] x1 + [0] p(c_1) = [0] p(c_2) = [0] p(c_3) = [0] p(c_4) = [0] p(c_5) = [0] p(c_6) = [0] p(c_7) = [1] x1 + [0] Following rules are strictly oriented: mark#(f(X1,X2,X3)) = [1] X1 + [1] X2 + [1] X3 + [3] > [1] X2 + [0] = c_7(mark#(X2)) Following rules are (at-least) weakly oriented: Further, it can be verified that all rules not oriented are covered by the weightgap condition. ** Step 6.a:4: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: mark#(f(X1,X2,X3)) -> c_7(mark#(X2)) - Signature: {a__b/0,a__f/3,mark/1,a__b#/0,a__f#/3,mark#/1} / {a/0,b/0,f/3,c_1/0,c_2/0,c_3/0,c_4/1,c_5/0,c_6/1,c_7/1} - Obligation: innermost runtime complexity wrt. defined symbols {a__b#,a__f#,mark#} and constructors {a,b,f} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). ** Step 6.b:1: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b())) - Weak DPs: mark#(f(X1,X2,X3)) -> a__f#(X1,mark(X2),X3) mark#(f(X1,X2,X3)) -> mark#(X2) - Weak TRS: a__b() -> a() a__b() -> b() a__f(X1,X2,X3) -> f(X1,X2,X3) a__f(a(),X,X) -> a__f(X,a__b(),b()) mark(a()) -> a() mark(b()) -> a__b() mark(f(X1,X2,X3)) -> a__f(X1,mark(X2),X3) - Signature: {a__b/0,a__f/3,mark/1,a__b#/0,a__f#/3,mark#/1} / {a/0,b/0,f/3,c_1/0,c_2/0,c_3/0,c_4/1,c_5/0,c_6/1,c_7/2} - Obligation: innermost runtime complexity wrt. defined symbols {a__b#,a__f#,mark#} and constructors {a,b,f} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + 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(a__f) = {2}, uargs(a__f#) = {2}, uargs(c_4) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(a) = [1] p(a__b) = [4] p(a__f) = [4] x1 + [1] x2 + [4] x3 + [2] p(b) = [0] p(f) = [1] x1 + [1] x2 + [1] x3 + [1] p(mark) = [12] x1 + [5] p(a__b#) = [0] p(a__f#) = [8] x1 + [1] x2 + [8] x3 + [0] p(mark#) = [12] x1 + [4] p(c_1) = [8] p(c_2) = [0] p(c_3) = [1] p(c_4) = [1] x1 + [3] p(c_5) = [0] p(c_6) = [1] x1 + [1] p(c_7) = [0] Following rules are strictly oriented: a__f#(a(),X,X) = [9] X + [8] > [8] X + [7] = c_4(a__f#(X,a__b(),b())) Following rules are (at-least) weakly oriented: mark#(f(X1,X2,X3)) = [12] X1 + [12] X2 + [12] X3 + [16] >= [8] X1 + [12] X2 + [8] X3 + [5] = a__f#(X1,mark(X2),X3) mark#(f(X1,X2,X3)) = [12] X1 + [12] X2 + [12] X3 + [16] >= [12] X2 + [4] = mark#(X2) a__b() = [4] >= [1] = a() a__b() = [4] >= [0] = b() a__f(X1,X2,X3) = [4] X1 + [1] X2 + [4] X3 + [2] >= [1] X1 + [1] X2 + [1] X3 + [1] = f(X1,X2,X3) a__f(a(),X,X) = [5] X + [6] >= [4] X + [6] = a__f(X,a__b(),b()) mark(a()) = [17] >= [1] = a() mark(b()) = [5] >= [4] = a__b() mark(f(X1,X2,X3)) = [12] X1 + [12] X2 + [12] X3 + [17] >= [4] X1 + [12] X2 + [4] X3 + [7] = a__f(X1,mark(X2),X3) Further, it can be verified that all rules not oriented are covered by the weightgap condition. ** Step 6.b:2: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: a__f#(a(),X,X) -> c_4(a__f#(X,a__b(),b())) mark#(f(X1,X2,X3)) -> a__f#(X1,mark(X2),X3) mark#(f(X1,X2,X3)) -> mark#(X2) - Weak TRS: a__b() -> a() a__b() -> b() a__f(X1,X2,X3) -> f(X1,X2,X3) a__f(a(),X,X) -> a__f(X,a__b(),b()) mark(a()) -> a() mark(b()) -> a__b() mark(f(X1,X2,X3)) -> a__f(X1,mark(X2),X3) - Signature: {a__b/0,a__f/3,mark/1,a__b#/0,a__f#/3,mark#/1} / {a/0,b/0,f/3,c_1/0,c_2/0,c_3/0,c_4/1,c_5/0,c_6/1,c_7/2} - Obligation: innermost runtime complexity wrt. defined symbols {a__b#,a__f#,mark#} and constructors {a,b,f} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^2))