YES
Input TRS:
      1: average(s(x),y) -> average(x,s(y))
      2: average(x,s(s(s(y)))) -> s(average(s(x),y))
      3: average(0(),0()) -> 0()
      4: average(0(),s(0())) -> 0()
      5: average(0(),s(s(0()))) -> s(0())
Number of strict rules: 5
Direct POLO(bPol) ... removes: 4 3 5 2
      s 	w: x1 + 10452
      average	w: 2 * x1 + 2 * x2
      0 	w: 1
Number of strict rules: 1
Direct POLO(bPol) ... removes: 1
      s 	w: x1 + 36737
      average	w: 2 * x1 + x2
      0 	w: 1
Number of strict rules: 0