YES
Input TRS:
      1: half(0()) -> 0()
      2: half(s(0())) -> 0()
      3: half(s(s(x))) -> s(half(x))
      4: bits(0()) -> 0()
      5: bits(s(x)) -> s(bits(half(s(x))))
Number of strict rules: 5
Direct POLO(bPol) ... removes: 4
      s 	w: x1
      half	w: x1
      0 	w: 14681
      bits	w: x1 + 2998
Number of strict rules: 4
Direct POLO(bPol) ... failed.
Uncurrying half
      1: half^1_0() -> 0()
      2: half^1_s(0()) -> 0()
      3: half^1_s(s(x)) -> s(half(x))
      5: bits(s(x)) -> s(bits(half^1_s(x)))
      6: half(0()) ->= half^1_0()
      7: half(s(_1)) ->= half^1_s(_1)
Number of strict rules: 4
Direct POLO(bPol) ... removes: 1 3 5 7 6 2
      s 	w: 2 * x1 + 21
      half^1_s	w: x1 + 5
      half	w: x1 + 2
      0 	w: 1
      half^1_0	w: 2
      bits	w: 2 * x1
Number of strict rules: 0