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