YES
O(n)
TRS:
 {
                h(x, c(y, z)) -> h(c(s(y), x), z),
  h(c(s(x), c(s(0()), y)), z) -> h(y, c(s(0()), c(x, z)))
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
                  h(x, c(y, z)) -> h(c(s(y), x), z),
    h(c(s(x), c(s(0()), y)), z) -> h(y, c(s(0()), c(x, z)))
   }
  BOUND:
   Automaton:
    {
           0_1() -> 9,
           0_0() -> 4,
         s_2(10) -> 13,
          s_2(4) -> 15,
          s_1(9) -> 10,
          s_1(4) -> 5,
          s_0(4) -> 4,
     c_2(15, 14) -> 16,
     c_2(13, 16) -> 14,
     c_2(13, 14) -> 14,
      c_2(13, 6) -> 14,
      c_2(13, 4) -> 14,
     c_1(10, 12) -> 12,
     c_1(10, 11) -> 12,
      c_1(5, 16) -> 6,
       c_1(5, 6) -> 6,
       c_1(5, 4) -> 6,
      c_1(4, 12) -> 11,
       c_1(4, 4) -> 11,
       c_0(4, 4) -> 4,
     h_2(16, 12) -> 4,
      h_2(16, 4) -> 4,
     h_2(14, 12) -> 4,
     h_2(14, 11) -> 4,
     h_1(16, 12) -> 4,
     h_1(14, 12) -> 4,
      h_1(6, 12) -> 4,
       h_1(6, 4) -> 4,
      h_1(4, 12) -> 4,
       h_0(4, 4) -> 4
    }
   Strict:
    {}
   Qed