MAYBE

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

Strict Trs:
  { from(X) -> cons(X, from(s(X)))
  , 2ndspos(s(N), cons(X, cons(Y, Z))) ->
    rcons(posrecip(Y), 2ndsneg(N, Z))
  , 2ndspos(0(), Z) -> rnil()
  , 2ndsneg(s(N), cons(X, cons(Y, Z))) ->
    rcons(negrecip(Y), 2ndspos(N, Z))
  , 2ndsneg(0(), Z) -> rnil()
  , pi(X) -> 2ndspos(X, from(0()))
  , plus(s(X), Y) -> s(plus(X, Y))
  , plus(0(), Y) -> Y
  , times(s(X), Y) -> plus(Y, times(X, Y))
  , times(0(), Y) -> 0()
  , square(X) -> times(X, X) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

We add following dependency tuples:

Strict DPs:
  { from^#(X) -> c_1(from^#(s(X)))
  , 2ndspos^#(s(N), cons(X, cons(Y, Z))) -> c_2(2ndsneg^#(N, Z))
  , 2ndspos^#(0(), Z) -> c_3()
  , 2ndsneg^#(s(N), cons(X, cons(Y, Z))) -> c_4(2ndspos^#(N, Z))
  , 2ndsneg^#(0(), Z) -> c_5()
  , pi^#(X) -> c_6(2ndspos^#(X, from(0())), from^#(0()))
  , plus^#(s(X), Y) -> c_7(plus^#(X, Y))
  , plus^#(0(), Y) -> c_8()
  , times^#(s(X), Y) -> c_9(plus^#(Y, times(X, Y)), times^#(X, Y))
  , times^#(0(), Y) -> c_10()
  , square^#(X) -> c_11(times^#(X, X)) }

and mark the set of starting terms.

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

Strict DPs:
  { from^#(X) -> c_1(from^#(s(X)))
  , 2ndspos^#(s(N), cons(X, cons(Y, Z))) -> c_2(2ndsneg^#(N, Z))
  , 2ndspos^#(0(), Z) -> c_3()
  , 2ndsneg^#(s(N), cons(X, cons(Y, Z))) -> c_4(2ndspos^#(N, Z))
  , 2ndsneg^#(0(), Z) -> c_5()
  , pi^#(X) -> c_6(2ndspos^#(X, from(0())), from^#(0()))
  , plus^#(s(X), Y) -> c_7(plus^#(X, Y))
  , plus^#(0(), Y) -> c_8()
  , times^#(s(X), Y) -> c_9(plus^#(Y, times(X, Y)), times^#(X, Y))
  , times^#(0(), Y) -> c_10()
  , square^#(X) -> c_11(times^#(X, X)) }
Weak Trs:
  { from(X) -> cons(X, from(s(X)))
  , 2ndspos(s(N), cons(X, cons(Y, Z))) ->
    rcons(posrecip(Y), 2ndsneg(N, Z))
  , 2ndspos(0(), Z) -> rnil()
  , 2ndsneg(s(N), cons(X, cons(Y, Z))) ->
    rcons(negrecip(Y), 2ndspos(N, Z))
  , 2ndsneg(0(), Z) -> rnil()
  , pi(X) -> 2ndspos(X, from(0()))
  , plus(s(X), Y) -> s(plus(X, Y))
  , plus(0(), Y) -> Y
  , times(s(X), Y) -> plus(Y, times(X, Y))
  , times(0(), Y) -> 0()
  , square(X) -> times(X, X) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

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

  DPs:
    { 1: from^#(X) -> c_1(from^#(s(X)))
    , 2: 2ndspos^#(s(N), cons(X, cons(Y, Z))) -> c_2(2ndsneg^#(N, Z))
    , 3: 2ndspos^#(0(), Z) -> c_3()
    , 4: 2ndsneg^#(s(N), cons(X, cons(Y, Z))) -> c_4(2ndspos^#(N, Z))
    , 5: 2ndsneg^#(0(), Z) -> c_5()
    , 6: pi^#(X) -> c_6(2ndspos^#(X, from(0())), from^#(0()))
    , 7: plus^#(s(X), Y) -> c_7(plus^#(X, Y))
    , 8: plus^#(0(), Y) -> c_8()
    , 9: times^#(s(X), Y) -> c_9(plus^#(Y, times(X, Y)), times^#(X, Y))
    , 10: times^#(0(), Y) -> c_10()
    , 11: square^#(X) -> c_11(times^#(X, X)) }

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

Strict DPs:
  { from^#(X) -> c_1(from^#(s(X)))
  , 2ndspos^#(s(N), cons(X, cons(Y, Z))) -> c_2(2ndsneg^#(N, Z))
  , 2ndsneg^#(s(N), cons(X, cons(Y, Z))) -> c_4(2ndspos^#(N, Z))
  , pi^#(X) -> c_6(2ndspos^#(X, from(0())), from^#(0()))
  , plus^#(s(X), Y) -> c_7(plus^#(X, Y))
  , times^#(s(X), Y) -> c_9(plus^#(Y, times(X, Y)), times^#(X, Y))
  , square^#(X) -> c_11(times^#(X, X)) }
Weak DPs:
  { 2ndspos^#(0(), Z) -> c_3()
  , 2ndsneg^#(0(), Z) -> c_5()
  , plus^#(0(), Y) -> c_8()
  , times^#(0(), Y) -> c_10() }
Weak Trs:
  { from(X) -> cons(X, from(s(X)))
  , 2ndspos(s(N), cons(X, cons(Y, Z))) ->
    rcons(posrecip(Y), 2ndsneg(N, Z))
  , 2ndspos(0(), Z) -> rnil()
  , 2ndsneg(s(N), cons(X, cons(Y, Z))) ->
    rcons(negrecip(Y), 2ndspos(N, Z))
  , 2ndsneg(0(), Z) -> rnil()
  , pi(X) -> 2ndspos(X, from(0()))
  , plus(s(X), Y) -> s(plus(X, Y))
  , plus(0(), Y) -> Y
  , times(s(X), Y) -> plus(Y, times(X, Y))
  , times(0(), Y) -> 0()
  , square(X) -> times(X, X) }
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.

{ 2ndspos^#(0(), Z) -> c_3()
, 2ndsneg^#(0(), Z) -> c_5()
, plus^#(0(), Y) -> c_8()
, times^#(0(), Y) -> c_10() }

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

Strict DPs:
  { from^#(X) -> c_1(from^#(s(X)))
  , 2ndspos^#(s(N), cons(X, cons(Y, Z))) -> c_2(2ndsneg^#(N, Z))
  , 2ndsneg^#(s(N), cons(X, cons(Y, Z))) -> c_4(2ndspos^#(N, Z))
  , pi^#(X) -> c_6(2ndspos^#(X, from(0())), from^#(0()))
  , plus^#(s(X), Y) -> c_7(plus^#(X, Y))
  , times^#(s(X), Y) -> c_9(plus^#(Y, times(X, Y)), times^#(X, Y))
  , square^#(X) -> c_11(times^#(X, X)) }
Weak Trs:
  { from(X) -> cons(X, from(s(X)))
  , 2ndspos(s(N), cons(X, cons(Y, Z))) ->
    rcons(posrecip(Y), 2ndsneg(N, Z))
  , 2ndspos(0(), Z) -> rnil()
  , 2ndsneg(s(N), cons(X, cons(Y, Z))) ->
    rcons(negrecip(Y), 2ndspos(N, Z))
  , 2ndsneg(0(), Z) -> rnil()
  , pi(X) -> 2ndspos(X, from(0()))
  , plus(s(X), Y) -> s(plus(X, Y))
  , plus(0(), Y) -> Y
  , times(s(X), Y) -> plus(Y, times(X, Y))
  , times(0(), Y) -> 0()
  , square(X) -> times(X, X) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

Consider the dependency graph

  1: from^#(X) -> c_1(from^#(s(X)))
     -->_1 from^#(X) -> c_1(from^#(s(X))) :1
  
  2: 2ndspos^#(s(N), cons(X, cons(Y, Z))) -> c_2(2ndsneg^#(N, Z))
     -->_1 2ndsneg^#(s(N), cons(X, cons(Y, Z))) ->
           c_4(2ndspos^#(N, Z)) :3
  
  3: 2ndsneg^#(s(N), cons(X, cons(Y, Z))) -> c_4(2ndspos^#(N, Z))
     -->_1 2ndspos^#(s(N), cons(X, cons(Y, Z))) ->
           c_2(2ndsneg^#(N, Z)) :2
  
  4: pi^#(X) -> c_6(2ndspos^#(X, from(0())), from^#(0()))
     -->_1 2ndspos^#(s(N), cons(X, cons(Y, Z))) ->
           c_2(2ndsneg^#(N, Z)) :2
     -->_2 from^#(X) -> c_1(from^#(s(X))) :1
  
  5: plus^#(s(X), Y) -> c_7(plus^#(X, Y))
     -->_1 plus^#(s(X), Y) -> c_7(plus^#(X, Y)) :5
  
  6: times^#(s(X), Y) -> c_9(plus^#(Y, times(X, Y)), times^#(X, Y))
     -->_2 times^#(s(X), Y) ->
           c_9(plus^#(Y, times(X, Y)), times^#(X, Y)) :6
     -->_1 plus^#(s(X), Y) -> c_7(plus^#(X, Y)) :5
  
  7: square^#(X) -> c_11(times^#(X, X))
     -->_1 times^#(s(X), Y) ->
           c_9(plus^#(Y, times(X, Y)), times^#(X, Y)) :6
  

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

  { square^#(X) -> c_11(times^#(X, X)) }


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

Strict DPs:
  { from^#(X) -> c_1(from^#(s(X)))
  , 2ndspos^#(s(N), cons(X, cons(Y, Z))) -> c_2(2ndsneg^#(N, Z))
  , 2ndsneg^#(s(N), cons(X, cons(Y, Z))) -> c_4(2ndspos^#(N, Z))
  , pi^#(X) -> c_6(2ndspos^#(X, from(0())), from^#(0()))
  , plus^#(s(X), Y) -> c_7(plus^#(X, Y))
  , times^#(s(X), Y) -> c_9(plus^#(Y, times(X, Y)), times^#(X, Y)) }
Weak Trs:
  { from(X) -> cons(X, from(s(X)))
  , 2ndspos(s(N), cons(X, cons(Y, Z))) ->
    rcons(posrecip(Y), 2ndsneg(N, Z))
  , 2ndspos(0(), Z) -> rnil()
  , 2ndsneg(s(N), cons(X, cons(Y, Z))) ->
    rcons(negrecip(Y), 2ndspos(N, Z))
  , 2ndsneg(0(), Z) -> rnil()
  , pi(X) -> 2ndspos(X, from(0()))
  , plus(s(X), Y) -> s(plus(X, Y))
  , plus(0(), Y) -> Y
  , times(s(X), Y) -> plus(Y, times(X, Y))
  , times(0(), Y) -> 0()
  , square(X) -> times(X, X) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

We replace rewrite rules by usable rules:

  Weak Usable Rules:
    { from(X) -> cons(X, from(s(X)))
    , plus(s(X), Y) -> s(plus(X, Y))
    , plus(0(), Y) -> Y
    , times(s(X), Y) -> plus(Y, times(X, Y))
    , times(0(), Y) -> 0() }

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

Strict DPs:
  { from^#(X) -> c_1(from^#(s(X)))
  , 2ndspos^#(s(N), cons(X, cons(Y, Z))) -> c_2(2ndsneg^#(N, Z))
  , 2ndsneg^#(s(N), cons(X, cons(Y, Z))) -> c_4(2ndspos^#(N, Z))
  , pi^#(X) -> c_6(2ndspos^#(X, from(0())), from^#(0()))
  , plus^#(s(X), Y) -> c_7(plus^#(X, Y))
  , times^#(s(X), Y) -> c_9(plus^#(Y, times(X, Y)), times^#(X, Y)) }
Weak Trs:
  { from(X) -> cons(X, from(s(X)))
  , plus(s(X), Y) -> s(plus(X, Y))
  , plus(0(), Y) -> Y
  , times(s(X), Y) -> plus(Y, times(X, Y))
  , times(0(), Y) -> 0() }
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..