YES(?,O(n^2))

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

Proof:
 RT Transformation Processor:
  strict:
   a(a(x1)) -> b(x1)
   a(a(a(x1))) -> a(b(a(x1)))
   a(b(a(x1))) -> b(b(b(x1)))
   a(a(a(a(x1)))) -> a(a(b(a(a(x1)))))
   a(a(b(a(x1)))) -> a(b(b(a(b(x1)))))
   a(b(a(a(x1)))) -> b(a(b(b(a(x1)))))
   a(b(b(a(x1)))) -> b(b(b(b(b(x1)))))
   a(a(a(a(a(x1))))) -> a(a(a(b(a(a(a(x1)))))))
   a(a(a(b(a(x1))))) -> a(a(b(b(a(a(b(x1)))))))
   a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(x1)))))))
   a(a(b(b(a(x1))))) -> a(b(b(b(a(b(b(x1)))))))
   a(b(a(a(a(x1))))) -> b(a(a(b(b(a(a(x1)))))))
   a(b(a(b(a(x1))))) -> b(a(b(b(b(a(b(x1)))))))
   a(b(b(a(a(x1))))) -> b(b(a(b(b(b(a(x1)))))))
   a(b(b(b(a(x1))))) -> b(b(b(b(b(b(b(x1)))))))
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   interpretation:
    [b](x0) = x0,
    
    [a](x0) = x0 + 4
   orientation:
    a(a(x1)) = x1 + 8 >= x1 = b(x1)
    
    a(a(a(x1))) = x1 + 12 >= x1 + 8 = a(b(a(x1)))
    
    a(b(a(x1))) = x1 + 8 >= x1 = b(b(b(x1)))
    
    a(a(a(a(x1)))) = x1 + 16 >= x1 + 16 = a(a(b(a(a(x1)))))
    
    a(a(b(a(x1)))) = x1 + 12 >= x1 + 8 = a(b(b(a(b(x1)))))
    
    a(b(a(a(x1)))) = x1 + 12 >= x1 + 8 = b(a(b(b(a(x1)))))
    
    a(b(b(a(x1)))) = x1 + 8 >= x1 = b(b(b(b(b(x1)))))
    
    a(a(a(a(a(x1))))) = x1 + 20 >= x1 + 24 = a(a(a(b(a(a(a(x1)))))))
    
    a(a(a(b(a(x1))))) = x1 + 16 >= x1 + 16 = a(a(b(b(a(a(b(x1)))))))
    
    a(a(b(a(a(x1))))) = x1 + 16 >= x1 + 16 = a(b(a(b(a(b(a(x1)))))))
    
    a(a(b(b(a(x1))))) = x1 + 12 >= x1 + 8 = a(b(b(b(a(b(b(x1)))))))
    
    a(b(a(a(a(x1))))) = x1 + 16 >= x1 + 16 = b(a(a(b(b(a(a(x1)))))))
    
    a(b(a(b(a(x1))))) = x1 + 12 >= x1 + 8 = b(a(b(b(b(a(b(x1)))))))
    
    a(b(b(a(a(x1))))) = x1 + 12 >= x1 + 8 = b(b(a(b(b(b(a(x1)))))))
    
    a(b(b(b(a(x1))))) = x1 + 8 >= x1 = b(b(b(b(b(b(b(x1)))))))
   problem:
    strict:
     a(a(a(a(x1)))) -> a(a(b(a(a(x1)))))
     a(a(a(a(a(x1))))) -> a(a(a(b(a(a(a(x1)))))))
     a(a(a(b(a(x1))))) -> a(a(b(b(a(a(b(x1)))))))
     a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(x1)))))))
     a(b(a(a(a(x1))))) -> b(a(a(b(b(a(a(x1)))))))
    weak:
     a(a(x1)) -> b(x1)
     a(a(a(x1))) -> a(b(a(x1)))
     a(b(a(x1))) -> b(b(b(x1)))
     a(a(b(a(x1)))) -> a(b(b(a(b(x1)))))
     a(b(a(a(x1)))) -> b(a(b(b(a(x1)))))
     a(b(b(a(x1)))) -> b(b(b(b(b(x1)))))
     a(a(b(b(a(x1))))) -> a(b(b(b(a(b(b(x1)))))))
     a(b(a(b(a(x1))))) -> b(a(b(b(b(a(b(x1)))))))
     a(b(b(a(a(x1))))) -> b(b(a(b(b(b(a(x1)))))))
     a(b(b(b(a(x1))))) -> b(b(b(b(b(b(b(x1)))))))
   Matrix Interpretation Processor:
    dimension: 2
    interpretation:
               [1 0]  
     [b](x0) = [0 0]x0,
     
               [1 1]     [0]
     [a](x0) = [0 0]x0 + [2]
    orientation:
                      [1 1]     [6]    [1 1]     [4]                    
     a(a(a(a(x1)))) = [0 0]x1 + [2] >= [0 0]x1 + [2] = a(a(b(a(a(x1)))))
     
                         [1 1]     [8]    [1 1]     [8]                          
     a(a(a(a(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 + [2] = a(a(a(b(a(a(a(x1)))))))
     
                         [1 1]     [4]    [1 0]     [4]                          
     a(a(a(b(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 + [2] = a(a(b(b(a(a(b(x1)))))))
     
                         [1 1]     [4]    [1 1]     [0]                          
     a(a(b(a(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 + [2] = a(b(a(b(a(b(a(x1)))))))
     
                         [1 1]     [4]    [1 1]     [4]                          
     a(b(a(a(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 + [0] = b(a(a(b(b(a(a(x1)))))))
     
                [1 1]     [2]    [1 0]          
     a(a(x1)) = [0 0]x1 + [2] >= [0 0]x1 = b(x1)
     
                   [1 1]     [4]    [1 1]     [0]              
     a(a(a(x1))) = [0 0]x1 + [2] >= [0 0]x1 + [2] = a(b(a(x1)))
     
                   [1 1]     [0]    [1 0]                
     a(b(a(x1))) = [0 0]x1 + [2] >= [0 0]x1 = b(b(b(x1)))
     
                      [1 1]     [2]    [1 0]     [0]                    
     a(a(b(a(x1)))) = [0 0]x1 + [2] >= [0 0]x1 + [2] = a(b(b(a(b(x1)))))
     
                      [1 1]     [2]    [1 1]                      
     a(b(a(a(x1)))) = [0 0]x1 + [2] >= [0 0]x1 = b(a(b(b(a(x1)))))
     
                      [1 1]     [0]    [1 0]                      
     a(b(b(a(x1)))) = [0 0]x1 + [2] >= [0 0]x1 = b(b(b(b(b(x1)))))
     
                         [1 1]     [2]    [1 0]     [0]                          
     a(a(b(b(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 + [2] = a(b(b(b(a(b(b(x1)))))))
     
                         [1 1]     [0]    [1 0]                            
     a(b(a(b(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 = b(a(b(b(b(a(b(x1)))))))
     
                         [1 1]     [2]    [1 1]                            
     a(b(b(a(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 = b(b(a(b(b(b(a(x1)))))))
     
                         [1 1]     [0]    [1 0]                            
     a(b(b(b(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 = b(b(b(b(b(b(b(x1)))))))
    problem:
     strict:
      a(a(a(a(a(x1))))) -> a(a(a(b(a(a(a(x1)))))))
      a(a(a(b(a(x1))))) -> a(a(b(b(a(a(b(x1)))))))
      a(b(a(a(a(x1))))) -> b(a(a(b(b(a(a(x1)))))))
     weak:
      a(a(a(a(x1)))) -> a(a(b(a(a(x1)))))
      a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(x1)))))))
      a(a(x1)) -> b(x1)
      a(a(a(x1))) -> a(b(a(x1)))
      a(b(a(x1))) -> b(b(b(x1)))
      a(a(b(a(x1)))) -> a(b(b(a(b(x1)))))
      a(b(a(a(x1)))) -> b(a(b(b(a(x1)))))
      a(b(b(a(x1)))) -> b(b(b(b(b(x1)))))
      a(a(b(b(a(x1))))) -> a(b(b(b(a(b(b(x1)))))))
      a(b(a(b(a(x1))))) -> b(a(b(b(b(a(b(x1)))))))
      a(b(b(a(a(x1))))) -> b(b(a(b(b(b(a(x1)))))))
      a(b(b(b(a(x1))))) -> b(b(b(b(b(b(b(x1)))))))
    Matrix Interpretation Processor:
     dimension: 2
     interpretation:
                [1 2]  
      [b](x0) = [0 0]x0,
      
                [1 2]     [0]
      [a](x0) = [0 1]x0 + [1]
     orientation:
                          [1  10]     [20]    [1 8]     [18]                          
      a(a(a(a(a(x1))))) = [0  1 ]x1 + [5 ] >= [0 0]x1 + [3 ] = a(a(a(b(a(a(a(x1)))))))
      
                          [1 4]     [8]    [1 2]     [8]                          
      a(a(a(b(a(x1))))) = [0 0]x1 + [3] >= [0 0]x1 + [2] = a(a(b(b(a(a(b(x1)))))))
      
                          [1 8]     [12]    [1 6]     [12]                          
      a(b(a(a(a(x1))))) = [0 0]x1 + [1 ] >= [0 0]x1 + [0 ] = b(a(a(b(b(a(a(x1)))))))
      
                       [1 8]     [12]    [1 6]     [8]                    
      a(a(a(a(x1)))) = [0 1]x1 + [4 ] >= [0 0]x1 + [2] = a(a(b(a(a(x1)))))
      
                          [1 6]     [8]    [1 4]     [6]                          
      a(a(b(a(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 + [1] = a(b(a(b(a(b(a(x1)))))))
      
                 [1 4]     [2]    [1 2]          
      a(a(x1)) = [0 1]x1 + [2] >= [0 0]x1 = b(x1)
      
                    [1 6]     [6]    [1 4]     [2]              
      a(a(a(x1))) = [0 1]x1 + [3] >= [0 0]x1 + [1] = a(b(a(x1)))
      
                    [1 4]     [2]    [1 2]                
      a(b(a(x1))) = [0 0]x1 + [1] >= [0 0]x1 = b(b(b(x1)))
      
                       [1 4]     [4]    [1 2]     [2]                    
      a(a(b(a(x1)))) = [0 0]x1 + [2] >= [0 0]x1 + [1] = a(b(b(a(b(x1)))))
      
                       [1 6]     [6]    [1 4]     [4]                    
      a(b(a(a(x1)))) = [0 0]x1 + [1] >= [0 0]x1 + [0] = b(a(b(b(a(x1)))))
      
                       [1 4]     [2]    [1 2]                      
      a(b(b(a(x1)))) = [0 0]x1 + [1] >= [0 0]x1 = b(b(b(b(b(x1)))))
      
                          [1 4]     [4]    [1 2]     [2]                          
      a(a(b(b(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 + [1] = a(b(b(b(a(b(b(x1)))))))
      
                          [1 4]     [4]    [1 2]     [4]                          
      a(b(a(b(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 + [0] = b(a(b(b(b(a(b(x1)))))))
      
                          [1 6]     [6]    [1 4]     [4]                          
      a(b(b(a(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 + [0] = b(b(a(b(b(b(a(x1)))))))
      
                          [1 4]     [2]    [1 2]                            
      a(b(b(b(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 = b(b(b(b(b(b(b(x1)))))))
     problem:
      strict:
       a(a(a(b(a(x1))))) -> a(a(b(b(a(a(b(x1)))))))
       a(b(a(a(a(x1))))) -> b(a(a(b(b(a(a(x1)))))))
      weak:
       a(a(a(a(a(x1))))) -> a(a(a(b(a(a(a(x1)))))))
       a(a(a(a(x1)))) -> a(a(b(a(a(x1)))))
       a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(x1)))))))
       a(a(x1)) -> b(x1)
       a(a(a(x1))) -> a(b(a(x1)))
       a(b(a(x1))) -> b(b(b(x1)))
       a(a(b(a(x1)))) -> a(b(b(a(b(x1)))))
       a(b(a(a(x1)))) -> b(a(b(b(a(x1)))))
       a(b(b(a(x1)))) -> b(b(b(b(b(x1)))))
       a(a(b(b(a(x1))))) -> a(b(b(b(a(b(b(x1)))))))
       a(b(a(b(a(x1))))) -> b(a(b(b(b(a(b(x1)))))))
       a(b(b(a(a(x1))))) -> b(b(a(b(b(b(a(x1)))))))
       a(b(b(b(a(x1))))) -> b(b(b(b(b(b(b(x1)))))))
     Matrix Interpretation Processor:
      dimension: 2
      interpretation:
                 [1 0]  
       [b](x0) = [0 0]x0,
       
                 [1 1]     [0]
       [a](x0) = [0 1]x0 + [1]
      orientation:
                           [1 1]     [3]    [1 0]     [2]                          
       a(a(a(b(a(x1))))) = [0 0]x1 + [3] >= [0 0]x1 + [2] = a(a(b(b(a(a(b(x1)))))))
       
                           [1 3]     [3]    [1 2]     [2]                          
       a(b(a(a(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 + [0] = b(a(a(b(b(a(a(x1)))))))
       
                           [1 5]     [10]    [1 3]     [6]                          
       a(a(a(a(a(x1))))) = [0 1]x1 + [5 ] >= [0 0]x1 + [3] = a(a(a(b(a(a(a(x1)))))))
       
                        [1 4]     [6]    [1 2]     [2]                    
       a(a(a(a(x1)))) = [0 1]x1 + [4] >= [0 0]x1 + [2] = a(a(b(a(a(x1)))))
       
                           [1 2]     [2]    [1 1]     [0]                          
       a(a(b(a(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 + [1] = a(b(a(b(a(b(a(x1)))))))
       
                  [1 2]     [1]    [1 0]          
       a(a(x1)) = [0 1]x1 + [2] >= [0 0]x1 = b(x1)
       
                     [1 3]     [3]    [1 1]     [0]              
       a(a(a(x1))) = [0 1]x1 + [3] >= [0 0]x1 + [1] = a(b(a(x1)))
       
                     [1 1]     [0]    [1 0]                
       a(b(a(x1))) = [0 0]x1 + [1] >= [0 0]x1 = b(b(b(x1)))
       
                        [1 1]     [1]    [1 0]     [0]                    
       a(a(b(a(x1)))) = [0 0]x1 + [2] >= [0 0]x1 + [1] = a(b(b(a(b(x1)))))
       
                        [1 2]     [1]    [1 1]                      
       a(b(a(a(x1)))) = [0 0]x1 + [1] >= [0 0]x1 = b(a(b(b(a(x1)))))
       
                        [1 1]     [0]    [1 0]                      
       a(b(b(a(x1)))) = [0 0]x1 + [1] >= [0 0]x1 = b(b(b(b(b(x1)))))
       
                           [1 1]     [1]    [1 0]     [0]                          
       a(a(b(b(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 + [1] = a(b(b(b(a(b(b(x1)))))))
       
                           [1 1]     [0]    [1 0]                            
       a(b(a(b(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 = b(a(b(b(b(a(b(x1)))))))
       
                           [1 2]     [1]    [1 1]                            
       a(b(b(a(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 = b(b(a(b(b(b(a(x1)))))))
       
                           [1 1]     [0]    [1 0]                            
       a(b(b(b(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 = b(b(b(b(b(b(b(x1)))))))
      problem:
       strict:
        
       weak:
        a(a(a(b(a(x1))))) -> a(a(b(b(a(a(b(x1)))))))
        a(b(a(a(a(x1))))) -> b(a(a(b(b(a(a(x1)))))))
        a(a(a(a(a(x1))))) -> a(a(a(b(a(a(a(x1)))))))
        a(a(a(a(x1)))) -> a(a(b(a(a(x1)))))
        a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(x1)))))))
        a(a(x1)) -> b(x1)
        a(a(a(x1))) -> a(b(a(x1)))
        a(b(a(x1))) -> b(b(b(x1)))
        a(a(b(a(x1)))) -> a(b(b(a(b(x1)))))
        a(b(a(a(x1)))) -> b(a(b(b(a(x1)))))
        a(b(b(a(x1)))) -> b(b(b(b(b(x1)))))
        a(a(b(b(a(x1))))) -> a(b(b(b(a(b(b(x1)))))))
        a(b(a(b(a(x1))))) -> b(a(b(b(b(a(b(x1)))))))
        a(b(b(a(a(x1))))) -> b(b(a(b(b(b(a(x1)))))))
        a(b(b(b(a(x1))))) -> b(b(b(b(b(b(b(x1)))))))
      Qed