TRS:
 {      fib(0()) -> 0(),
     fib(s(0())) -> s(0()),
  fib(s(s(0()))) -> s(0()),
    fib(s(s(x))) -> sp(g(x)),
          g(0()) -> pair(s(0()), 0()),
       g(s(0())) -> pair(s(0()), s(0())),
         g(s(x)) -> np(g(x)),
  sp(pair(x, y)) -> +(x, y),
  np(pair(x, y)) -> pair(+(x, y), x),
       +(x, 0()) -> x,
      +(x, s(y)) -> s(+(x, y))}
 MPO:
  Prec:
   np > pair, 
   np > +, 
   g > s, 
   g > pair, 
   g > np, 
   fib > g, 
   fib > sp, 
   sp > +, 
   + > s
   empty
  Strict:
   {}
   Weak:
    {}
  Qed