YES
TRS:
 {    fib(0()) -> 0(),
   fib(s(0())) -> s(0()),
  fib(s(s(x))) -> +(fib(s(x)), fib(x)),
     +(x, 0()) -> x,
    +(x, s(y)) -> s(+(x, y))}
 DP:
  Strict:
   {fib#(s(s(x))) -> fib#(x),
    fib#(s(s(x))) -> fib#(s(x)),
    fib#(s(s(x))) -> +#(fib(s(x)), fib(x)),
      +#(x, s(y)) -> +#(x, y)}
  Weak:
  {    fib(0()) -> 0(),
    fib(s(0())) -> s(0()),
   fib(s(s(x))) -> +(fib(s(x)), fib(x)),
      +(x, 0()) -> x,
     +(x, s(y)) -> s(+(x, y))}
  EDG:
   {(fib#(s(s(x))) -> +#(fib(s(x)), fib(x)), +#(x, s(y)) -> +#(x, y))
    (+#(x, s(y)) -> +#(x, y), +#(x, s(y)) -> +#(x, y))
    (fib#(s(s(x))) -> fib#(s(x)), fib#(s(s(x))) -> fib#(x))
    (fib#(s(s(x))) -> fib#(s(x)), fib#(s(s(x))) -> fib#(s(x)))
    (fib#(s(s(x))) -> fib#(s(x)), fib#(s(s(x))) -> +#(fib(s(x)), fib(x)))
    (fib#(s(s(x))) -> fib#(x), fib#(s(s(x))) -> fib#(x))
    (fib#(s(s(x))) -> fib#(x), fib#(s(s(x))) -> fib#(s(x)))
    (fib#(s(s(x))) -> fib#(x), fib#(s(s(x))) -> +#(fib(s(x)), fib(x)))}
   SCCS:
    Scc:
     {+#(x, s(y)) -> +#(x, y)}
    Scc:
     {fib#(s(s(x))) -> fib#(x),
      fib#(s(s(x))) -> fib#(s(x))}
    SCC:
     Strict:
      {+#(x, s(y)) -> +#(x, y)}
     Weak:
     {    fib(0()) -> 0(),
       fib(s(0())) -> s(0()),
      fib(s(s(x))) -> +(fib(s(x)), fib(x)),
         +(x, 0()) -> x,
        +(x, s(y)) -> s(+(x, y))}
     SPSC:
      Simple Projection:
       pi(+#) = 1
      Strict:
       {}
      Qed
    SCC:
     Strict:
      {fib#(s(s(x))) -> fib#(x),
       fib#(s(s(x))) -> fib#(s(x))}
     Weak:
     {    fib(0()) -> 0(),
       fib(s(0())) -> s(0()),
      fib(s(s(x))) -> +(fib(s(x)), fib(x)),
         +(x, 0()) -> x,
        +(x, s(y)) -> s(+(x, y))}
     SPSC:
      Simple Projection:
       pi(fib#) = 0
      Strict:
       {fib#(s(s(x))) -> fib#(s(x))}
      EDG:
       {(fib#(s(s(x))) -> fib#(s(x)), fib#(s(s(x))) -> fib#(s(x)))}
       SCCS:
        Scc:
         {fib#(s(s(x))) -> fib#(s(x))}
        SCC:
         Strict:
          {fib#(s(s(x))) -> fib#(s(x))}
         Weak:
         {    fib(0()) -> 0(),
           fib(s(0())) -> s(0()),
          fib(s(s(x))) -> +(fib(s(x)), fib(x)),
             +(x, 0()) -> x,
            +(x, s(y)) -> s(+(x, y))}
         SPSC:
          Simple Projection:
           pi(fib#) = 0
          Strict:
           {}
          Qed