YES(?,PRIMREC)

We are left with following problem, upon which TcT provides the
certificate YES(?,PRIMREC).

Strict Trs:
  { fib(0()) -> 0()
  , fib(s(0())) -> s(0())
  , fib(s(s(x))) -> sp(g(x))
  , fib(s(s(0()))) -> s(0())
  , sp(pair(x, y)) -> +(x, y)
  , g(0()) -> pair(s(0()), 0())
  , g(s(x)) -> np(g(x))
  , g(s(0())) -> pair(s(0()), s(0()))
  , np(pair(x, y)) -> pair(+(x, y), x)
  , +(x, 0()) -> x
  , +(x, s(y)) -> s(+(x, y)) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,PRIMREC)

The input was oriented with the instance of'multiset path order' as
induced by the precedence

 fib > s, fib > sp, fib > g, fib > pair, fib > np, fib > +, 0 > s,
 0 > sp, 0 > g, 0 > pair, 0 > np, 0 > +, sp > s, sp > pair, g > s,
 g > sp, g > pair, g > np, g > +, np > s, np > sp, np > pair,
 np > +, + > s, + > pair, fib ~ 0, s ~ pair, sp ~ + .

Hurray, we answered YES(?,PRIMREC)