MAYBE * Step 1: DependencyPairs MAYBE + Considered Problem: - Strict TRS: active(a()) -> mark(b()) active(f(X,X)) -> mark(h(a())) active(f(X1,X2)) -> f(active(X1),X2) active(g(X1,X2)) -> g(active(X1),X2) active(g(a(),X)) -> mark(f(b(),X)) active(h(X)) -> h(active(X)) active(h(X)) -> mark(g(X,X)) f(mark(X1),X2) -> mark(f(X1,X2)) f(ok(X1),ok(X2)) -> ok(f(X1,X2)) g(mark(X1),X2) -> mark(g(X1,X2)) g(ok(X1),ok(X2)) -> ok(g(X1,X2)) h(mark(X)) -> mark(h(X)) h(ok(X)) -> ok(h(X)) proper(a()) -> ok(a()) proper(b()) -> ok(b()) proper(f(X1,X2)) -> f(proper(X1),proper(X2)) proper(g(X1,X2)) -> g(proper(X1),proper(X2)) proper(h(X)) -> h(proper(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) - Signature: {active/1,f/2,g/2,h/1,proper/1,top/1} / {a/0,b/0,mark/1,ok/1} - Obligation: innermost runtime complexity wrt. defined symbols {active,f,g,h,proper,top} and constructors {a,b,mark,ok} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs active#(a()) -> c_1() active#(f(X,X)) -> c_2(h#(a())) active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)) active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)) active#(g(a(),X)) -> c_5(f#(b(),X)) active#(h(X)) -> c_6(h#(active(X)),active#(X)) active#(h(X)) -> c_7(g#(X,X)) f#(mark(X1),X2) -> c_8(f#(X1,X2)) f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)) g#(mark(X1),X2) -> c_10(g#(X1,X2)) g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)) h#(mark(X)) -> c_12(h#(X)) h#(ok(X)) -> c_13(h#(X)) proper#(a()) -> c_14() proper#(b()) -> c_15() proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)) top#(mark(X)) -> c_19(top#(proper(X)),proper#(X)) top#(ok(X)) -> c_20(top#(active(X)),active#(X)) Weak DPs and mark the set of starting terms. * Step 2: UsableRules MAYBE + Considered Problem: - Strict DPs: active#(a()) -> c_1() active#(f(X,X)) -> c_2(h#(a())) active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)) active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)) active#(g(a(),X)) -> c_5(f#(b(),X)) active#(h(X)) -> c_6(h#(active(X)),active#(X)) active#(h(X)) -> c_7(g#(X,X)) f#(mark(X1),X2) -> c_8(f#(X1,X2)) f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)) g#(mark(X1),X2) -> c_10(g#(X1,X2)) g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)) h#(mark(X)) -> c_12(h#(X)) h#(ok(X)) -> c_13(h#(X)) proper#(a()) -> c_14() proper#(b()) -> c_15() proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)) top#(mark(X)) -> c_19(top#(proper(X)),proper#(X)) top#(ok(X)) -> c_20(top#(active(X)),active#(X)) - Weak TRS: active(a()) -> mark(b()) active(f(X,X)) -> mark(h(a())) active(f(X1,X2)) -> f(active(X1),X2) active(g(X1,X2)) -> g(active(X1),X2) active(g(a(),X)) -> mark(f(b(),X)) active(h(X)) -> h(active(X)) active(h(X)) -> mark(g(X,X)) f(mark(X1),X2) -> mark(f(X1,X2)) f(ok(X1),ok(X2)) -> ok(f(X1,X2)) g(mark(X1),X2) -> mark(g(X1,X2)) g(ok(X1),ok(X2)) -> ok(g(X1,X2)) h(mark(X)) -> mark(h(X)) h(ok(X)) -> ok(h(X)) proper(a()) -> ok(a()) proper(b()) -> ok(b()) proper(f(X1,X2)) -> f(proper(X1),proper(X2)) proper(g(X1,X2)) -> g(proper(X1),proper(X2)) proper(h(X)) -> h(proper(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) - Signature: {active/1,f/2,g/2,h/1,proper/1,top/1,active#/1,f#/2,g#/2,h#/1,proper#/1,top#/1} / {a/0,b/0,mark/1,ok/1,c_1/0 ,c_2/1,c_3/2,c_4/2,c_5/1,c_6/2,c_7/1,c_8/1,c_9/1,c_10/1,c_11/1,c_12/1,c_13/1,c_14/0,c_15/0,c_16/3,c_17/3 ,c_18/2,c_19/2,c_20/2} - Obligation: innermost runtime complexity wrt. defined symbols {active#,f#,g#,h#,proper#,top#} and constructors {a,b,mark ,ok} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: active(a()) -> mark(b()) active(f(X,X)) -> mark(h(a())) active(f(X1,X2)) -> f(active(X1),X2) active(g(X1,X2)) -> g(active(X1),X2) active(g(a(),X)) -> mark(f(b(),X)) active(h(X)) -> h(active(X)) active(h(X)) -> mark(g(X,X)) f(mark(X1),X2) -> mark(f(X1,X2)) f(ok(X1),ok(X2)) -> ok(f(X1,X2)) g(mark(X1),X2) -> mark(g(X1,X2)) g(ok(X1),ok(X2)) -> ok(g(X1,X2)) h(mark(X)) -> mark(h(X)) h(ok(X)) -> ok(h(X)) proper(a()) -> ok(a()) proper(b()) -> ok(b()) proper(f(X1,X2)) -> f(proper(X1),proper(X2)) proper(g(X1,X2)) -> g(proper(X1),proper(X2)) proper(h(X)) -> h(proper(X)) active#(a()) -> c_1() active#(f(X,X)) -> c_2(h#(a())) active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)) active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)) active#(g(a(),X)) -> c_5(f#(b(),X)) active#(h(X)) -> c_6(h#(active(X)),active#(X)) active#(h(X)) -> c_7(g#(X,X)) f#(mark(X1),X2) -> c_8(f#(X1,X2)) f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)) g#(mark(X1),X2) -> c_10(g#(X1,X2)) g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)) h#(mark(X)) -> c_12(h#(X)) h#(ok(X)) -> c_13(h#(X)) proper#(a()) -> c_14() proper#(b()) -> c_15() proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)) top#(mark(X)) -> c_19(top#(proper(X)),proper#(X)) top#(ok(X)) -> c_20(top#(active(X)),active#(X)) * Step 3: PredecessorEstimation MAYBE + Considered Problem: - Strict DPs: active#(a()) -> c_1() active#(f(X,X)) -> c_2(h#(a())) active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)) active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)) active#(g(a(),X)) -> c_5(f#(b(),X)) active#(h(X)) -> c_6(h#(active(X)),active#(X)) active#(h(X)) -> c_7(g#(X,X)) f#(mark(X1),X2) -> c_8(f#(X1,X2)) f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)) g#(mark(X1),X2) -> c_10(g#(X1,X2)) g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)) h#(mark(X)) -> c_12(h#(X)) h#(ok(X)) -> c_13(h#(X)) proper#(a()) -> c_14() proper#(b()) -> c_15() proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)) top#(mark(X)) -> c_19(top#(proper(X)),proper#(X)) top#(ok(X)) -> c_20(top#(active(X)),active#(X)) - Weak TRS: active(a()) -> mark(b()) active(f(X,X)) -> mark(h(a())) active(f(X1,X2)) -> f(active(X1),X2) active(g(X1,X2)) -> g(active(X1),X2) active(g(a(),X)) -> mark(f(b(),X)) active(h(X)) -> h(active(X)) active(h(X)) -> mark(g(X,X)) f(mark(X1),X2) -> mark(f(X1,X2)) f(ok(X1),ok(X2)) -> ok(f(X1,X2)) g(mark(X1),X2) -> mark(g(X1,X2)) g(ok(X1),ok(X2)) -> ok(g(X1,X2)) h(mark(X)) -> mark(h(X)) h(ok(X)) -> ok(h(X)) proper(a()) -> ok(a()) proper(b()) -> ok(b()) proper(f(X1,X2)) -> f(proper(X1),proper(X2)) proper(g(X1,X2)) -> g(proper(X1),proper(X2)) proper(h(X)) -> h(proper(X)) - Signature: {active/1,f/2,g/2,h/1,proper/1,top/1,active#/1,f#/2,g#/2,h#/1,proper#/1,top#/1} / {a/0,b/0,mark/1,ok/1,c_1/0 ,c_2/1,c_3/2,c_4/2,c_5/1,c_6/2,c_7/1,c_8/1,c_9/1,c_10/1,c_11/1,c_12/1,c_13/1,c_14/0,c_15/0,c_16/3,c_17/3 ,c_18/2,c_19/2,c_20/2} - Obligation: innermost runtime complexity wrt. defined symbols {active#,f#,g#,h#,proper#,top#} and constructors {a,b,mark ,ok} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,2,5,14,15} by application of Pre({1,2,5,14,15}) = {3,4,6,16,17,18,19,20}. Here rules are labelled as follows: 1: active#(a()) -> c_1() 2: active#(f(X,X)) -> c_2(h#(a())) 3: active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)) 4: active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)) 5: active#(g(a(),X)) -> c_5(f#(b(),X)) 6: active#(h(X)) -> c_6(h#(active(X)),active#(X)) 7: active#(h(X)) -> c_7(g#(X,X)) 8: f#(mark(X1),X2) -> c_8(f#(X1,X2)) 9: f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)) 10: g#(mark(X1),X2) -> c_10(g#(X1,X2)) 11: g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)) 12: h#(mark(X)) -> c_12(h#(X)) 13: h#(ok(X)) -> c_13(h#(X)) 14: proper#(a()) -> c_14() 15: proper#(b()) -> c_15() 16: proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) 17: proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) 18: proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)) 19: top#(mark(X)) -> c_19(top#(proper(X)),proper#(X)) 20: top#(ok(X)) -> c_20(top#(active(X)),active#(X)) * Step 4: RemoveWeakSuffixes MAYBE + Considered Problem: - Strict DPs: active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)) active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)) active#(h(X)) -> c_6(h#(active(X)),active#(X)) active#(h(X)) -> c_7(g#(X,X)) f#(mark(X1),X2) -> c_8(f#(X1,X2)) f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)) g#(mark(X1),X2) -> c_10(g#(X1,X2)) g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)) h#(mark(X)) -> c_12(h#(X)) h#(ok(X)) -> c_13(h#(X)) proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)) top#(mark(X)) -> c_19(top#(proper(X)),proper#(X)) top#(ok(X)) -> c_20(top#(active(X)),active#(X)) - Weak DPs: active#(a()) -> c_1() active#(f(X,X)) -> c_2(h#(a())) active#(g(a(),X)) -> c_5(f#(b(),X)) proper#(a()) -> c_14() proper#(b()) -> c_15() - Weak TRS: active(a()) -> mark(b()) active(f(X,X)) -> mark(h(a())) active(f(X1,X2)) -> f(active(X1),X2) active(g(X1,X2)) -> g(active(X1),X2) active(g(a(),X)) -> mark(f(b(),X)) active(h(X)) -> h(active(X)) active(h(X)) -> mark(g(X,X)) f(mark(X1),X2) -> mark(f(X1,X2)) f(ok(X1),ok(X2)) -> ok(f(X1,X2)) g(mark(X1),X2) -> mark(g(X1,X2)) g(ok(X1),ok(X2)) -> ok(g(X1,X2)) h(mark(X)) -> mark(h(X)) h(ok(X)) -> ok(h(X)) proper(a()) -> ok(a()) proper(b()) -> ok(b()) proper(f(X1,X2)) -> f(proper(X1),proper(X2)) proper(g(X1,X2)) -> g(proper(X1),proper(X2)) proper(h(X)) -> h(proper(X)) - Signature: {active/1,f/2,g/2,h/1,proper/1,top/1,active#/1,f#/2,g#/2,h#/1,proper#/1,top#/1} / {a/0,b/0,mark/1,ok/1,c_1/0 ,c_2/1,c_3/2,c_4/2,c_5/1,c_6/2,c_7/1,c_8/1,c_9/1,c_10/1,c_11/1,c_12/1,c_13/1,c_14/0,c_15/0,c_16/3,c_17/3 ,c_18/2,c_19/2,c_20/2} - Obligation: innermost runtime complexity wrt. defined symbols {active#,f#,g#,h#,proper#,top#} and constructors {a,b,mark ,ok} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)) -->_1 f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)):6 -->_1 f#(mark(X1),X2) -> c_8(f#(X1,X2)):5 -->_2 active#(h(X)) -> c_7(g#(X,X)):4 -->_2 active#(h(X)) -> c_6(h#(active(X)),active#(X)):3 -->_2 active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)):2 -->_2 active#(g(a(),X)) -> c_5(f#(b(),X)):18 -->_2 active#(f(X,X)) -> c_2(h#(a())):17 -->_2 active#(a()) -> c_1():16 -->_2 active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)):1 2:S:active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)) -->_1 g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)):8 -->_1 g#(mark(X1),X2) -> c_10(g#(X1,X2)):7 -->_2 active#(h(X)) -> c_7(g#(X,X)):4 -->_2 active#(h(X)) -> c_6(h#(active(X)),active#(X)):3 -->_2 active#(g(a(),X)) -> c_5(f#(b(),X)):18 -->_2 active#(f(X,X)) -> c_2(h#(a())):17 -->_2 active#(a()) -> c_1():16 -->_2 active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)):2 -->_2 active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)):1 3:S:active#(h(X)) -> c_6(h#(active(X)),active#(X)) -->_1 h#(ok(X)) -> c_13(h#(X)):10 -->_1 h#(mark(X)) -> c_12(h#(X)):9 -->_2 active#(h(X)) -> c_7(g#(X,X)):4 -->_2 active#(g(a(),X)) -> c_5(f#(b(),X)):18 -->_2 active#(f(X,X)) -> c_2(h#(a())):17 -->_2 active#(a()) -> c_1():16 -->_2 active#(h(X)) -> c_6(h#(active(X)),active#(X)):3 -->_2 active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)):2 -->_2 active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)):1 4:S:active#(h(X)) -> c_7(g#(X,X)) -->_1 g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)):8 -->_1 g#(mark(X1),X2) -> c_10(g#(X1,X2)):7 5:S:f#(mark(X1),X2) -> c_8(f#(X1,X2)) -->_1 f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)):6 -->_1 f#(mark(X1),X2) -> c_8(f#(X1,X2)):5 6:S:f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)) -->_1 f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)):6 -->_1 f#(mark(X1),X2) -> c_8(f#(X1,X2)):5 7:S:g#(mark(X1),X2) -> c_10(g#(X1,X2)) -->_1 g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)):8 -->_1 g#(mark(X1),X2) -> c_10(g#(X1,X2)):7 8:S:g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)) -->_1 g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)):8 -->_1 g#(mark(X1),X2) -> c_10(g#(X1,X2)):7 9:S:h#(mark(X)) -> c_12(h#(X)) -->_1 h#(ok(X)) -> c_13(h#(X)):10 -->_1 h#(mark(X)) -> c_12(h#(X)):9 10:S:h#(ok(X)) -> c_13(h#(X)) -->_1 h#(ok(X)) -> c_13(h#(X)):10 -->_1 h#(mark(X)) -> c_12(h#(X)):9 11:S:proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) -->_3 proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)):13 -->_2 proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)):13 -->_3 proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):12 -->_2 proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):12 -->_3 proper#(b()) -> c_15():20 -->_2 proper#(b()) -> c_15():20 -->_3 proper#(a()) -> c_14():19 -->_2 proper#(a()) -> c_14():19 -->_3 proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):11 -->_2 proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):11 -->_1 f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)):6 -->_1 f#(mark(X1),X2) -> c_8(f#(X1,X2)):5 12:S:proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) -->_3 proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)):13 -->_2 proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)):13 -->_3 proper#(b()) -> c_15():20 -->_2 proper#(b()) -> c_15():20 -->_3 proper#(a()) -> c_14():19 -->_2 proper#(a()) -> c_14():19 -->_3 proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):12 -->_2 proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):12 -->_3 proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):11 -->_2 proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):11 -->_1 g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)):8 -->_1 g#(mark(X1),X2) -> c_10(g#(X1,X2)):7 13:S:proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)) -->_2 proper#(b()) -> c_15():20 -->_2 proper#(a()) -> c_14():19 -->_2 proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)):13 -->_2 proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):12 -->_2 proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):11 -->_1 h#(ok(X)) -> c_13(h#(X)):10 -->_1 h#(mark(X)) -> c_12(h#(X)):9 14:S:top#(mark(X)) -> c_19(top#(proper(X)),proper#(X)) -->_1 top#(ok(X)) -> c_20(top#(active(X)),active#(X)):15 -->_2 proper#(b()) -> c_15():20 -->_2 proper#(a()) -> c_14():19 -->_1 top#(mark(X)) -> c_19(top#(proper(X)),proper#(X)):14 -->_2 proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)):13 -->_2 proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):12 -->_2 proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)):11 15:S:top#(ok(X)) -> c_20(top#(active(X)),active#(X)) -->_2 active#(g(a(),X)) -> c_5(f#(b(),X)):18 -->_2 active#(f(X,X)) -> c_2(h#(a())):17 -->_2 active#(a()) -> c_1():16 -->_1 top#(ok(X)) -> c_20(top#(active(X)),active#(X)):15 -->_1 top#(mark(X)) -> c_19(top#(proper(X)),proper#(X)):14 -->_2 active#(h(X)) -> c_7(g#(X,X)):4 -->_2 active#(h(X)) -> c_6(h#(active(X)),active#(X)):3 -->_2 active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)):2 -->_2 active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)):1 16:W:active#(a()) -> c_1() 17:W:active#(f(X,X)) -> c_2(h#(a())) 18:W:active#(g(a(),X)) -> c_5(f#(b(),X)) 19:W:proper#(a()) -> c_14() 20:W:proper#(b()) -> c_15() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 19: proper#(a()) -> c_14() 20: proper#(b()) -> c_15() 16: active#(a()) -> c_1() 17: active#(f(X,X)) -> c_2(h#(a())) 18: active#(g(a(),X)) -> c_5(f#(b(),X)) * Step 5: Failure MAYBE + Considered Problem: - Strict DPs: active#(f(X1,X2)) -> c_3(f#(active(X1),X2),active#(X1)) active#(g(X1,X2)) -> c_4(g#(active(X1),X2),active#(X1)) active#(h(X)) -> c_6(h#(active(X)),active#(X)) active#(h(X)) -> c_7(g#(X,X)) f#(mark(X1),X2) -> c_8(f#(X1,X2)) f#(ok(X1),ok(X2)) -> c_9(f#(X1,X2)) g#(mark(X1),X2) -> c_10(g#(X1,X2)) g#(ok(X1),ok(X2)) -> c_11(g#(X1,X2)) h#(mark(X)) -> c_12(h#(X)) h#(ok(X)) -> c_13(h#(X)) proper#(f(X1,X2)) -> c_16(f#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(g(X1,X2)) -> c_17(g#(proper(X1),proper(X2)),proper#(X1),proper#(X2)) proper#(h(X)) -> c_18(h#(proper(X)),proper#(X)) top#(mark(X)) -> c_19(top#(proper(X)),proper#(X)) top#(ok(X)) -> c_20(top#(active(X)),active#(X)) - Weak TRS: active(a()) -> mark(b()) active(f(X,X)) -> mark(h(a())) active(f(X1,X2)) -> f(active(X1),X2) active(g(X1,X2)) -> g(active(X1),X2) active(g(a(),X)) -> mark(f(b(),X)) active(h(X)) -> h(active(X)) active(h(X)) -> mark(g(X,X)) f(mark(X1),X2) -> mark(f(X1,X2)) f(ok(X1),ok(X2)) -> ok(f(X1,X2)) g(mark(X1),X2) -> mark(g(X1,X2)) g(ok(X1),ok(X2)) -> ok(g(X1,X2)) h(mark(X)) -> mark(h(X)) h(ok(X)) -> ok(h(X)) proper(a()) -> ok(a()) proper(b()) -> ok(b()) proper(f(X1,X2)) -> f(proper(X1),proper(X2)) proper(g(X1,X2)) -> g(proper(X1),proper(X2)) proper(h(X)) -> h(proper(X)) - Signature: {active/1,f/2,g/2,h/1,proper/1,top/1,active#/1,f#/2,g#/2,h#/1,proper#/1,top#/1} / {a/0,b/0,mark/1,ok/1,c_1/0 ,c_2/1,c_3/2,c_4/2,c_5/1,c_6/2,c_7/1,c_8/1,c_9/1,c_10/1,c_11/1,c_12/1,c_13/1,c_14/0,c_15/0,c_16/3,c_17/3 ,c_18/2,c_19/2,c_20/2} - Obligation: innermost runtime complexity wrt. defined symbols {active#,f#,g#,h#,proper#,top#} and constructors {a,b,mark ,ok} + Applied Processor: EmptyProcessor + Details: The problem is still open. MAYBE