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