MAYBE We are left with following problem, upon which TcT provides the certificate MAYBE. Strict Trs: { div(x, s(y)) -> d(x, s(y), 0()) , d(x, s(y), z) -> cond(ge(x, z), x, y, z) , cond(true(), x, y, z) -> s(d(x, s(y), plus(s(y), z))) , cond(false(), x, y, z) -> 0() , ge(u, 0()) -> true() , ge(s(u), s(v)) -> ge(u, v) , ge(0(), s(v)) -> false() , plus(n, s(m)) -> s(plus(n, m)) , plus(n, 0()) -> n } Obligation: innermost runtime complexity Answer: MAYBE We add following dependency tuples: Strict DPs: { div^#(x, s(y)) -> c_1(d^#(x, s(y), 0())) , d^#(x, s(y), z) -> c_2(cond^#(ge(x, z), x, y, z), ge^#(x, z)) , cond^#(true(), x, y, z) -> c_3(d^#(x, s(y), plus(s(y), z)), plus^#(s(y), z)) , cond^#(false(), x, y, z) -> c_4() , ge^#(u, 0()) -> c_5() , ge^#(s(u), s(v)) -> c_6(ge^#(u, v)) , ge^#(0(), s(v)) -> c_7() , plus^#(n, s(m)) -> c_8(plus^#(n, m)) , plus^#(n, 0()) -> c_9() } and mark the set of starting terms. We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { div^#(x, s(y)) -> c_1(d^#(x, s(y), 0())) , d^#(x, s(y), z) -> c_2(cond^#(ge(x, z), x, y, z), ge^#(x, z)) , cond^#(true(), x, y, z) -> c_3(d^#(x, s(y), plus(s(y), z)), plus^#(s(y), z)) , cond^#(false(), x, y, z) -> c_4() , ge^#(u, 0()) -> c_5() , ge^#(s(u), s(v)) -> c_6(ge^#(u, v)) , ge^#(0(), s(v)) -> c_7() , plus^#(n, s(m)) -> c_8(plus^#(n, m)) , plus^#(n, 0()) -> c_9() } Weak Trs: { div(x, s(y)) -> d(x, s(y), 0()) , d(x, s(y), z) -> cond(ge(x, z), x, y, z) , cond(true(), x, y, z) -> s(d(x, s(y), plus(s(y), z))) , cond(false(), x, y, z) -> 0() , ge(u, 0()) -> true() , ge(s(u), s(v)) -> ge(u, v) , ge(0(), s(v)) -> false() , plus(n, s(m)) -> s(plus(n, m)) , plus(n, 0()) -> n } Obligation: innermost runtime complexity Answer: MAYBE We estimate the number of application of {4,5,7,9} by applications of Pre({4,5,7,9}) = {2,3,6,8}. Here rules are labeled as follows: DPs: { 1: div^#(x, s(y)) -> c_1(d^#(x, s(y), 0())) , 2: d^#(x, s(y), z) -> c_2(cond^#(ge(x, z), x, y, z), ge^#(x, z)) , 3: cond^#(true(), x, y, z) -> c_3(d^#(x, s(y), plus(s(y), z)), plus^#(s(y), z)) , 4: cond^#(false(), x, y, z) -> c_4() , 5: ge^#(u, 0()) -> c_5() , 6: ge^#(s(u), s(v)) -> c_6(ge^#(u, v)) , 7: ge^#(0(), s(v)) -> c_7() , 8: plus^#(n, s(m)) -> c_8(plus^#(n, m)) , 9: plus^#(n, 0()) -> c_9() } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { div^#(x, s(y)) -> c_1(d^#(x, s(y), 0())) , d^#(x, s(y), z) -> c_2(cond^#(ge(x, z), x, y, z), ge^#(x, z)) , cond^#(true(), x, y, z) -> c_3(d^#(x, s(y), plus(s(y), z)), plus^#(s(y), z)) , ge^#(s(u), s(v)) -> c_6(ge^#(u, v)) , plus^#(n, s(m)) -> c_8(plus^#(n, m)) } Weak DPs: { cond^#(false(), x, y, z) -> c_4() , ge^#(u, 0()) -> c_5() , ge^#(0(), s(v)) -> c_7() , plus^#(n, 0()) -> c_9() } Weak Trs: { div(x, s(y)) -> d(x, s(y), 0()) , d(x, s(y), z) -> cond(ge(x, z), x, y, z) , cond(true(), x, y, z) -> s(d(x, s(y), plus(s(y), z))) , cond(false(), x, y, z) -> 0() , ge(u, 0()) -> true() , ge(s(u), s(v)) -> ge(u, v) , ge(0(), s(v)) -> false() , plus(n, s(m)) -> s(plus(n, m)) , plus(n, 0()) -> n } 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. { cond^#(false(), x, y, z) -> c_4() , ge^#(u, 0()) -> c_5() , ge^#(0(), s(v)) -> c_7() , plus^#(n, 0()) -> c_9() } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { div^#(x, s(y)) -> c_1(d^#(x, s(y), 0())) , d^#(x, s(y), z) -> c_2(cond^#(ge(x, z), x, y, z), ge^#(x, z)) , cond^#(true(), x, y, z) -> c_3(d^#(x, s(y), plus(s(y), z)), plus^#(s(y), z)) , ge^#(s(u), s(v)) -> c_6(ge^#(u, v)) , plus^#(n, s(m)) -> c_8(plus^#(n, m)) } Weak Trs: { div(x, s(y)) -> d(x, s(y), 0()) , d(x, s(y), z) -> cond(ge(x, z), x, y, z) , cond(true(), x, y, z) -> s(d(x, s(y), plus(s(y), z))) , cond(false(), x, y, z) -> 0() , ge(u, 0()) -> true() , ge(s(u), s(v)) -> ge(u, v) , ge(0(), s(v)) -> false() , plus(n, s(m)) -> s(plus(n, m)) , plus(n, 0()) -> n } Obligation: innermost runtime complexity Answer: MAYBE Consider the dependency graph 1: div^#(x, s(y)) -> c_1(d^#(x, s(y), 0())) -->_1 d^#(x, s(y), z) -> c_2(cond^#(ge(x, z), x, y, z), ge^#(x, z)) :2 2: d^#(x, s(y), z) -> c_2(cond^#(ge(x, z), x, y, z), ge^#(x, z)) -->_2 ge^#(s(u), s(v)) -> c_6(ge^#(u, v)) :4 -->_1 cond^#(true(), x, y, z) -> c_3(d^#(x, s(y), plus(s(y), z)), plus^#(s(y), z)) :3 3: cond^#(true(), x, y, z) -> c_3(d^#(x, s(y), plus(s(y), z)), plus^#(s(y), z)) -->_2 plus^#(n, s(m)) -> c_8(plus^#(n, m)) :5 -->_1 d^#(x, s(y), z) -> c_2(cond^#(ge(x, z), x, y, z), ge^#(x, z)) :2 4: ge^#(s(u), s(v)) -> c_6(ge^#(u, v)) -->_1 ge^#(s(u), s(v)) -> c_6(ge^#(u, v)) :4 5: plus^#(n, s(m)) -> c_8(plus^#(n, m)) -->_1 plus^#(n, s(m)) -> c_8(plus^#(n, m)) :5 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). { div^#(x, s(y)) -> c_1(d^#(x, s(y), 0())) } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { d^#(x, s(y), z) -> c_2(cond^#(ge(x, z), x, y, z), ge^#(x, z)) , cond^#(true(), x, y, z) -> c_3(d^#(x, s(y), plus(s(y), z)), plus^#(s(y), z)) , ge^#(s(u), s(v)) -> c_6(ge^#(u, v)) , plus^#(n, s(m)) -> c_8(plus^#(n, m)) } Weak Trs: { div(x, s(y)) -> d(x, s(y), 0()) , d(x, s(y), z) -> cond(ge(x, z), x, y, z) , cond(true(), x, y, z) -> s(d(x, s(y), plus(s(y), z))) , cond(false(), x, y, z) -> 0() , ge(u, 0()) -> true() , ge(s(u), s(v)) -> ge(u, v) , ge(0(), s(v)) -> false() , plus(n, s(m)) -> s(plus(n, m)) , plus(n, 0()) -> n } Obligation: innermost runtime complexity Answer: MAYBE We replace rewrite rules by usable rules: Weak Usable Rules: { ge(u, 0()) -> true() , ge(s(u), s(v)) -> ge(u, v) , ge(0(), s(v)) -> false() , plus(n, s(m)) -> s(plus(n, m)) , plus(n, 0()) -> n } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { d^#(x, s(y), z) -> c_2(cond^#(ge(x, z), x, y, z), ge^#(x, z)) , cond^#(true(), x, y, z) -> c_3(d^#(x, s(y), plus(s(y), z)), plus^#(s(y), z)) , ge^#(s(u), s(v)) -> c_6(ge^#(u, v)) , plus^#(n, s(m)) -> c_8(plus^#(n, m)) } Weak Trs: { ge(u, 0()) -> true() , ge(s(u), s(v)) -> ge(u, v) , ge(0(), s(v)) -> false() , plus(n, s(m)) -> s(plus(n, m)) , plus(n, 0()) -> n } Obligation: innermost runtime complexity Answer: MAYBE The input cannot be shown compatible Arrrr..