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..