YES
Trs:
 {f(c(s(x), y)) -> f(c(x, s(y))),
  g(c(x, s(y))) -> g(c(s(x), y))}
 Comment:
  We consider a non-duplicating trs.
  BOUND:
   Automaton:
    {    f_1(q9) -> q4,
         f_0(q4) -> q4,
         s_1(q5) -> q5,
         s_1(q4) -> q5,
         s_0(q4) -> q4,
     c_1(q5, q4) -> q6,
     c_1(q4, q5) -> q9,
     c_0(q4, q4) -> q4,
         g_1(q6) -> q4,
         g_0(q4) -> q4}
   Strict:
   {}
   Qed