YES

Proof:
This system is confluent.
By \cite{ALS94}, Theorem 4.1.
This system is of type 3 or smaller.
This system is strongly deterministic.
There are no critical pairs.
By \cite{A14}, Theorem 11.5.9.
This system is of type 3 or smaller.
This system is deterministic.
System R transformed to V(R) + Emb.
Call external tool:
ttt2 - trs 30
Input:
  plus(0, X) -> X
  plus(s(X), Y) -> plus(X, s(Y))
  fib(0) -> pair(s(0), 0)
  fib(s(X)) -> pair(plus(fib(X), fib(X)), fib(X))
  fib(s(X)) -> plus(fib(X), fib(X))
  fib(s(X)) -> fib(X)
  pair(x, y) -> x
  pair(x, y) -> y
  s(x) -> x
  fib(x) -> x
  plus(x, y) -> x
  plus(x, y) -> y

 DP Processor:
  DPs:
   plus#(s(X),Y) -> s#(Y)
   plus#(s(X),Y) -> plus#(X,s(Y))
   fib#(0()) -> s#(0())
   fib#(0()) -> pair#(s(0()),0())
   fib#(s(X)) -> fib#(X)
   fib#(s(X)) -> plus#(fib(X),fib(X))
   fib#(s(X)) -> pair#(plus(fib(X),fib(X)),fib(X))
  TRS:
   plus(0(),X) -> X
   plus(s(X),Y) -> plus(X,s(Y))
   fib(0()) -> pair(s(0()),0())
   fib(s(X)) -> pair(plus(fib(X),fib(X)),fib(X))
   fib(s(X)) -> plus(fib(X),fib(X))
   fib(s(X)) -> fib(X)
   pair(x,y) -> x
   pair(x,y) -> y
   s(x) -> x
   fib(x) -> x
   plus(x,y) -> x
   plus(x,y) -> y
  TDG Processor:
   DPs:
    plus#(s(X),Y) -> s#(Y)
    plus#(s(X),Y) -> plus#(X,s(Y))
    fib#(0()) -> s#(0())
    fib#(0()) -> pair#(s(0()),0())
    fib#(s(X)) -> fib#(X)
    fib#(s(X)) -> plus#(fib(X),fib(X))
    fib#(s(X)) -> pair#(plus(fib(X),fib(X)),fib(X))
   TRS:
    plus(0(),X) -> X
    plus(s(X),Y) -> plus(X,s(Y))
    fib(0()) -> pair(s(0()),0())
    fib(s(X)) -> pair(plus(fib(X),fib(X)),fib(X))
    fib(s(X)) -> plus(fib(X),fib(X))
    fib(s(X)) -> fib(X)
    pair(x,y) -> x
    pair(x,y) -> y
    s(x) -> x
    fib(x) -> x
    plus(x,y) -> x
    plus(x,y) -> y
   graph:
    fib#(s(X)) -> fib#(X) -> fib#(s(X)) -> pair#(plus(fib(X),fib(X)),fib(X))
    fib#(s(X)) -> fib#(X) -> fib#(s(X)) -> plus#(fib(X),fib(X))
    fib#(s(X)) -> fib#(X) -> fib#(s(X)) -> fib#(X)
    fib#(s(X)) -> fib#(X) -> fib#(0()) -> pair#(s(0()),0())
    fib#(s(X)) -> fib#(X) -> fib#(0()) -> s#(0())
    fib#(s(X)) -> plus#(fib(X),fib(X)) ->
    plus#(s(X),Y) -> plus#(X,s(Y))
    fib#(s(X)) -> plus#(fib(X),fib(X)) -> plus#(s(X),Y) -> s#(Y)
    plus#(s(X),Y) -> plus#(X,s(Y)) -> plus#(s(X),Y) -> plus#(X,s(Y))
    plus#(s(X),Y) -> plus#(X,s(Y)) -> plus#(s(X),Y) -> s#(Y)
   SCC Processor:
    #sccs: 2
    #rules: 2
    #arcs: 9/49
    DPs:
     fib#(s(X)) -> fib#(X)
    TRS:
     plus(0(),X) -> X
     plus(s(X),Y) -> plus(X,s(Y))
     fib(0()) -> pair(s(0()),0())
     fib(s(X)) -> pair(plus(fib(X),fib(X)),fib(X))
     fib(s(X)) -> plus(fib(X),fib(X))
     fib(s(X)) -> fib(X)
     pair(x,y) -> x
     pair(x,y) -> y
     s(x) -> x
     fib(x) -> x
     plus(x,y) -> x
     plus(x,y) -> y
    Subterm Criterion Processor:
     simple projection:
      pi(fib#) = 0
     problem:
      DPs:
       
      TRS:
       plus(0(),X) -> X
       plus(s(X),Y) -> plus(X,s(Y))
       fib(0()) -> pair(s(0()),0())
       fib(s(X)) -> pair(plus(fib(X),fib(X)),fib(X))
       fib(s(X)) -> plus(fib(X),fib(X))
       fib(s(X)) -> fib(X)
       pair(x,y) -> x
       pair(x,y) -> y
       s(x) -> x
       fib(x) -> x
       plus(x,y) -> x
       plus(x,y) -> y
     Qed
    
    DPs:
     plus#(s(X),Y) -> plus#(X,s(Y))
    TRS:
     plus(0(),X) -> X
     plus(s(X),Y) -> plus(X,s(Y))
     fib(0()) -> pair(s(0()),0())
     fib(s(X)) -> pair(plus(fib(X),fib(X)),fib(X))
     fib(s(X)) -> plus(fib(X),fib(X))
     fib(s(X)) -> fib(X)
     pair(x,y) -> x
     pair(x,y) -> y
     s(x) -> x
     fib(x) -> x
     plus(x,y) -> x
     plus(x,y) -> y
    Subterm Criterion Processor:
     simple projection:
      pi(plus#) = 0
     problem:
      DPs:
       
      TRS:
       plus(0(),X) -> X
       plus(s(X),Y) -> plus(X,s(Y))
       fib(0()) -> pair(s(0()),0())
       fib(s(X)) -> pair(plus(fib(X),fib(X)),fib(X))
       fib(s(X)) -> plus(fib(X),fib(X))
       fib(s(X)) -> fib(X)
       pair(x,y) -> x
       pair(x,y) -> y
       s(x) -> x
       fib(x) -> x
       plus(x,y) -> x
       plus(x,y) -> y
     Qed