YES

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

linear polynomial interpretations on N:

  fib_A(x1) = 1
  fib#_A(x1) = 5
  0_A = 1
  0#_A = 0
  s_A(x1) = 0
  s#_A(x1) = 1
  sp_A(x1) = x1
  sp#_A(x1) = x1 + 2
  g_A(x1) = 1
  g#_A(x1) = 4
  pair_A(x1,x2) = x1 + 1
  pair#_A(x1,x2) = 0
  np_A(x1) = x1
  np#_A(x1) = 3
  +_A(x1,x2) = x1
  +#_A(x1,x2) = 2

precedence:

  sp > fib > s > g > 0 = np > pair > +