YES
O(n)
TRS:
 {
           f(s(X)) -> f(X),
  g(cons(s(X), Y)) -> s(X),
   g(cons(0(), Y)) -> g(Y),
     h(cons(X, Y)) -> h(g(cons(X, Y)))
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
             f(s(X)) -> f(X),
    g(cons(s(X), Y)) -> s(X),
     g(cons(0(), Y)) -> g(Y),
       h(cons(X, Y)) -> h(g(cons(X, Y)))
   }
  BOUND:
   Automaton:
    {
           h_1(9) -> 6,
           h_0(7) -> 6,
           h_0(6) -> 6,
            0_0() -> 7,
     cons_1(7, 7) -> 8,
     cons_1(7, 6) -> 8,
     cons_1(6, 7) -> 8,
     cons_1(6, 6) -> 8,
     cons_0(7, 7) -> 6,
     cons_0(7, 6) -> 6,
     cons_0(6, 7) -> 6,
     cons_0(6, 6) -> 6,
           g_1(8) -> 9,
           g_1(7) -> 9 | 6,
           g_1(6) -> 9 | 6,
           g_0(7) -> 6,
           g_0(6) -> 6,
           s_2(7) -> 9,
           s_2(6) -> 9,
           s_1(7) -> 9 | 6,
           s_1(6) -> 9 | 6,
           s_0(7) -> 6,
           s_0(6) -> 6,
           f_2(7) -> 6,
           f_2(6) -> 6,
           f_1(7) -> 6,
           f_1(6) -> 6,
           f_0(7) -> 6,
           f_0(6) -> 6
    }
   Strict:
    {}
   Qed