YES
Trs:
 {         f(s(X)) -> f(X),
   g(cons(0(), Y)) -> g(Y),
  g(cons(s(X), Y)) -> s(X),
     h(cons(X, Y)) -> h(g(cons(X, Y)))}
 Comment:
  We consider a non-duplicating trs.
  BOUND:
   Automaton:
    {       f_2(q7) -> q6,
            f_2(q6) -> q6,
            f_1(q7) -> q6,
            f_1(q6) -> q6,
            f_0(q7) -> q6,
            f_0(q6) -> q6,
              0_0() -> q7,
            s_2(q7) -> q9,
            s_2(q6) -> q9,
            s_1(q7) -> q9 | q6,
            s_1(q6) -> q9 | q6,
            s_0(q7) -> q6,
            s_0(q6) -> q6,
     cons_1(q7, q7) -> q8,
     cons_1(q7, q6) -> q8,
     cons_1(q6, q7) -> q8,
     cons_1(q6, q6) -> q8,
     cons_0(q7, q7) -> q6,
     cons_0(q7, q6) -> q6,
     cons_0(q6, q7) -> q6,
     cons_0(q6, q6) -> q6,
            g_1(q8) -> q9,
            g_1(q7) -> q9 | q6,
            g_1(q6) -> q9 | q6,
            g_0(q7) -> q6,
            g_0(q6) -> q6,
            h_1(q9) -> q6,
            h_0(q7) -> q6,
            h_0(q6) -> q6}
   Strict:
   {}
   Qed