MAYBE
TRS:
 {          sieve(cons(X, Y)) -> cons(X, filter(X, sieve(Y))),
                      from(X) -> cons(X, from(s(X))),
                     primes() -> sieve(from(s(s(0())))),
             head(cons(X, Y)) -> X,
             tail(cons(X, Y)) -> Y,
             if(true(), X, Y) -> X,
            if(false(), X, Y) -> Y,
  filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y))))}
 DP:
  Strict:
   {          sieve#(cons(X, Y)) -> sieve#(Y),
              sieve#(cons(X, Y)) -> filter#(X, sieve(Y)),
                        from#(X) -> from#(s(X)),
                       primes#() -> sieve#(from(s(s(0())))),
                       primes#() -> from#(s(s(0()))),
    filter#(s(s(X)), cons(Y, Z)) -> sieve#(Y),
    filter#(s(s(X)), cons(Y, Z)) -> if#(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))),
    filter#(s(s(X)), cons(Y, Z)) -> filter#(X, sieve(Y)),
    filter#(s(s(X)), cons(Y, Z)) -> filter#(s(s(X)), Z)}
  Weak:
  {          sieve(cons(X, Y)) -> cons(X, filter(X, sieve(Y))),
                       from(X) -> cons(X, from(s(X))),
                      primes() -> sieve(from(s(s(0())))),
              head(cons(X, Y)) -> X,
              tail(cons(X, Y)) -> Y,
              if(true(), X, Y) -> X,
             if(false(), X, Y) -> Y,
   filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y))))}
  EDG:
   {(filter#(s(s(X)), cons(Y, Z)) -> sieve#(Y), sieve#(cons(X, Y)) -> filter#(X, sieve(Y)))
    (filter#(s(s(X)), cons(Y, Z)) -> sieve#(Y), sieve#(cons(X, Y)) -> sieve#(Y))
    (primes#() -> from#(s(s(0()))), from#(X) -> from#(s(X)))
    (from#(X) -> from#(s(X)), from#(X) -> from#(s(X)))
    (sieve#(cons(X, Y)) -> filter#(X, sieve(Y)), filter#(s(s(X)), cons(Y, Z)) -> filter#(s(s(X)), Z))
    (sieve#(cons(X, Y)) -> filter#(X, sieve(Y)), filter#(s(s(X)), cons(Y, Z)) -> filter#(X, sieve(Y)))
    (sieve#(cons(X, Y)) -> filter#(X, sieve(Y)), filter#(s(s(X)), cons(Y, Z)) -> if#(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))))
    (sieve#(cons(X, Y)) -> filter#(X, sieve(Y)), filter#(s(s(X)), cons(Y, Z)) -> sieve#(Y))
    (filter#(s(s(X)), cons(Y, Z)) -> filter#(X, sieve(Y)), filter#(s(s(X)), cons(Y, Z)) -> sieve#(Y))
    (filter#(s(s(X)), cons(Y, Z)) -> filter#(X, sieve(Y)), filter#(s(s(X)), cons(Y, Z)) -> if#(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))))
    (filter#(s(s(X)), cons(Y, Z)) -> filter#(X, sieve(Y)), filter#(s(s(X)), cons(Y, Z)) -> filter#(X, sieve(Y)))
    (filter#(s(s(X)), cons(Y, Z)) -> filter#(X, sieve(Y)), filter#(s(s(X)), cons(Y, Z)) -> filter#(s(s(X)), Z))
    (filter#(s(s(X)), cons(Y, Z)) -> filter#(s(s(X)), Z), filter#(s(s(X)), cons(Y, Z)) -> sieve#(Y))
    (filter#(s(s(X)), cons(Y, Z)) -> filter#(s(s(X)), Z), filter#(s(s(X)), cons(Y, Z)) -> if#(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))))
    (filter#(s(s(X)), cons(Y, Z)) -> filter#(s(s(X)), Z), filter#(s(s(X)), cons(Y, Z)) -> filter#(X, sieve(Y)))
    (filter#(s(s(X)), cons(Y, Z)) -> filter#(s(s(X)), Z), filter#(s(s(X)), cons(Y, Z)) -> filter#(s(s(X)), Z))
    (primes#() -> sieve#(from(s(s(0())))), sieve#(cons(X, Y)) -> sieve#(Y))
    (primes#() -> sieve#(from(s(s(0())))), sieve#(cons(X, Y)) -> filter#(X, sieve(Y)))
    (sieve#(cons(X, Y)) -> sieve#(Y), sieve#(cons(X, Y)) -> sieve#(Y))
    (sieve#(cons(X, Y)) -> sieve#(Y), sieve#(cons(X, Y)) -> filter#(X, sieve(Y)))}
   SCCS:
    Scc:
     {from#(X) -> from#(s(X))}
    Scc:
     {          sieve#(cons(X, Y)) -> sieve#(Y),
                sieve#(cons(X, Y)) -> filter#(X, sieve(Y)),
      filter#(s(s(X)), cons(Y, Z)) -> sieve#(Y),
      filter#(s(s(X)), cons(Y, Z)) -> filter#(X, sieve(Y)),
      filter#(s(s(X)), cons(Y, Z)) -> filter#(s(s(X)), Z)}
    SCC:
     Strict:
      {from#(X) -> from#(s(X))}
     Weak:
     {          sieve(cons(X, Y)) -> cons(X, filter(X, sieve(Y))),
                          from(X) -> cons(X, from(s(X))),
                         primes() -> sieve(from(s(s(0())))),
                 head(cons(X, Y)) -> X,
                 tail(cons(X, Y)) -> Y,
                 if(true(), X, Y) -> X,
                if(false(), X, Y) -> Y,
      filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y))))}
     Fail
    SCC:
     Strict:
      {          sieve#(cons(X, Y)) -> sieve#(Y),
                 sieve#(cons(X, Y)) -> filter#(X, sieve(Y)),
       filter#(s(s(X)), cons(Y, Z)) -> sieve#(Y),
       filter#(s(s(X)), cons(Y, Z)) -> filter#(X, sieve(Y)),
       filter#(s(s(X)), cons(Y, Z)) -> filter#(s(s(X)), Z)}
     Weak:
     {          sieve(cons(X, Y)) -> cons(X, filter(X, sieve(Y))),
                          from(X) -> cons(X, from(s(X))),
                         primes() -> sieve(from(s(s(0())))),
                 head(cons(X, Y)) -> X,
                 tail(cons(X, Y)) -> Y,
                 if(true(), X, Y) -> X,
                if(false(), X, Y) -> Y,
      filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y))))}
     Fail