MAYBE

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

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

We add following dependency tuples:

Strict DPs:
  { terms^#(N) -> c_1(sqr^#(N))
  , sqr^#(0()) -> c_2()
  , sqr^#(s(X)) -> c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X))
  , add^#(0(), X) -> c_4()
  , add^#(s(X), Y) -> c_5(add^#(X, Y))
  , dbl^#(0()) -> c_6()
  , dbl^#(s(X)) -> c_7(dbl^#(X))
  , first^#(0(), X) -> c_8()
  , first^#(s(X), cons(Y)) -> c_9() }

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))
  , sqr^#(0()) -> c_2()
  , sqr^#(s(X)) -> c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X))
  , add^#(0(), X) -> c_4()
  , add^#(s(X), Y) -> c_5(add^#(X, Y))
  , dbl^#(0()) -> c_6()
  , dbl^#(s(X)) -> c_7(dbl^#(X))
  , first^#(0(), X) -> c_8()
  , first^#(s(X), cons(Y)) -> c_9() }
Weak Trs:
  { terms(N) -> cons(recip(sqr(N)))
  , sqr(0()) -> 0()
  , sqr(s(X)) -> s(add(sqr(X), dbl(X)))
  , add(0(), X) -> X
  , add(s(X), Y) -> s(add(X, Y))
  , dbl(0()) -> 0()
  , dbl(s(X)) -> s(s(dbl(X)))
  , first(0(), X) -> nil()
  , first(s(X), cons(Y)) -> cons(Y) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

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

  DPs:
    { 1: terms^#(N) -> c_1(sqr^#(N))
    , 2: sqr^#(0()) -> c_2()
    , 3: sqr^#(s(X)) -> c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X))
    , 4: add^#(0(), X) -> c_4()
    , 5: add^#(s(X), Y) -> c_5(add^#(X, Y))
    , 6: dbl^#(0()) -> c_6()
    , 7: dbl^#(s(X)) -> c_7(dbl^#(X))
    , 8: first^#(0(), X) -> c_8()
    , 9: first^#(s(X), cons(Y)) -> c_9() }

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)) }
Weak DPs:
  { sqr^#(0()) -> c_2()
  , add^#(0(), X) -> c_4()
  , dbl^#(0()) -> c_6()
  , first^#(0(), X) -> c_8()
  , first^#(s(X), cons(Y)) -> c_9() }
Weak Trs:
  { terms(N) -> cons(recip(sqr(N)))
  , sqr(0()) -> 0()
  , sqr(s(X)) -> s(add(sqr(X), dbl(X)))
  , add(0(), X) -> X
  , add(s(X), Y) -> s(add(X, Y))
  , dbl(0()) -> 0()
  , dbl(s(X)) -> s(s(dbl(X)))
  , first(0(), X) -> nil()
  , first(s(X), cons(Y)) -> cons(Y) }
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.

{ sqr^#(0()) -> c_2()
, add^#(0(), X) -> c_4()
, dbl^#(0()) -> c_6()
, first^#(0(), X) -> c_8()
, first^#(s(X), cons(Y)) -> c_9() }

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)) }
Weak Trs:
  { terms(N) -> cons(recip(sqr(N)))
  , sqr(0()) -> 0()
  , sqr(s(X)) -> s(add(sqr(X), dbl(X)))
  , add(0(), X) -> X
  , add(s(X), Y) -> s(add(X, Y))
  , dbl(0()) -> 0()
  , dbl(s(X)) -> s(s(dbl(X)))
  , first(0(), X) -> nil()
  , first(s(X), cons(Y)) -> cons(Y) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

Consider the dependency graph

  1: terms^#(N) -> c_1(sqr^#(N))
     -->_1 sqr^#(s(X)) ->
           c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X)) :2
  
  2: sqr^#(s(X)) -> c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X))
     -->_3 dbl^#(s(X)) -> c_7(dbl^#(X)) :4
     -->_1 add^#(s(X), Y) -> c_5(add^#(X, Y)) :3
     -->_2 sqr^#(s(X)) ->
           c_3(add^#(sqr(X), dbl(X)), sqr^#(X), dbl^#(X)) :2
  
  3: add^#(s(X), Y) -> c_5(add^#(X, Y))
     -->_1 add^#(s(X), Y) -> c_5(add^#(X, Y)) :3
  
  4: dbl^#(s(X)) -> c_7(dbl^#(X))
     -->_1 dbl^#(s(X)) -> c_7(dbl^#(X)) :4
  

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

  { terms^#(N) -> c_1(sqr^#(N)) }


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

Strict DPs:
  { 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)) }
Weak Trs:
  { terms(N) -> cons(recip(sqr(N)))
  , sqr(0()) -> 0()
  , sqr(s(X)) -> s(add(sqr(X), dbl(X)))
  , add(0(), X) -> X
  , add(s(X), Y) -> s(add(X, Y))
  , dbl(0()) -> 0()
  , dbl(s(X)) -> s(s(dbl(X)))
  , first(0(), X) -> nil()
  , first(s(X), cons(Y)) -> cons(Y) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

We replace rewrite rules by usable rules:

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

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

Strict DPs:
  { 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)) }
Weak Trs:
  { sqr(0()) -> 0()
  , sqr(s(X)) -> s(add(sqr(X), dbl(X)))
  , add(0(), X) -> X
  , add(s(X), Y) -> s(add(X, Y))
  , dbl(0()) -> 0()
  , dbl(s(X)) -> s(s(dbl(X))) }
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..