YES(?,O(n^3))

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

Proof:
 RT Transformation Processor:
  strict:
   a(a(x1)) -> b(a(b(x1)))
   a(a(a(x1))) -> a(b(a(b(a(x1)))))
   a(b(a(x1))) -> b(b(a(b(b(x1)))))
   a(a(a(a(x1)))) -> a(a(b(a(b(a(a(x1)))))))
   a(a(b(a(x1)))) -> a(b(b(a(b(a(b(x1)))))))
   a(b(a(a(x1)))) -> b(a(b(a(b(b(a(x1)))))))
   a(b(b(a(x1)))) -> b(b(b(a(b(b(b(x1)))))))
   a(a(a(a(a(x1))))) -> a(a(a(b(a(b(a(a(a(x1)))))))))
   a(a(a(b(a(x1))))) -> a(a(b(b(a(b(a(a(b(x1)))))))))
   a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(b(a(x1)))))))))
   a(a(b(b(a(x1))))) -> a(b(b(b(a(b(a(b(b(x1)))))))))
   a(b(a(a(a(x1))))) -> b(a(a(b(a(b(b(a(a(x1)))))))))
   a(b(a(b(a(x1))))) -> b(a(b(b(a(b(b(a(b(x1)))))))))
   a(b(b(a(a(x1))))) -> b(b(a(b(a(b(b(b(a(x1)))))))))
   a(b(b(b(a(x1))))) -> b(b(b(b(a(b(b(b(b(x1)))))))))
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   interpretation:
    [b](x0) = x0,
    
    [a](x0) = x0 + 1
   orientation:
    a(a(x1)) = x1 + 2 >= x1 + 1 = b(a(b(x1)))
    
    a(a(a(x1))) = x1 + 3 >= x1 + 3 = a(b(a(b(a(x1)))))
    
    a(b(a(x1))) = x1 + 2 >= x1 + 1 = b(b(a(b(b(x1)))))
    
    a(a(a(a(x1)))) = x1 + 4 >= x1 + 5 = a(a(b(a(b(a(a(x1)))))))
    
    a(a(b(a(x1)))) = x1 + 3 >= x1 + 3 = a(b(b(a(b(a(b(x1)))))))
    
    a(b(a(a(x1)))) = x1 + 3 >= x1 + 3 = b(a(b(a(b(b(a(x1)))))))
    
    a(b(b(a(x1)))) = x1 + 2 >= x1 + 1 = b(b(b(a(b(b(b(x1)))))))
    
    a(a(a(a(a(x1))))) = x1 + 5 >= x1 + 7 = a(a(a(b(a(b(a(a(a(x1)))))))))
    
    a(a(a(b(a(x1))))) = x1 + 4 >= x1 + 5 = a(a(b(b(a(b(a(a(b(x1)))))))))
    
    a(a(b(a(a(x1))))) = x1 + 4 >= x1 + 5 = a(b(a(b(a(b(a(b(a(x1)))))))))
    
    a(a(b(b(a(x1))))) = x1 + 3 >= x1 + 3 = a(b(b(b(a(b(a(b(b(x1)))))))))
    
    a(b(a(a(a(x1))))) = x1 + 4 >= x1 + 5 = b(a(a(b(a(b(b(a(a(x1)))))))))
    
    a(b(a(b(a(x1))))) = x1 + 3 >= x1 + 3 = b(a(b(b(a(b(b(a(b(x1)))))))))
    
    a(b(b(a(a(x1))))) = x1 + 3 >= x1 + 3 = b(b(a(b(a(b(b(b(a(x1)))))))))
    
    a(b(b(b(a(x1))))) = x1 + 2 >= x1 + 1 = b(b(b(b(a(b(b(b(b(x1)))))))))
   problem:
    strict:
     a(a(a(x1))) -> a(b(a(b(a(x1)))))
     a(a(a(a(x1)))) -> a(a(b(a(b(a(a(x1)))))))
     a(a(b(a(x1)))) -> a(b(b(a(b(a(b(x1)))))))
     a(b(a(a(x1)))) -> b(a(b(a(b(b(a(x1)))))))
     a(a(a(a(a(x1))))) -> a(a(a(b(a(b(a(a(a(x1)))))))))
     a(a(a(b(a(x1))))) -> a(a(b(b(a(b(a(a(b(x1)))))))))
     a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(b(a(x1)))))))))
     a(a(b(b(a(x1))))) -> a(b(b(b(a(b(a(b(b(x1)))))))))
     a(b(a(a(a(x1))))) -> b(a(a(b(a(b(b(a(a(x1)))))))))
     a(b(a(b(a(x1))))) -> b(a(b(b(a(b(b(a(b(x1)))))))))
     a(b(b(a(a(x1))))) -> b(b(a(b(a(b(b(b(a(x1)))))))))
    weak:
     a(a(x1)) -> b(a(b(x1)))
     a(b(a(x1))) -> b(b(a(b(b(x1)))))
     a(b(b(a(x1)))) -> b(b(b(a(b(b(b(x1)))))))
     a(b(b(b(a(x1))))) -> b(b(b(b(a(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 + [4]
    orientation:
                   [1 1]     [8]    [1 1]     [0]                    
     a(a(a(x1))) = [0 0]x1 + [4] >= [0 0]x1 + [4] = a(b(a(b(a(x1)))))
     
                      [1 1]     [12]    [1 1]     [8]                          
     a(a(a(a(x1)))) = [0 0]x1 + [4 ] >= [0 0]x1 + [4] = a(a(b(a(b(a(a(x1)))))))
     
                      [1 1]     [4]    [1 0]     [0]                          
     a(a(b(a(x1)))) = [0 0]x1 + [4] >= [0 0]x1 + [4] = a(b(b(a(b(a(b(x1)))))))
     
                      [1 1]     [4]    [1 1]                            
     a(b(a(a(x1)))) = [0 0]x1 + [4] >= [0 0]x1 = b(a(b(a(b(b(a(x1)))))))
     
                         [1 1]     [16]    [1 1]     [16]                                
     a(a(a(a(a(x1))))) = [0 0]x1 + [4 ] >= [0 0]x1 + [4 ] = a(a(a(b(a(b(a(a(a(x1)))))))))
     
                         [1 1]     [8]    [1 0]     [8]                                
     a(a(a(b(a(x1))))) = [0 0]x1 + [4] >= [0 0]x1 + [4] = a(a(b(b(a(b(a(a(b(x1)))))))))
     
                         [1 1]     [8]    [1 1]     [0]                                
     a(a(b(a(a(x1))))) = [0 0]x1 + [4] >= [0 0]x1 + [4] = a(b(a(b(a(b(a(b(a(x1)))))))))
     
                         [1 1]     [4]    [1 0]     [0]                                
     a(a(b(b(a(x1))))) = [0 0]x1 + [4] >= [0 0]x1 + [4] = a(b(b(b(a(b(a(b(b(x1)))))))))
     
                         [1 1]     [8]    [1 1]     [8]                                
     a(b(a(a(a(x1))))) = [0 0]x1 + [4] >= [0 0]x1 + [0] = b(a(a(b(a(b(b(a(a(x1)))))))))
     
                         [1 1]     [0]    [1 0]                                  
     a(b(a(b(a(x1))))) = [0 0]x1 + [4] >= [0 0]x1 = b(a(b(b(a(b(b(a(b(x1)))))))))
     
                         [1 1]     [4]    [1 1]                                  
     a(b(b(a(a(x1))))) = [0 0]x1 + [4] >= [0 0]x1 = b(b(a(b(a(b(b(b(a(x1)))))))))
     
                [1 1]     [4]    [1 0]                
     a(a(x1)) = [0 0]x1 + [4] >= [0 0]x1 = b(a(b(x1)))
     
                   [1 1]     [0]    [1 0]                      
     a(b(a(x1))) = [0 0]x1 + [4] >= [0 0]x1 = b(b(a(b(b(x1)))))
     
                      [1 1]     [0]    [1 0]                            
     a(b(b(a(x1)))) = [0 0]x1 + [4] >= [0 0]x1 = b(b(b(a(b(b(b(x1)))))))
     
                         [1 1]     [0]    [1 0]                                  
     a(b(b(b(a(x1))))) = [0 0]x1 + [4] >= [0 0]x1 = b(b(b(b(a(b(b(b(b(x1)))))))))
    problem:
     strict:
      a(a(a(a(a(x1))))) -> a(a(a(b(a(b(a(a(a(x1)))))))))
      a(a(a(b(a(x1))))) -> a(a(b(b(a(b(a(a(b(x1)))))))))
      a(b(a(a(a(x1))))) -> b(a(a(b(a(b(b(a(a(x1)))))))))
      a(b(a(b(a(x1))))) -> b(a(b(b(a(b(b(a(b(x1)))))))))
     weak:
      a(a(a(x1))) -> a(b(a(b(a(x1)))))
      a(a(a(a(x1)))) -> a(a(b(a(b(a(a(x1)))))))
      a(a(b(a(x1)))) -> a(b(b(a(b(a(b(x1)))))))
      a(b(a(a(x1)))) -> b(a(b(a(b(b(a(x1)))))))
      a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(b(a(x1)))))))))
      a(a(b(b(a(x1))))) -> a(b(b(b(a(b(a(b(b(x1)))))))))
      a(b(b(a(a(x1))))) -> b(b(a(b(a(b(b(b(a(x1)))))))))
      a(a(x1)) -> b(a(b(x1)))
      a(b(a(x1))) -> b(b(a(b(b(x1)))))
      a(b(b(a(x1)))) -> b(b(b(a(b(b(b(x1)))))))
      a(b(b(b(a(x1))))) -> b(b(b(b(a(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 + [2]
     orientation:
                          [1 5]     [20]    [1 3]     [12]                                
      a(a(a(a(a(x1))))) = [0 1]x1 + [10] >= [0 0]x1 + [6 ] = a(a(a(b(a(b(a(a(a(x1)))))))))
      
                          [1 1]     [6]    [1 0]     [4]                                
      a(a(a(b(a(x1))))) = [0 0]x1 + [6] >= [0 0]x1 + [4] = a(a(b(b(a(b(a(a(b(x1)))))))))
      
                          [1 3]     [6]    [1 2]     [4]                                
      a(b(a(a(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 + [0] = b(a(a(b(a(b(b(a(a(x1)))))))))
      
                          [1 1]     [0]    [1 0]                                  
      a(b(a(b(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 = b(a(b(b(a(b(b(a(b(x1)))))))))
      
                    [1 3]     [6]    [1 1]     [0]                    
      a(a(a(x1))) = [0 1]x1 + [6] >= [0 0]x1 + [2] = a(b(a(b(a(x1)))))
      
                       [1 4]     [12]    [1 2]     [4]                          
      a(a(a(a(x1)))) = [0 1]x1 + [8 ] >= [0 0]x1 + [4] = a(a(b(a(b(a(a(x1)))))))
      
                       [1 1]     [2]    [1 0]     [0]                          
      a(a(b(a(x1)))) = [0 0]x1 + [4] >= [0 0]x1 + [2] = a(b(b(a(b(a(b(x1)))))))
      
                       [1 2]     [2]    [1 1]                            
      a(b(a(a(x1)))) = [0 0]x1 + [2] >= [0 0]x1 = b(a(b(a(b(b(a(x1)))))))
      
                          [1 2]     [4]    [1 1]     [0]                                
      a(a(b(a(a(x1))))) = [0 0]x1 + [4] >= [0 0]x1 + [2] = a(b(a(b(a(b(a(b(a(x1)))))))))
      
                          [1 1]     [2]    [1 0]     [0]                                
      a(a(b(b(a(x1))))) = [0 0]x1 + [4] >= [0 0]x1 + [2] = a(b(b(b(a(b(a(b(b(x1)))))))))
      
                          [1 2]     [2]    [1 1]                                  
      a(b(b(a(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 = b(b(a(b(a(b(b(b(a(x1)))))))))
      
                 [1 2]     [2]    [1 0]                
      a(a(x1)) = [0 1]x1 + [4] >= [0 0]x1 = b(a(b(x1)))
      
                    [1 1]     [0]    [1 0]                      
      a(b(a(x1))) = [0 0]x1 + [2] >= [0 0]x1 = b(b(a(b(b(x1)))))
      
                       [1 1]     [0]    [1 0]                            
      a(b(b(a(x1)))) = [0 0]x1 + [2] >= [0 0]x1 = b(b(b(a(b(b(b(x1)))))))
      
                          [1 1]     [0]    [1 0]                                  
      a(b(b(b(a(x1))))) = [0 0]x1 + [2] >= [0 0]x1 = b(b(b(b(a(b(b(b(b(x1)))))))))
     problem:
      strict:
       a(b(a(b(a(x1))))) -> b(a(b(b(a(b(b(a(b(x1)))))))))
      weak:
       a(a(a(a(a(x1))))) -> a(a(a(b(a(b(a(a(a(x1)))))))))
       a(a(a(b(a(x1))))) -> a(a(b(b(a(b(a(a(b(x1)))))))))
       a(b(a(a(a(x1))))) -> b(a(a(b(a(b(b(a(a(x1)))))))))
       a(a(a(x1))) -> a(b(a(b(a(x1)))))
       a(a(a(a(x1)))) -> a(a(b(a(b(a(a(x1)))))))
       a(a(b(a(x1)))) -> a(b(b(a(b(a(b(x1)))))))
       a(b(a(a(x1)))) -> b(a(b(a(b(b(a(x1)))))))
       a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(b(a(x1)))))))))
       a(a(b(b(a(x1))))) -> a(b(b(b(a(b(a(b(b(x1)))))))))
       a(b(b(a(a(x1))))) -> b(b(a(b(a(b(b(b(a(x1)))))))))
       a(a(x1)) -> b(a(b(x1)))
       a(b(a(x1))) -> b(b(a(b(b(x1)))))
       a(b(b(a(x1)))) -> b(b(b(a(b(b(b(x1)))))))
       a(b(b(b(a(x1))))) -> b(b(b(b(a(b(b(b(b(x1)))))))))
     Matrix Interpretation Processor:
      dimension: 3
      interpretation:
                 [1 0 0]  
       [b](x0) = [0 0 1]x0
                 [0 0 0]  ,
       
                 [1 1 2]     [0]
       [a](x0) = [0 1 1]x0 + [0]
                 [0 0 0]     [1]
      orientation:
                           [1 1 2]     [2]    [1 0 1]     [0]                                
       a(b(a(b(a(x1))))) = [0 0 0]x1 + [1] >= [0 0 0]x1 + [1] = b(a(b(b(a(b(b(a(b(x1)))))))))
                           [0 0 0]     [1]    [0 0 0]     [0]                                
       
                           [1 5 6]     [14]    [1 3 4]     [14]                                
       a(a(a(a(a(x1))))) = [0 1 1]x1 + [4 ] >= [0 0 0]x1 + [3 ] = a(a(a(b(a(b(a(a(a(x1)))))))))
                           [0 0 0]     [1 ]    [0 0 0]     [1 ]                                
       
                           [1 1 2]     [8]    [1 0 2]     [5]                                
       a(a(a(b(a(x1))))) = [0 0 0]x1 + [3] >= [0 0 0]x1 + [1] = a(a(b(b(a(b(a(a(b(x1)))))))))
                           [0 0 0]     [1]    [0 0 0]     [1]                                
       
                           [1 3 4]     [6]    [1 2 3]     [6]                                
       a(b(a(a(a(x1))))) = [0 0 0]x1 + [1] >= [0 0 0]x1 + [1] = b(a(a(b(a(b(b(a(a(x1)))))))))
                           [0 0 0]     [1]    [0 0 0]     [0]                                
       
                     [1 3 4]     [5]    [1 1 2]     [2]                    
       a(a(a(x1))) = [0 1 1]x1 + [2] >= [0 0 0]x1 + [1] = a(b(a(b(a(x1)))))
                     [0 0 0]     [1]    [0 0 0]     [1]                    
       
                        [1 4 5]     [9]    [1 2 3]     [7]                          
       a(a(a(a(x1)))) = [0 1 1]x1 + [3] >= [0 0 0]x1 + [2] = a(a(b(a(b(a(a(x1)))))))
                        [0 0 0]     [1]    [0 0 0]     [1]                          
       
                        [1 1 2]     [4]    [1 0 1]     [1]                          
       a(a(b(a(x1)))) = [0 0 0]x1 + [2] >= [0 0 0]x1 + [0] = a(b(b(a(b(a(b(x1)))))))
                        [0 0 0]     [1]    [0 0 0]     [1]                          
       
                        [1 2 3]     [3]    [1 1 2]     [1]                          
       a(b(a(a(x1)))) = [0 0 0]x1 + [1] >= [0 0 0]x1 + [1] = b(a(b(a(b(b(a(x1)))))))
                        [0 0 0]     [1]    [0 0 0]     [0]                          
       
                           [1 2 3]     [6]    [1 1 2]     [4]                                
       a(a(b(a(a(x1))))) = [0 0 0]x1 + [2] >= [0 0 0]x1 + [1] = a(b(a(b(a(b(a(b(a(x1)))))))))
                           [0 0 0]     [1]    [0 0 0]     [1]                                
       
                           [1 1 2]     [2]    [1 0 0]     [1]                                
       a(a(b(b(a(x1))))) = [0 0 0]x1 + [1] >= [0 0 0]x1 + [0] = a(b(b(b(a(b(a(b(b(x1)))))))))
                           [0 0 0]     [1]    [0 0 0]     [1]                                
       
                           [1 2 3]     [2]    [1 1 2]     [1]                                
       a(b(b(a(a(x1))))) = [0 0 0]x1 + [0] >= [0 0 0]x1 + [0] = b(b(a(b(a(b(b(b(a(x1)))))))))
                           [0 0 0]     [1]    [0 0 0]     [0]                                
       
                  [1 2 3]     [2]    [1 0 1]     [0]              
       a(a(x1)) = [0 1 1]x1 + [1] >= [0 0 0]x1 + [1] = b(a(b(x1)))
                  [0 0 0]     [1]    [0 0 0]     [0]              
       
                     [1 1 2]     [1]    [1 0 0]                      
       a(b(a(x1))) = [0 0 0]x1 + [1] >= [0 0 0]x1 = b(b(a(b(b(x1)))))
                     [0 0 0]     [1]    [0 0 0]                      
       
                        [1 1 2]     [0]    [1 0 0]                            
       a(b(b(a(x1)))) = [0 0 0]x1 + [0] >= [0 0 0]x1 = b(b(b(a(b(b(b(x1)))))))
                        [0 0 0]     [1]    [0 0 0]                            
       
                           [1 1 2]     [0]    [1 0 0]                                  
       a(b(b(b(a(x1))))) = [0 0 0]x1 + [0] >= [0 0 0]x1 = b(b(b(b(a(b(b(b(b(x1)))))))))
                           [0 0 0]     [1]    [0 0 0]                                  
      problem:
       strict:
        
       weak:
        a(b(a(b(a(x1))))) -> b(a(b(b(a(b(b(a(b(x1)))))))))
        a(a(a(a(a(x1))))) -> a(a(a(b(a(b(a(a(a(x1)))))))))
        a(a(a(b(a(x1))))) -> a(a(b(b(a(b(a(a(b(x1)))))))))
        a(b(a(a(a(x1))))) -> b(a(a(b(a(b(b(a(a(x1)))))))))
        a(a(a(x1))) -> a(b(a(b(a(x1)))))
        a(a(a(a(x1)))) -> a(a(b(a(b(a(a(x1)))))))
        a(a(b(a(x1)))) -> a(b(b(a(b(a(b(x1)))))))
        a(b(a(a(x1)))) -> b(a(b(a(b(b(a(x1)))))))
        a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(b(a(x1)))))))))
        a(a(b(b(a(x1))))) -> a(b(b(b(a(b(a(b(b(x1)))))))))
        a(b(b(a(a(x1))))) -> b(b(a(b(a(b(b(b(a(x1)))))))))
        a(a(x1)) -> b(a(b(x1)))
        a(b(a(x1))) -> b(b(a(b(b(x1)))))
        a(b(b(a(x1)))) -> b(b(b(a(b(b(b(x1)))))))
        a(b(b(b(a(x1))))) -> b(b(b(b(a(b(b(b(b(x1)))))))))
      Qed