MAYBE We are left with following problem, upon which TcT provides the certificate MAYBE. Strict Trs: { plus(x, y) -> ifPlus(isZero(x), x, inc(y)) , ifPlus(true(), x, y) -> p(y) , ifPlus(false(), x, y) -> plus(p(x), y) , isZero(0()) -> true() , isZero(s(0())) -> false() , isZero(s(s(x))) -> isZero(s(x)) , inc(x) -> s(x) , inc(0()) -> s(0()) , inc(s(x)) -> s(inc(x)) , p(0()) -> 0() , p(s(x)) -> x , p(s(s(x))) -> s(p(s(x))) , times(x, y) -> timesIter(0(), x, y, 0()) , timesIter(i, x, y, z) -> ifTimes(ge(i, x), i, x, y, z) , ifTimes(true(), i, x, y, z) -> z , ifTimes(false(), i, x, y, z) -> timesIter(inc(i), x, y, plus(z, y)) , ge(x, 0()) -> true() , ge(0(), s(y)) -> false() , ge(s(x), s(y)) -> ge(x, y) , f0(x, y, z) -> d() , f0(0(), y, x) -> f1(x, y, x) , f1(x, y, z) -> f2(x, y, z) , f1(x, y, z) -> c() , f2(x, 1(), z) -> f0(x, z, z) } Obligation: innermost runtime complexity Answer: MAYBE We add following dependency tuples: Strict DPs: { plus^#(x, y) -> c_1(ifPlus^#(isZero(x), x, inc(y)), isZero^#(x), inc^#(y)) , ifPlus^#(true(), x, y) -> c_2(p^#(y)) , ifPlus^#(false(), x, y) -> c_3(plus^#(p(x), y), p^#(x)) , isZero^#(0()) -> c_4() , isZero^#(s(0())) -> c_5() , isZero^#(s(s(x))) -> c_6(isZero^#(s(x))) , inc^#(x) -> c_7() , inc^#(0()) -> c_8() , inc^#(s(x)) -> c_9(inc^#(x)) , p^#(0()) -> c_10() , p^#(s(x)) -> c_11() , p^#(s(s(x))) -> c_12(p^#(s(x))) , times^#(x, y) -> c_13(timesIter^#(0(), x, y, 0())) , timesIter^#(i, x, y, z) -> c_14(ifTimes^#(ge(i, x), i, x, y, z), ge^#(i, x)) , ifTimes^#(true(), i, x, y, z) -> c_15() , ifTimes^#(false(), i, x, y, z) -> c_16(timesIter^#(inc(i), x, y, plus(z, y)), inc^#(i), plus^#(z, y)) , ge^#(x, 0()) -> c_17() , ge^#(0(), s(y)) -> c_18() , ge^#(s(x), s(y)) -> c_19(ge^#(x, y)) , f0^#(x, y, z) -> c_20() , f0^#(0(), y, x) -> c_21(f1^#(x, y, x)) , f1^#(x, y, z) -> c_22(f2^#(x, y, z)) , f1^#(x, y, z) -> c_23() , f2^#(x, 1(), z) -> c_24(f0^#(x, z, z)) } and mark the set of starting terms. We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { plus^#(x, y) -> c_1(ifPlus^#(isZero(x), x, inc(y)), isZero^#(x), inc^#(y)) , ifPlus^#(true(), x, y) -> c_2(p^#(y)) , ifPlus^#(false(), x, y) -> c_3(plus^#(p(x), y), p^#(x)) , isZero^#(0()) -> c_4() , isZero^#(s(0())) -> c_5() , isZero^#(s(s(x))) -> c_6(isZero^#(s(x))) , inc^#(x) -> c_7() , inc^#(0()) -> c_8() , inc^#(s(x)) -> c_9(inc^#(x)) , p^#(0()) -> c_10() , p^#(s(x)) -> c_11() , p^#(s(s(x))) -> c_12(p^#(s(x))) , times^#(x, y) -> c_13(timesIter^#(0(), x, y, 0())) , timesIter^#(i, x, y, z) -> c_14(ifTimes^#(ge(i, x), i, x, y, z), ge^#(i, x)) , ifTimes^#(true(), i, x, y, z) -> c_15() , ifTimes^#(false(), i, x, y, z) -> c_16(timesIter^#(inc(i), x, y, plus(z, y)), inc^#(i), plus^#(z, y)) , ge^#(x, 0()) -> c_17() , ge^#(0(), s(y)) -> c_18() , ge^#(s(x), s(y)) -> c_19(ge^#(x, y)) , f0^#(x, y, z) -> c_20() , f0^#(0(), y, x) -> c_21(f1^#(x, y, x)) , f1^#(x, y, z) -> c_22(f2^#(x, y, z)) , f1^#(x, y, z) -> c_23() , f2^#(x, 1(), z) -> c_24(f0^#(x, z, z)) } Weak Trs: { plus(x, y) -> ifPlus(isZero(x), x, inc(y)) , ifPlus(true(), x, y) -> p(y) , ifPlus(false(), x, y) -> plus(p(x), y) , isZero(0()) -> true() , isZero(s(0())) -> false() , isZero(s(s(x))) -> isZero(s(x)) , inc(x) -> s(x) , inc(0()) -> s(0()) , inc(s(x)) -> s(inc(x)) , p(0()) -> 0() , p(s(x)) -> x , p(s(s(x))) -> s(p(s(x))) , times(x, y) -> timesIter(0(), x, y, 0()) , timesIter(i, x, y, z) -> ifTimes(ge(i, x), i, x, y, z) , ifTimes(true(), i, x, y, z) -> z , ifTimes(false(), i, x, y, z) -> timesIter(inc(i), x, y, plus(z, y)) , ge(x, 0()) -> true() , ge(0(), s(y)) -> false() , ge(s(x), s(y)) -> ge(x, y) , f0(x, y, z) -> d() , f0(0(), y, x) -> f1(x, y, x) , f1(x, y, z) -> f2(x, y, z) , f1(x, y, z) -> c() , f2(x, 1(), z) -> f0(x, z, z) } Obligation: innermost runtime complexity Answer: MAYBE We estimate the number of application of {4,5,7,8,10,11,15,17,18,20,23} by applications of Pre({4,5,7,8,10,11,15,17,18,20,23}) = {1,2,3,6,9,12,14,16,19,21,24}. Here rules are labeled as follows: DPs: { 1: plus^#(x, y) -> c_1(ifPlus^#(isZero(x), x, inc(y)), isZero^#(x), inc^#(y)) , 2: ifPlus^#(true(), x, y) -> c_2(p^#(y)) , 3: ifPlus^#(false(), x, y) -> c_3(plus^#(p(x), y), p^#(x)) , 4: isZero^#(0()) -> c_4() , 5: isZero^#(s(0())) -> c_5() , 6: isZero^#(s(s(x))) -> c_6(isZero^#(s(x))) , 7: inc^#(x) -> c_7() , 8: inc^#(0()) -> c_8() , 9: inc^#(s(x)) -> c_9(inc^#(x)) , 10: p^#(0()) -> c_10() , 11: p^#(s(x)) -> c_11() , 12: p^#(s(s(x))) -> c_12(p^#(s(x))) , 13: times^#(x, y) -> c_13(timesIter^#(0(), x, y, 0())) , 14: timesIter^#(i, x, y, z) -> c_14(ifTimes^#(ge(i, x), i, x, y, z), ge^#(i, x)) , 15: ifTimes^#(true(), i, x, y, z) -> c_15() , 16: ifTimes^#(false(), i, x, y, z) -> c_16(timesIter^#(inc(i), x, y, plus(z, y)), inc^#(i), plus^#(z, y)) , 17: ge^#(x, 0()) -> c_17() , 18: ge^#(0(), s(y)) -> c_18() , 19: ge^#(s(x), s(y)) -> c_19(ge^#(x, y)) , 20: f0^#(x, y, z) -> c_20() , 21: f0^#(0(), y, x) -> c_21(f1^#(x, y, x)) , 22: f1^#(x, y, z) -> c_22(f2^#(x, y, z)) , 23: f1^#(x, y, z) -> c_23() , 24: f2^#(x, 1(), z) -> c_24(f0^#(x, z, z)) } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { plus^#(x, y) -> c_1(ifPlus^#(isZero(x), x, inc(y)), isZero^#(x), inc^#(y)) , ifPlus^#(true(), x, y) -> c_2(p^#(y)) , ifPlus^#(false(), x, y) -> c_3(plus^#(p(x), y), p^#(x)) , isZero^#(s(s(x))) -> c_6(isZero^#(s(x))) , inc^#(s(x)) -> c_9(inc^#(x)) , p^#(s(s(x))) -> c_12(p^#(s(x))) , times^#(x, y) -> c_13(timesIter^#(0(), x, y, 0())) , timesIter^#(i, x, y, z) -> c_14(ifTimes^#(ge(i, x), i, x, y, z), ge^#(i, x)) , ifTimes^#(false(), i, x, y, z) -> c_16(timesIter^#(inc(i), x, y, plus(z, y)), inc^#(i), plus^#(z, y)) , ge^#(s(x), s(y)) -> c_19(ge^#(x, y)) , f0^#(0(), y, x) -> c_21(f1^#(x, y, x)) , f1^#(x, y, z) -> c_22(f2^#(x, y, z)) , f2^#(x, 1(), z) -> c_24(f0^#(x, z, z)) } Weak DPs: { isZero^#(0()) -> c_4() , isZero^#(s(0())) -> c_5() , inc^#(x) -> c_7() , inc^#(0()) -> c_8() , p^#(0()) -> c_10() , p^#(s(x)) -> c_11() , ifTimes^#(true(), i, x, y, z) -> c_15() , ge^#(x, 0()) -> c_17() , ge^#(0(), s(y)) -> c_18() , f0^#(x, y, z) -> c_20() , f1^#(x, y, z) -> c_23() } Weak Trs: { plus(x, y) -> ifPlus(isZero(x), x, inc(y)) , ifPlus(true(), x, y) -> p(y) , ifPlus(false(), x, y) -> plus(p(x), y) , isZero(0()) -> true() , isZero(s(0())) -> false() , isZero(s(s(x))) -> isZero(s(x)) , inc(x) -> s(x) , inc(0()) -> s(0()) , inc(s(x)) -> s(inc(x)) , p(0()) -> 0() , p(s(x)) -> x , p(s(s(x))) -> s(p(s(x))) , times(x, y) -> timesIter(0(), x, y, 0()) , timesIter(i, x, y, z) -> ifTimes(ge(i, x), i, x, y, z) , ifTimes(true(), i, x, y, z) -> z , ifTimes(false(), i, x, y, z) -> timesIter(inc(i), x, y, plus(z, y)) , ge(x, 0()) -> true() , ge(0(), s(y)) -> false() , ge(s(x), s(y)) -> ge(x, y) , f0(x, y, z) -> d() , f0(0(), y, x) -> f1(x, y, x) , f1(x, y, z) -> f2(x, y, z) , f1(x, y, z) -> c() , f2(x, 1(), z) -> f0(x, z, z) } Obligation: innermost runtime complexity Answer: MAYBE The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. { isZero^#(0()) -> c_4() , isZero^#(s(0())) -> c_5() , inc^#(x) -> c_7() , inc^#(0()) -> c_8() , p^#(0()) -> c_10() , p^#(s(x)) -> c_11() , ifTimes^#(true(), i, x, y, z) -> c_15() , ge^#(x, 0()) -> c_17() , ge^#(0(), s(y)) -> c_18() , f0^#(x, y, z) -> c_20() , f1^#(x, y, z) -> c_23() } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { plus^#(x, y) -> c_1(ifPlus^#(isZero(x), x, inc(y)), isZero^#(x), inc^#(y)) , ifPlus^#(true(), x, y) -> c_2(p^#(y)) , ifPlus^#(false(), x, y) -> c_3(plus^#(p(x), y), p^#(x)) , isZero^#(s(s(x))) -> c_6(isZero^#(s(x))) , inc^#(s(x)) -> c_9(inc^#(x)) , p^#(s(s(x))) -> c_12(p^#(s(x))) , times^#(x, y) -> c_13(timesIter^#(0(), x, y, 0())) , timesIter^#(i, x, y, z) -> c_14(ifTimes^#(ge(i, x), i, x, y, z), ge^#(i, x)) , ifTimes^#(false(), i, x, y, z) -> c_16(timesIter^#(inc(i), x, y, plus(z, y)), inc^#(i), plus^#(z, y)) , ge^#(s(x), s(y)) -> c_19(ge^#(x, y)) , f0^#(0(), y, x) -> c_21(f1^#(x, y, x)) , f1^#(x, y, z) -> c_22(f2^#(x, y, z)) , f2^#(x, 1(), z) -> c_24(f0^#(x, z, z)) } Weak Trs: { plus(x, y) -> ifPlus(isZero(x), x, inc(y)) , ifPlus(true(), x, y) -> p(y) , ifPlus(false(), x, y) -> plus(p(x), y) , isZero(0()) -> true() , isZero(s(0())) -> false() , isZero(s(s(x))) -> isZero(s(x)) , inc(x) -> s(x) , inc(0()) -> s(0()) , inc(s(x)) -> s(inc(x)) , p(0()) -> 0() , p(s(x)) -> x , p(s(s(x))) -> s(p(s(x))) , times(x, y) -> timesIter(0(), x, y, 0()) , timesIter(i, x, y, z) -> ifTimes(ge(i, x), i, x, y, z) , ifTimes(true(), i, x, y, z) -> z , ifTimes(false(), i, x, y, z) -> timesIter(inc(i), x, y, plus(z, y)) , ge(x, 0()) -> true() , ge(0(), s(y)) -> false() , ge(s(x), s(y)) -> ge(x, y) , f0(x, y, z) -> d() , f0(0(), y, x) -> f1(x, y, x) , f1(x, y, z) -> f2(x, y, z) , f1(x, y, z) -> c() , f2(x, 1(), z) -> f0(x, z, z) } Obligation: innermost runtime complexity Answer: MAYBE Consider the dependency graph 1: plus^#(x, y) -> c_1(ifPlus^#(isZero(x), x, inc(y)), isZero^#(x), inc^#(y)) -->_3 inc^#(s(x)) -> c_9(inc^#(x)) :5 -->_2 isZero^#(s(s(x))) -> c_6(isZero^#(s(x))) :4 -->_1 ifPlus^#(false(), x, y) -> c_3(plus^#(p(x), y), p^#(x)) :3 -->_1 ifPlus^#(true(), x, y) -> c_2(p^#(y)) :2 2: ifPlus^#(true(), x, y) -> c_2(p^#(y)) -->_1 p^#(s(s(x))) -> c_12(p^#(s(x))) :6 3: ifPlus^#(false(), x, y) -> c_3(plus^#(p(x), y), p^#(x)) -->_2 p^#(s(s(x))) -> c_12(p^#(s(x))) :6 -->_1 plus^#(x, y) -> c_1(ifPlus^#(isZero(x), x, inc(y)), isZero^#(x), inc^#(y)) :1 4: isZero^#(s(s(x))) -> c_6(isZero^#(s(x))) -->_1 isZero^#(s(s(x))) -> c_6(isZero^#(s(x))) :4 5: inc^#(s(x)) -> c_9(inc^#(x)) -->_1 inc^#(s(x)) -> c_9(inc^#(x)) :5 6: p^#(s(s(x))) -> c_12(p^#(s(x))) -->_1 p^#(s(s(x))) -> c_12(p^#(s(x))) :6 7: times^#(x, y) -> c_13(timesIter^#(0(), x, y, 0())) -->_1 timesIter^#(i, x, y, z) -> c_14(ifTimes^#(ge(i, x), i, x, y, z), ge^#(i, x)) :8 8: timesIter^#(i, x, y, z) -> c_14(ifTimes^#(ge(i, x), i, x, y, z), ge^#(i, x)) -->_2 ge^#(s(x), s(y)) -> c_19(ge^#(x, y)) :10 -->_1 ifTimes^#(false(), i, x, y, z) -> c_16(timesIter^#(inc(i), x, y, plus(z, y)), inc^#(i), plus^#(z, y)) :9 9: ifTimes^#(false(), i, x, y, z) -> c_16(timesIter^#(inc(i), x, y, plus(z, y)), inc^#(i), plus^#(z, y)) -->_1 timesIter^#(i, x, y, z) -> c_14(ifTimes^#(ge(i, x), i, x, y, z), ge^#(i, x)) :8 -->_2 inc^#(s(x)) -> c_9(inc^#(x)) :5 -->_3 plus^#(x, y) -> c_1(ifPlus^#(isZero(x), x, inc(y)), isZero^#(x), inc^#(y)) :1 10: ge^#(s(x), s(y)) -> c_19(ge^#(x, y)) -->_1 ge^#(s(x), s(y)) -> c_19(ge^#(x, y)) :10 11: f0^#(0(), y, x) -> c_21(f1^#(x, y, x)) -->_1 f1^#(x, y, z) -> c_22(f2^#(x, y, z)) :12 12: f1^#(x, y, z) -> c_22(f2^#(x, y, z)) -->_1 f2^#(x, 1(), z) -> c_24(f0^#(x, z, z)) :13 13: f2^#(x, 1(), z) -> c_24(f0^#(x, z, z)) -->_1 f0^#(0(), y, x) -> c_21(f1^#(x, y, x)) :11 Following roots of the dependency graph are removed, as the considered set of starting terms is closed under reduction with respect to these rules (modulo compound contexts). { times^#(x, y) -> c_13(timesIter^#(0(), x, y, 0())) } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { plus^#(x, y) -> c_1(ifPlus^#(isZero(x), x, inc(y)), isZero^#(x), inc^#(y)) , ifPlus^#(true(), x, y) -> c_2(p^#(y)) , ifPlus^#(false(), x, y) -> c_3(plus^#(p(x), y), p^#(x)) , isZero^#(s(s(x))) -> c_6(isZero^#(s(x))) , inc^#(s(x)) -> c_9(inc^#(x)) , p^#(s(s(x))) -> c_12(p^#(s(x))) , timesIter^#(i, x, y, z) -> c_14(ifTimes^#(ge(i, x), i, x, y, z), ge^#(i, x)) , ifTimes^#(false(), i, x, y, z) -> c_16(timesIter^#(inc(i), x, y, plus(z, y)), inc^#(i), plus^#(z, y)) , ge^#(s(x), s(y)) -> c_19(ge^#(x, y)) , f0^#(0(), y, x) -> c_21(f1^#(x, y, x)) , f1^#(x, y, z) -> c_22(f2^#(x, y, z)) , f2^#(x, 1(), z) -> c_24(f0^#(x, z, z)) } Weak Trs: { plus(x, y) -> ifPlus(isZero(x), x, inc(y)) , ifPlus(true(), x, y) -> p(y) , ifPlus(false(), x, y) -> plus(p(x), y) , isZero(0()) -> true() , isZero(s(0())) -> false() , isZero(s(s(x))) -> isZero(s(x)) , inc(x) -> s(x) , inc(0()) -> s(0()) , inc(s(x)) -> s(inc(x)) , p(0()) -> 0() , p(s(x)) -> x , p(s(s(x))) -> s(p(s(x))) , times(x, y) -> timesIter(0(), x, y, 0()) , timesIter(i, x, y, z) -> ifTimes(ge(i, x), i, x, y, z) , ifTimes(true(), i, x, y, z) -> z , ifTimes(false(), i, x, y, z) -> timesIter(inc(i), x, y, plus(z, y)) , ge(x, 0()) -> true() , ge(0(), s(y)) -> false() , ge(s(x), s(y)) -> ge(x, y) , f0(x, y, z) -> d() , f0(0(), y, x) -> f1(x, y, x) , f1(x, y, z) -> f2(x, y, z) , f1(x, y, z) -> c() , f2(x, 1(), z) -> f0(x, z, z) } Obligation: innermost runtime complexity Answer: MAYBE We replace rewrite rules by usable rules: Weak Usable Rules: { plus(x, y) -> ifPlus(isZero(x), x, inc(y)) , ifPlus(true(), x, y) -> p(y) , ifPlus(false(), x, y) -> plus(p(x), y) , isZero(0()) -> true() , isZero(s(0())) -> false() , isZero(s(s(x))) -> isZero(s(x)) , inc(x) -> s(x) , inc(0()) -> s(0()) , inc(s(x)) -> s(inc(x)) , p(0()) -> 0() , p(s(x)) -> x , p(s(s(x))) -> s(p(s(x))) , ge(x, 0()) -> true() , ge(0(), s(y)) -> false() , ge(s(x), s(y)) -> ge(x, y) } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { plus^#(x, y) -> c_1(ifPlus^#(isZero(x), x, inc(y)), isZero^#(x), inc^#(y)) , ifPlus^#(true(), x, y) -> c_2(p^#(y)) , ifPlus^#(false(), x, y) -> c_3(plus^#(p(x), y), p^#(x)) , isZero^#(s(s(x))) -> c_6(isZero^#(s(x))) , inc^#(s(x)) -> c_9(inc^#(x)) , p^#(s(s(x))) -> c_12(p^#(s(x))) , timesIter^#(i, x, y, z) -> c_14(ifTimes^#(ge(i, x), i, x, y, z), ge^#(i, x)) , ifTimes^#(false(), i, x, y, z) -> c_16(timesIter^#(inc(i), x, y, plus(z, y)), inc^#(i), plus^#(z, y)) , ge^#(s(x), s(y)) -> c_19(ge^#(x, y)) , f0^#(0(), y, x) -> c_21(f1^#(x, y, x)) , f1^#(x, y, z) -> c_22(f2^#(x, y, z)) , f2^#(x, 1(), z) -> c_24(f0^#(x, z, z)) } Weak Trs: { plus(x, y) -> ifPlus(isZero(x), x, inc(y)) , ifPlus(true(), x, y) -> p(y) , ifPlus(false(), x, y) -> plus(p(x), y) , isZero(0()) -> true() , isZero(s(0())) -> false() , isZero(s(s(x))) -> isZero(s(x)) , inc(x) -> s(x) , inc(0()) -> s(0()) , inc(s(x)) -> s(inc(x)) , p(0()) -> 0() , p(s(x)) -> x , p(s(s(x))) -> s(p(s(x))) , ge(x, 0()) -> true() , ge(0(), s(y)) -> false() , ge(s(x), s(y)) -> ge(x, y) } Obligation: innermost runtime complexity Answer: MAYBE None of the processors succeeded. Details of failed attempt(s): ----------------------------- 1) 'matrices' failed due to the following reason: None of the processors succeeded. Details of failed attempt(s): ----------------------------- 1) 'matrix interpretation of dimension 4' failed due to the following reason: The input cannot be shown compatible 2) 'matrix interpretation of dimension 3' failed due to the following reason: The input cannot be shown compatible 3) 'matrix interpretation of dimension 3' failed due to the following reason: The input cannot be shown compatible 4) 'matrix interpretation of dimension 2' failed due to the following reason: The input cannot be shown compatible 5) 'matrix interpretation of dimension 2' failed due to the following reason: The input cannot be shown compatible 6) 'matrix interpretation of dimension 1' failed due to the following reason: The input cannot be shown compatible 2) 'empty' failed due to the following reason: Empty strict component of the problem is NOT empty. Arrrr..