MAYBE

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict Trs:
  { terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
  , terms(X) -> n__terms(X)
  , sqr(s(X)) -> s(add(sqr(X), dbl(X)))
  , sqr(0()) -> 0()
  , add(s(X), Y) -> s(add(X, Y))
  , add(0(), X) -> X
  , dbl(s(X)) -> s(s(dbl(X)))
  , dbl(0()) -> 0()
  , first(X1, X2) -> n__first(X1, X2)
  , first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
  , first(0(), X) -> nil()
  , activate(X) -> X
  , activate(n__terms(X)) -> terms(X)
  , activate(n__first(X1, X2)) -> first(X1, X2) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

We add following dependency tuples:

Strict DPs:
  { terms^#(N) -> c_1(sqr^#(N))
  , terms^#(X) -> c_2()
  , sqr^#(s(X)) -> c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X))
  , sqr^#(0()) -> c_4()
  , add^#(s(X), Y) -> c_5(add^#(X, Y))
  , add^#(0(), X) -> c_6()
  , dbl^#(s(X)) -> c_7(dbl^#(X))
  , dbl^#(0()) -> c_8()
  , first^#(X1, X2) -> c_9()
  , first^#(s(X), cons(Y, Z)) -> c_10(activate^#(Z))
  , first^#(0(), X) -> c_11()
  , activate^#(X) -> c_12()
  , activate^#(n__terms(X)) -> c_13(terms^#(X))
  , activate^#(n__first(X1, X2)) -> c_14(first^#(X1, X2)) }

and mark the set of starting terms.

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict DPs:
  { terms^#(N) -> c_1(sqr^#(N))
  , terms^#(X) -> c_2()
  , sqr^#(s(X)) -> c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X))
  , sqr^#(0()) -> c_4()
  , add^#(s(X), Y) -> c_5(add^#(X, Y))
  , add^#(0(), X) -> c_6()
  , dbl^#(s(X)) -> c_7(dbl^#(X))
  , dbl^#(0()) -> c_8()
  , first^#(X1, X2) -> c_9()
  , first^#(s(X), cons(Y, Z)) -> c_10(activate^#(Z))
  , first^#(0(), X) -> c_11()
  , activate^#(X) -> c_12()
  , activate^#(n__terms(X)) -> c_13(terms^#(X))
  , activate^#(n__first(X1, X2)) -> c_14(first^#(X1, X2)) }
Weak Trs:
  { terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
  , terms(X) -> n__terms(X)
  , sqr(s(X)) -> s(add(sqr(X), dbl(X)))
  , sqr(0()) -> 0()
  , add(s(X), Y) -> s(add(X, Y))
  , add(0(), X) -> X
  , dbl(s(X)) -> s(s(dbl(X)))
  , dbl(0()) -> 0()
  , first(X1, X2) -> n__first(X1, X2)
  , first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
  , first(0(), X) -> nil()
  , activate(X) -> X
  , activate(n__terms(X)) -> terms(X)
  , activate(n__first(X1, X2)) -> first(X1, X2) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

We estimate the number of application of {2,4,6,8,9,11,12} by
applications of Pre({2,4,6,8,9,11,12}) = {1,3,5,7,10,13,14}. Here
rules are labeled as follows:

  DPs:
    { 1: terms^#(N) -> c_1(sqr^#(N))
    , 2: terms^#(X) -> c_2()
    , 3: sqr^#(s(X)) -> c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X))
    , 4: sqr^#(0()) -> c_4()
    , 5: add^#(s(X), Y) -> c_5(add^#(X, Y))
    , 6: add^#(0(), X) -> c_6()
    , 7: dbl^#(s(X)) -> c_7(dbl^#(X))
    , 8: dbl^#(0()) -> c_8()
    , 9: first^#(X1, X2) -> c_9()
    , 10: first^#(s(X), cons(Y, Z)) -> c_10(activate^#(Z))
    , 11: first^#(0(), X) -> c_11()
    , 12: activate^#(X) -> c_12()
    , 13: activate^#(n__terms(X)) -> c_13(terms^#(X))
    , 14: activate^#(n__first(X1, X2)) -> c_14(first^#(X1, X2)) }

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict DPs:
  { terms^#(N) -> c_1(sqr^#(N))
  , sqr^#(s(X)) -> c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X))
  , add^#(s(X), Y) -> c_5(add^#(X, Y))
  , dbl^#(s(X)) -> c_7(dbl^#(X))
  , first^#(s(X), cons(Y, Z)) -> c_10(activate^#(Z))
  , activate^#(n__terms(X)) -> c_13(terms^#(X))
  , activate^#(n__first(X1, X2)) -> c_14(first^#(X1, X2)) }
Weak DPs:
  { terms^#(X) -> c_2()
  , sqr^#(0()) -> c_4()
  , add^#(0(), X) -> c_6()
  , dbl^#(0()) -> c_8()
  , first^#(X1, X2) -> c_9()
  , first^#(0(), X) -> c_11()
  , activate^#(X) -> c_12() }
Weak Trs:
  { terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
  , terms(X) -> n__terms(X)
  , sqr(s(X)) -> s(add(sqr(X), dbl(X)))
  , sqr(0()) -> 0()
  , add(s(X), Y) -> s(add(X, Y))
  , add(0(), X) -> X
  , dbl(s(X)) -> s(s(dbl(X)))
  , dbl(0()) -> 0()
  , first(X1, X2) -> n__first(X1, X2)
  , first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
  , first(0(), X) -> nil()
  , activate(X) -> X
  , activate(n__terms(X)) -> terms(X)
  , activate(n__first(X1, X2)) -> first(X1, X2) }
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.

{ terms^#(X) -> c_2()
, sqr^#(0()) -> c_4()
, add^#(0(), X) -> c_6()
, dbl^#(0()) -> c_8()
, first^#(X1, X2) -> c_9()
, first^#(0(), X) -> c_11()
, activate^#(X) -> c_12() }

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict DPs:
  { terms^#(N) -> c_1(sqr^#(N))
  , sqr^#(s(X)) -> c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X))
  , add^#(s(X), Y) -> c_5(add^#(X, Y))
  , dbl^#(s(X)) -> c_7(dbl^#(X))
  , first^#(s(X), cons(Y, Z)) -> c_10(activate^#(Z))
  , activate^#(n__terms(X)) -> c_13(terms^#(X))
  , activate^#(n__first(X1, X2)) -> c_14(first^#(X1, X2)) }
Weak Trs:
  { terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
  , terms(X) -> n__terms(X)
  , sqr(s(X)) -> s(add(sqr(X), dbl(X)))
  , sqr(0()) -> 0()
  , add(s(X), Y) -> s(add(X, Y))
  , add(0(), X) -> X
  , dbl(s(X)) -> s(s(dbl(X)))
  , dbl(0()) -> 0()
  , first(X1, X2) -> n__first(X1, X2)
  , first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
  , first(0(), X) -> nil()
  , activate(X) -> X
  , activate(n__terms(X)) -> terms(X)
  , activate(n__first(X1, X2)) -> first(X1, X2) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

We replace rewrite rules by usable rules:

  Weak Usable Rules:
    { sqr(s(X)) -> s(add(sqr(X), dbl(X)))
    , sqr(0()) -> 0()
    , add(s(X), Y) -> s(add(X, Y))
    , add(0(), X) -> X
    , dbl(s(X)) -> s(s(dbl(X)))
    , dbl(0()) -> 0() }

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict DPs:
  { terms^#(N) -> c_1(sqr^#(N))
  , sqr^#(s(X)) -> c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X))
  , add^#(s(X), Y) -> c_5(add^#(X, Y))
  , dbl^#(s(X)) -> c_7(dbl^#(X))
  , first^#(s(X), cons(Y, Z)) -> c_10(activate^#(Z))
  , activate^#(n__terms(X)) -> c_13(terms^#(X))
  , activate^#(n__first(X1, X2)) -> c_14(first^#(X1, X2)) }
Weak Trs:
  { sqr(s(X)) -> s(add(sqr(X), dbl(X)))
  , sqr(0()) -> 0()
  , add(s(X), Y) -> s(add(X, Y))
  , add(0(), X) -> X
  , dbl(s(X)) -> s(s(dbl(X)))
  , dbl(0()) -> 0() }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

The input cannot be shown compatible

Arrrr..