YES(?,O(n^2))

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

Proof:
 RT Transformation Processor:
  strict:
   a(a(x1)) -> d(c(x1))
   a(b(x1)) -> c(c(c(x1)))
   b(b(x1)) -> a(c(c(x1)))
   c(c(x1)) -> b(x1)
   c(d(x1)) -> a(a(x1))
   d(d(x1)) -> b(a(c(x1)))
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   interpretation:
    [b](x0) = x0 + 2,
    
    [d](x0) = x0 + 24,
    
    [c](x0) = x0,
    
    [a](x0) = x0
   orientation:
    a(a(x1)) = x1 >= x1 + 24 = d(c(x1))
    
    a(b(x1)) = x1 + 2 >= x1 = c(c(c(x1)))
    
    b(b(x1)) = x1 + 4 >= x1 = a(c(c(x1)))
    
    c(c(x1)) = x1 >= x1 + 2 = b(x1)
    
    c(d(x1)) = x1 + 24 >= x1 = a(a(x1))
    
    d(d(x1)) = x1 + 48 >= x1 + 2 = b(a(c(x1)))
   problem:
    strict:
     a(a(x1)) -> d(c(x1))
     c(c(x1)) -> b(x1)
    weak:
     a(b(x1)) -> c(c(c(x1)))
     b(b(x1)) -> a(c(c(x1)))
     c(d(x1)) -> a(a(x1))
     d(d(x1)) -> b(a(c(x1)))
   Matrix Interpretation Processor:
    dimension: 1
    interpretation:
     [b](x0) = x0 + 15,
     
     [d](x0) = x0 + 19,
     
     [c](x0) = x0 + 8,
     
     [a](x0) = x0 + 9
    orientation:
     a(a(x1)) = x1 + 18 >= x1 + 27 = d(c(x1))
     
     c(c(x1)) = x1 + 16 >= x1 + 15 = b(x1)
     
     a(b(x1)) = x1 + 24 >= x1 + 24 = c(c(c(x1)))
     
     b(b(x1)) = x1 + 30 >= x1 + 25 = a(c(c(x1)))
     
     c(d(x1)) = x1 + 27 >= x1 + 18 = a(a(x1))
     
     d(d(x1)) = x1 + 38 >= x1 + 32 = b(a(c(x1)))
    problem:
     strict:
      a(a(x1)) -> d(c(x1))
     weak:
      c(c(x1)) -> b(x1)
      a(b(x1)) -> c(c(c(x1)))
      b(b(x1)) -> a(c(c(x1)))
      c(d(x1)) -> a(a(x1))
      d(d(x1)) -> b(a(c(x1)))
    Matrix Interpretation Processor:
     dimension: 2
     interpretation:
                [1 6]     [3]
      [b](x0) = [0 1]x0 + [2],
      
                [1 7]     [4]
      [d](x0) = [0 1]x0 + [3],
      
                [1 3]     [1]
      [c](x0) = [0 1]x0 + [1],
      
                [1 5]     [2]
      [a](x0) = [0 1]x0 + [2]
     orientation:
                 [1  10]     [14]    [1  10]     [12]           
      a(a(x1)) = [0  1 ]x1 + [4 ] >= [0  1 ]x1 + [4 ] = d(c(x1))
      
                 [1 6]     [5]    [1 6]     [3]        
      c(c(x1)) = [0 1]x1 + [2] >= [0 1]x1 + [2] = b(x1)
      
                 [1  11]     [15]    [1 9]     [12]              
      a(b(x1)) = [0  1 ]x1 + [4 ] >= [0 1]x1 + [3 ] = c(c(c(x1)))
      
                 [1  12]     [18]    [1  11]     [17]              
      b(b(x1)) = [0  1 ]x1 + [4 ] >= [0  1 ]x1 + [4 ] = a(c(c(x1)))
      
                 [1  10]     [14]    [1  10]     [14]           
      c(d(x1)) = [0  1 ]x1 + [4 ] >= [0  1 ]x1 + [4 ] = a(a(x1))
      
                 [1  14]     [29]    [1  14]     [29]              
      d(d(x1)) = [0  1 ]x1 + [6 ] >= [0  1 ]x1 + [5 ] = b(a(c(x1)))
     problem:
      strict:
       
      weak:
       a(a(x1)) -> d(c(x1))
       c(c(x1)) -> b(x1)
       a(b(x1)) -> c(c(c(x1)))
       b(b(x1)) -> a(c(c(x1)))
       c(d(x1)) -> a(a(x1))
       d(d(x1)) -> b(a(c(x1)))
     Qed