YES
Trs:
 {  f(f(x)) -> f(c(f(x))),
    f(f(x)) -> f(d(f(x))),
  g(c(1())) -> g(d(0())),
  g(c(0())) -> g(d(1())),
    g(c(x)) -> x,
    g(d(x)) -> x}
 Comment:
  We consider a non-duplicating trs.
  BOUND:
   Automaton:
    {f_2(q22) -> q23,
     f_2(q20) -> q21,
     f_1(q13) -> q14,
     f_1(q11) -> q12,
      f_0(q6) -> q6,
        1_1() -> q10,
        1_0() -> q6,
     c_2(q25) -> q26,
     c_1(q15) -> q16,
      c_0(q6) -> q6,
        0_1() -> q7,
        0_0() -> q6,
     d_2(q21) -> q22,
     d_1(q12) -> q13,
      d_1(q7) -> q8,
      d_0(q6) -> q6,
      g_1(q8) -> q9,
      g_0(q6) -> q6,
          q26 -> q22,
          q23 -> q12,
          q21 -> q25,
          q16 -> q13,
          q14 -> q12 | q6,
          q13 -> q20,
          q12 -> q15,
          q10 -> q7,
           q9 -> q6,
           q7 -> q9,
           q6 -> q11}
   Strict:
   {}
   Qed