YES
O(n)
TRS:
 {f(c(s(x), y)) -> f(c(x, s(y))),
  g(c(x, s(y))) -> g(c(s(x), y))}
 DUP: We consider a non-duplicating system.
  Trs:
   {f(c(s(x), y)) -> f(c(x, s(y))),
    g(c(x, s(y))) -> g(c(s(x), y))}
  BOUND:
   Automaton:
    {
        g_1(9) -> 4,
        g_0(4) -> 4,
        s_1(5) -> 5,
        s_1(4) -> 5,
        s_0(4) -> 4,
     c_1(5, 4) -> 9,
     c_1(4, 5) -> 6,
     c_0(4, 4) -> 4,
        f_1(6) -> 4,
        f_0(4) -> 4
    }
   Strict:
    {}
   Qed