MAYBE
* Step 1: DependencyPairs MAYBE
    + Considered Problem:
        - Strict TRS:
            filter(cons(X,Y),0(),M) -> cons(0(),filter(Y,M,M))
            filter(cons(X,Y),s(N),M) -> cons(X,filter(Y,N,M))
            nats(N) -> cons(N,nats(s(N)))
            sieve(cons(0(),Y)) -> cons(0(),sieve(Y))
            sieve(cons(s(N),Y)) -> cons(s(N),sieve(filter(Y,N,N)))
            zprimes() -> sieve(nats(s(s(0()))))
        - Signature:
            {filter/3,nats/1,sieve/1,zprimes/0} / {0/0,cons/2,s/1}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {filter,nats,sieve,zprimes} and constructors {0,cons,s}
    + Applied Processor:
        DependencyPairs {dpKind_ = DT}
    + Details:
        We add the following dependency tuples:
        
        Strict DPs
          filter#(cons(X,Y),0(),M) -> c_1(filter#(Y,M,M))
          filter#(cons(X,Y),s(N),M) -> c_2(filter#(Y,N,M))
          nats#(N) -> c_3(nats#(s(N)))
          sieve#(cons(0(),Y)) -> c_4(sieve#(Y))
          sieve#(cons(s(N),Y)) -> c_5(sieve#(filter(Y,N,N)),filter#(Y,N,N))
          zprimes#() -> c_6(sieve#(nats(s(s(0())))),nats#(s(s(0()))))
        Weak DPs
          
        
        and mark the set of starting terms.
* Step 2: UsableRules MAYBE
    + Considered Problem:
        - Strict DPs:
            filter#(cons(X,Y),0(),M) -> c_1(filter#(Y,M,M))
            filter#(cons(X,Y),s(N),M) -> c_2(filter#(Y,N,M))
            nats#(N) -> c_3(nats#(s(N)))
            sieve#(cons(0(),Y)) -> c_4(sieve#(Y))
            sieve#(cons(s(N),Y)) -> c_5(sieve#(filter(Y,N,N)),filter#(Y,N,N))
            zprimes#() -> c_6(sieve#(nats(s(s(0())))),nats#(s(s(0()))))
        - Weak TRS:
            filter(cons(X,Y),0(),M) -> cons(0(),filter(Y,M,M))
            filter(cons(X,Y),s(N),M) -> cons(X,filter(Y,N,M))
            nats(N) -> cons(N,nats(s(N)))
            sieve(cons(0(),Y)) -> cons(0(),sieve(Y))
            sieve(cons(s(N),Y)) -> cons(s(N),sieve(filter(Y,N,N)))
            zprimes() -> sieve(nats(s(s(0()))))
        - Signature:
            {filter/3,nats/1,sieve/1,zprimes/0,filter#/3,nats#/1,sieve#/1,zprimes#/0} / {0/0,cons/2,s/1,c_1/1,c_2/1
            ,c_3/1,c_4/1,c_5/2,c_6/2}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {filter#,nats#,sieve#,zprimes#} and constructors {0,cons
            ,s}
    + Applied Processor:
        UsableRules
    + Details:
        We replace rewrite rules by usable rules:
          filter(cons(X,Y),0(),M) -> cons(0(),filter(Y,M,M))
          filter(cons(X,Y),s(N),M) -> cons(X,filter(Y,N,M))
          nats(N) -> cons(N,nats(s(N)))
          filter#(cons(X,Y),0(),M) -> c_1(filter#(Y,M,M))
          filter#(cons(X,Y),s(N),M) -> c_2(filter#(Y,N,M))
          nats#(N) -> c_3(nats#(s(N)))
          sieve#(cons(0(),Y)) -> c_4(sieve#(Y))
          sieve#(cons(s(N),Y)) -> c_5(sieve#(filter(Y,N,N)),filter#(Y,N,N))
          zprimes#() -> c_6(sieve#(nats(s(s(0())))),nats#(s(s(0()))))
