YES
O(n)
TRS:
 {
    f(f(x)) -> f(c(f(x))),
    f(f(x)) -> f(d(f(x))),
    g(c(x)) -> x,
  g(c(1())) -> g(d(0())),
  g(c(0())) -> g(d(1())),
    g(d(x)) -> x
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
      f(f(x)) -> f(c(f(x))),
      f(f(x)) -> f(d(f(x))),
      g(c(x)) -> x,
    g(c(1())) -> g(d(0())),
    g(c(0())) -> g(d(1())),
      g(d(x)) -> x
   }
  BOUND:
   Automaton:
    {
       0_1() -> 10,
       0_0() -> 6,
       1_1() -> 7,
       1_0() -> 6,
      g_1(8) -> 9,
      g_0(6) -> 6,
     d_2(25) -> 26,
     d_1(15) -> 16,
      d_1(7) -> 8,
      d_0(6) -> 6,
     c_2(21) -> 22,
     c_1(12) -> 13,
      c_0(6) -> 6,
     f_2(22) -> 23,
     f_2(20) -> 21,
     f_1(13) -> 14,
     f_1(11) -> 12,
      f_0(6) -> 6,
          26 -> 22,
          23 -> 12,
          21 -> 25,
          16 -> 13,
          14 -> 12 | 6,
          13 -> 20,
          12 -> 15,
          10 -> 7,
           9 -> 6,
           7 -> 9,
           6 -> 11
    }
   Strict:
    {}
   Qed