YES(?,O(n^1))

Problem:
 a(x1) -> g(d(x1))
 b(b(b(x1))) -> c(d(c(x1)))
 b(b(x1)) -> a(g(g(x1)))
 c(d(x1)) -> g(g(x1))
 g(g(g(x1))) -> b(b(x1))

Proof:
 RT Transformation Processor:
  strict:
   a(x1) -> g(d(x1))
   b(b(b(x1))) -> c(d(c(x1)))
   b(b(x1)) -> a(g(g(x1)))
   c(d(x1)) -> g(g(x1))
   g(g(g(x1))) -> b(b(x1))
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   interpretation:
    [c](x0) = x0,
    
    [b](x0) = x0,
    
    [g](x0) = x0 + 13,
    
    [d](x0) = x0,
    
    [a](x0) = x0 + 2
   orientation:
    a(x1) = x1 + 2 >= x1 + 13 = g(d(x1))
    
    b(b(b(x1))) = x1 >= x1 = c(d(c(x1)))
    
    b(b(x1)) = x1 >= x1 + 28 = a(g(g(x1)))
    
    c(d(x1)) = x1 >= x1 + 26 = g(g(x1))
    
    g(g(g(x1))) = x1 + 39 >= x1 = b(b(x1))
   problem:
    strict:
     a(x1) -> g(d(x1))
     b(b(b(x1))) -> c(d(c(x1)))
     b(b(x1)) -> a(g(g(x1)))
     c(d(x1)) -> g(g(x1))
    weak:
     g(g(g(x1))) -> b(b(x1))
   Matrix Interpretation Processor:
    dimension: 1
    interpretation:
     [c](x0) = x0 + 16,
     
     [b](x0) = x0,
     
     [g](x0) = x0,
     
     [d](x0) = x0 + 11,
     
     [a](x0) = x0
    orientation:
     a(x1) = x1 >= x1 + 11 = g(d(x1))
     
     b(b(b(x1))) = x1 >= x1 + 43 = c(d(c(x1)))
     
     b(b(x1)) = x1 >= x1 = a(g(g(x1)))
     
     c(d(x1)) = x1 + 27 >= x1 = g(g(x1))
     
     g(g(g(x1))) = x1 >= x1 = b(b(x1))
    problem:
     strict:
      a(x1) -> g(d(x1))
      b(b(b(x1))) -> c(d(c(x1)))
      b(b(x1)) -> a(g(g(x1)))
     weak:
      c(d(x1)) -> g(g(x1))
      g(g(g(x1))) -> b(b(x1))
    Matrix Interpretation Processor:
     dimension: 1
     interpretation:
      [c](x0) = x0 + 17,
      
      [b](x0) = x0,
      
      [g](x0) = x0 + 9,
      
      [d](x0) = x0 + 1,
      
      [a](x0) = x0 + 12
     orientation:
      a(x1) = x1 + 12 >= x1 + 10 = g(d(x1))
      
      b(b(b(x1))) = x1 >= x1 + 35 = c(d(c(x1)))
      
      b(b(x1)) = x1 >= x1 + 30 = a(g(g(x1)))
      
      c(d(x1)) = x1 + 18 >= x1 + 18 = g(g(x1))
      
      g(g(g(x1))) = x1 + 27 >= x1 = b(b(x1))
     problem:
      strict:
       b(b(b(x1))) -> c(d(c(x1)))
       b(b(x1)) -> a(g(g(x1)))
      weak:
       a(x1) -> g(d(x1))
       c(d(x1)) -> g(g(x1))
       g(g(g(x1))) -> b(b(x1))
     Matrix Interpretation Processor:
      dimension: 1
      interpretation:
       [c](x0) = x0 + 4,
       
       [b](x0) = x0 + 3,
       
       [g](x0) = x0 + 2,
       
       [d](x0) = x0,
       
       [a](x0) = x0 + 2
      orientation:
       b(b(b(x1))) = x1 + 9 >= x1 + 8 = c(d(c(x1)))
       
       b(b(x1)) = x1 + 6 >= x1 + 6 = a(g(g(x1)))
       
       a(x1) = x1 + 2 >= x1 + 2 = g(d(x1))
       
       c(d(x1)) = x1 + 4 >= x1 + 4 = g(g(x1))
       
       g(g(g(x1))) = x1 + 6 >= x1 + 6 = b(b(x1))
      problem:
       strict:
        b(b(x1)) -> a(g(g(x1)))
       weak:
        b(b(b(x1))) -> c(d(c(x1)))
        a(x1) -> g(d(x1))
        c(d(x1)) -> g(g(x1))
        g(g(g(x1))) -> b(b(x1))
      Arctic Interpretation Processor:
       dimension: 2
       interpretation:
                  [4  0 ]  
        [c](x0) = [3  -&]x0,
        
                  [0 4]  
        [b](x0) = [1 3]x0,
        
                  [0 3]  
        [g](x0) = [0 2]x0,
        
                  [0  1 ]  
        [d](x0) = [-& -&]x0,
        
                  [1 1]  
        [a](x0) = [0 1]x0
       orientation:
                   [5 7]      [4 6]                
        b(b(x1)) = [4 6]x1 >= [3 5]x1 = a(g(g(x1)))
        
                      [8  10]      [8 4]                
        b(b(b(x1))) = [7  9 ]x1 >= [7 3]x1 = c(d(c(x1)))
        
                [1 1]      [0 1]             
        a(x1) = [0 1]x1 >= [0 1]x1 = g(d(x1))
        
                   [4 5]      [3 5]             
        c(d(x1)) = [3 4]x1 >= [2 4]x1 = g(g(x1))
        
                      [5 7]      [5 7]             
        g(g(g(x1))) = [4 6]x1 >= [4 6]x1 = b(b(x1))
       problem:
        strict:
         
        weak:
         b(b(x1)) -> a(g(g(x1)))
         b(b(b(x1))) -> c(d(c(x1)))
         a(x1) -> g(d(x1))
         c(d(x1)) -> g(g(x1))
         g(g(g(x1))) -> b(b(x1))
       Qed