YES(?,O(n^1))

Problem:
 f(f(x)) -> f(c(f(x)))
 f(f(x)) -> f(d(f(x)))
 g(c(x)) -> x
 g(d(x)) -> x
 g(c(0())) -> g(d(1()))
 g(c(1())) -> g(d(0()))

Proof:
 RT Transformation Processor:
  strict:
   f(f(x)) -> f(c(f(x)))
   f(f(x)) -> f(d(f(x)))
   g(c(x)) -> x
   g(d(x)) -> x
   g(c(0())) -> g(d(1()))
   g(c(1())) -> g(d(0()))
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   interpretation:
    [1] = 13,
    
    [0] = 25,
    
    [g](x0) = x0 + 3,
    
    [d](x0) = x0 + 16,
    
    [c](x0) = x0 + 29,
    
    [f](x0) = x0
   orientation:
    f(f(x)) = x >= x + 29 = f(c(f(x)))
    
    f(f(x)) = x >= x + 16 = f(d(f(x)))
    
    g(c(x)) = x + 32 >= x = x
    
    g(d(x)) = x + 19 >= x = x
    
    g(c(0())) = 57 >= 32 = g(d(1()))
    
    g(c(1())) = 45 >= 44 = g(d(0()))
   problem:
    strict:
     f(f(x)) -> f(c(f(x)))
     f(f(x)) -> f(d(f(x)))
    weak:
     g(c(x)) -> x
     g(d(x)) -> x
     g(c(0())) -> g(d(1()))
     g(c(1())) -> g(d(0()))
   Bounds Processor:
    bound: 2
    enrichment: match-rt
    automaton:
     final states: {7}
     transitions:
      f1(12) -> 13*
      f1(14) -> 15*
      c1(28) -> 29*
      c1(13) -> 14*
      d1(60) -> 61*
      d1(50) -> 51*
      f2(34) -> 35*
      f2(36) -> 37*
      d2(68) -> 69*
      c2(35) -> 36*
      f0(7) -> 7*
      c0(7) -> 7*
      d0(7) -> 7*
      g0(7) -> 7*
      00() -> 7*
      10() -> 7*
      7 -> 12*
      13 -> 60*
      14 -> 34*
      15 -> 50,13,28,7
      29 -> 14*
      35 -> 68*
      37 -> 13*
      51 -> 14*
      61 -> 14*
      69 -> 36*
    problem:
     strict:
      f(f(x)) -> f(d(f(x)))
     weak:
      f(f(x)) -> f(c(f(x)))
      g(c(x)) -> x
      g(d(x)) -> x
      g(c(0())) -> g(d(1()))
      g(c(1())) -> g(d(0()))
    Bounds Processor:
     bound: 2
     enrichment: match-rt
     automaton:
      final states: {7}
      transitions:
       f1(12) -> 13*
       f1(14) -> 15*
       c1(30) -> 31*
       c1(32) -> 33*
       d1(16) -> 17*
       d1(13) -> 14*
       f2(22) -> 23*
       f2(24) -> 25*
       d2(23) -> 24*
       c2(40) -> 41*
       f0(7) -> 7*
       c0(7) -> 7*
       d0(7) -> 7*
       g0(7) -> 7*
       00() -> 7*
       10() -> 7*
       7 -> 12*
       13 -> 32*
       14 -> 22*
       15 -> 30,13,16,7
       17 -> 14*
       23 -> 40*
       25 -> 13*
       31 -> 14*
       33 -> 14*
       41 -> 24*
     problem:
      strict:
       
      weak:
       f(f(x)) -> f(d(f(x)))
       f(f(x)) -> f(c(f(x)))
       g(c(x)) -> x
       g(d(x)) -> x
       g(c(0())) -> g(d(1()))
       g(c(1())) -> g(d(0()))
     Qed