* Step 3: NaturalMI MAYBE
    + Considered Problem:
        - Strict DPs:
            filter#(cons(X,Y),0(),M) -> c_1(filter#(Y,M,M))
            filter#(cons(X,Y),s(N),M) -> c_2(filter#(Y,N,M))
            nats#(N) -> c_3(nats#(s(N)))
            sieve#(cons(0(),Y)) -> c_4(sieve#(Y))
            sieve#(cons(s(N),Y)) -> c_5(sieve#(filter(Y,N,N)),filter#(Y,N,N))
            zprimes#() -> c_6(sieve#(nats(s(s(0())))),nats#(s(s(0()))))
        - Weak TRS:
            filter(cons(X,Y),0(),M) -> cons(0(),filter(Y,M,M))
            filter(cons(X,Y),s(N),M) -> cons(X,filter(Y,N,M))
            nats(N) -> cons(N,nats(s(N)))
        - Signature:
            {filter/3,nats/1,sieve/1,zprimes/0,filter#/3,nats#/1,sieve#/1,zprimes#/0} / {0/0,cons/2,s/1,c_1/1,c_2/1
            ,c_3/1,c_4/1,c_5/2,c_6/2}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {filter#,nats#,sieve#,zprimes#} and constructors {0,cons
            ,s}
    + Applied Processor:
        NaturalMI {miDimension = 1, miDegree = 0, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any strict-rules}
    + Details:
        We apply a matrix interpretation of kind constructor based matrix interpretation (containing no more than 0 non-zero interpretation-entries in the diagonal of the component-wise maxima):
        The following argument positions are considered usable:
          uargs(c_1) = {1},
          uargs(c_2) = {1},
          uargs(c_3) = {1},
          uargs(c_4) = {1},
          uargs(c_5) = {1,2},
          uargs(c_6) = {1,2}
        
        Following symbols are considered usable:
          {filter#,nats#,sieve#,zprimes#}
        TcT has computed the following interpretation:
                 p(0) = [1]                  
              p(cons) = [0]                  
            p(filter) = [8] x2 + [0]         
              p(nats) = [0]                  
                 p(s) = [0]                  
             p(sieve) = [0]                  
           p(zprimes) = [0]                  
           p(filter#) = [0]                  
             p(nats#) = [3]                  
            p(sieve#) = [0]                  
          p(zprimes#) = [15]                 
               p(c_1) = [1] x1 + [0]         
               p(c_2) = [4] x1 + [0]         
               p(c_3) = [1] x1 + [0]         
               p(c_4) = [1] x1 + [0]         
               p(c_5) = [1] x1 + [8] x2 + [0]
               p(c_6) = [8] x1 + [1] x2 + [8]
        
        Following rules are strictly oriented:
        zprimes#() = [15]                                         
                   > [11]                                         
                   = c_6(sieve#(nats(s(s(0())))),nats#(s(s(0()))))
        
        
        Following rules are (at-least) weakly oriented:
         filter#(cons(X,Y),0(),M) =  [0]                                      
                                  >= [0]                                      
                                  =  c_1(filter#(Y,M,M))                      
        
        filter#(cons(X,Y),s(N),M) =  [0]                                      
                                  >= [0]                                      
                                  =  c_2(filter#(Y,N,M))                      
        
                         nats#(N) =  [3]                                      
                                  >= [3]                                      
                                  =  c_3(nats#(s(N)))                         
        
              sieve#(cons(0(),Y)) =  [0]                                      
                                  >= [0]                                      
                                  =  c_4(sieve#(Y))                           
        
             sieve#(cons(s(N),Y)) =  [0]                                      
                                  >= [0]                                      
                                  =  c_5(sieve#(filter(Y,N,N)),filter#(Y,N,N))
        
* Step 4: Failure MAYBE
  + Considered Problem:
      - Strict DPs:
          filter#(cons(X,Y),0(),M) -> c_1(filter#(Y,M,M))
          filter#(cons(X,Y),s(N),M) -> c_2(filter#(Y,N,M))
          nats#(N) -> c_3(nats#(s(N)))
          sieve#(cons(0(),Y)) -> c_4(sieve#(Y))
          sieve#(cons(s(N),Y)) -> c_5(sieve#(filter(Y,N,N)),filter#(Y,N,N))
      - Weak DPs:
          zprimes#() -> c_6(sieve#(nats(s(s(0())))),nats#(s(s(0()))))
      - Weak TRS:
          filter(cons(X,Y),0(),M) -> cons(0(),filter(Y,M,M))
          filter(cons(X,Y),s(N),M) -> cons(X,filter(Y,N,M))
          nats(N) -> cons(N,nats(s(N)))
      - Signature:
          {filter/3,nats/1,sieve/1,zprimes/0,filter#/3,nats#/1,sieve#/1,zprimes#/0} / {0/0,cons/2,s/1,c_1/1,c_2/1
          ,c_3/1,c_4/1,c_5/2,c_6/2}
      - Obligation:
          innermost runtime complexity wrt. defined symbols {filter#,nats#,sieve#,zprimes#} and constructors {0,cons
          ,s}
  + Applied Processor:
      EmptyProcessor
  + Details:
      The problem is still open.
MAYBE