YES

Problem:
 bin(x,0()) -> s(0())
 bin(0(),s(y)) -> 0()
 bin(s(x),s(y)) -> +(bin(x,s(y)),bin(x,y))

Proof:
 DP Processor:
  DPs:
   bin#(s(x),s(y)) -> bin#(x,y)
   bin#(s(x),s(y)) -> bin#(x,s(y))
  TRS:
   bin(x,0()) -> s(0())
   bin(0(),s(y)) -> 0()
   bin(s(x),s(y)) -> +(bin(x,s(y)),bin(x,y))
  Usable Rule Processor:
   DPs:
    bin#(s(x),s(y)) -> bin#(x,y)
    bin#(s(x),s(y)) -> bin#(x,s(y))
   TRS:
    
   Restore Modifier:
    DPs:
     bin#(s(x),s(y)) -> bin#(x,y)
     bin#(s(x),s(y)) -> bin#(x,s(y))
    TRS:
     bin(x,0()) -> s(0())
     bin(0(),s(y)) -> 0()
     bin(s(x),s(y)) -> +(bin(x,s(y)),bin(x,y))
    SCC Processor:
     #sccs: 1
     #rules: 2
     #arcs: 4/4
     DPs:
      bin#(s(x),s(y)) -> bin#(x,y)
      bin#(s(x),s(y)) -> bin#(x,s(y))
     TRS:
      bin(x,0()) -> s(0())
      bin(0(),s(y)) -> 0()
      bin(s(x),s(y)) -> +(bin(x,s(y)),bin(x,y))
     Matrix Interpretation Processor:
      dimension: 1
      interpretation:
       [bin#](x0, x1) = x0,
       
       [+](x0, x1) = x0,
       
       [s](x0) = x0 + 1,
       
       [bin](x0, x1) = x1 + 1,
       
       [0] = 1
      orientation:
       bin#(s(x),s(y)) = x + 1 >= x = bin#(x,y)
       
       bin#(s(x),s(y)) = x + 1 >= x = bin#(x,s(y))
       
       bin(x,0()) = 2 >= 2 = s(0())
       
       bin(0(),s(y)) = y + 2 >= 1 = 0()
       
       bin(s(x),s(y)) = y + 2 >= y + 2 = +(bin(x,s(y)),bin(x,y))
      problem:
       DPs:
        
       TRS:
        bin(x,0()) -> s(0())
        bin(0(),s(y)) -> 0()
        bin(s(x),s(y)) -> +(bin(x,s(y)),bin(x,y))
      Qed