YES

Problem:
 average(s(x),y) -> average(x,s(y))
 average(x,s(s(s(y)))) -> s(average(s(x),y))
 average(0(),0()) -> 0()
 average(0(),s(0())) -> 0()
 average(0(),s(s(0()))) -> s(0())

Proof:
 DP Processor:
  DPs:
   average#(s(x),y) -> average#(x,s(y))
   average#(x,s(s(s(y)))) -> average#(s(x),y)
  TRS:
   average(s(x),y) -> average(x,s(y))
   average(x,s(s(s(y)))) -> s(average(s(x),y))
   average(0(),0()) -> 0()
   average(0(),s(0())) -> 0()
   average(0(),s(s(0()))) -> s(0())
  Matrix Interpretation Processor:
   dimension: 1
   interpretation:
    [average#](x0, x1) = x0 + x1,
    
    [0] = 0,
    
    [average](x0, x1) = x0 + x1,
    
    [s](x0) = x0 + 1
   orientation:
    average#(s(x),y) = x + y + 1 >= x + y + 1 = average#(x,s(y))
    
    average#(x,s(s(s(y)))) = x + y + 3 >= x + y + 1 = average#(s(x),y)
    
    average(s(x),y) = x + y + 1 >= x + y + 1 = average(x,s(y))
    
    average(x,s(s(s(y)))) = x + y + 3 >= x + y + 2 = s(average(s(x),y))
    
    average(0(),0()) = 0 >= 0 = 0()
    
    average(0(),s(0())) = 1 >= 0 = 0()
    
    average(0(),s(s(0()))) = 2 >= 1 = s(0())
   problem:
    DPs:
     average#(s(x),y) -> average#(x,s(y))
    TRS:
     average(s(x),y) -> average(x,s(y))
     average(x,s(s(s(y)))) -> s(average(s(x),y))
     average(0(),0()) -> 0()
     average(0(),s(0())) -> 0()
     average(0(),s(s(0()))) -> s(0())
   Subterm Criterion Processor:
    simple projection:
     pi(average#) = 0
    problem:
     DPs:
      
     TRS:
      average(s(x),y) -> average(x,s(y))
      average(x,s(s(s(y)))) -> s(average(s(x),y))
      average(0(),0()) -> 0()
      average(0(),s(0())) -> 0()
      average(0(),s(s(0()))) -> s(0())
    Qed