YES(?,O(n^2))

Problem:
 q0(a(x1)) -> x(q1(x1))
 q1(a(x1)) -> a(q1(x1))
 q1(y(x1)) -> y(q1(x1))
 a(q1(b(x1))) -> q2(a(y(x1)))
 a(q2(a(x1))) -> q2(a(a(x1)))
 a(q2(y(x1))) -> q2(a(y(x1)))
 y(q1(b(x1))) -> q2(y(y(x1)))
 y(q2(a(x1))) -> q2(y(a(x1)))
 y(q2(y(x1))) -> q2(y(y(x1)))
 q2(x(x1)) -> x(q0(x1))
 q0(y(x1)) -> y(q3(x1))
 q3(y(x1)) -> y(q3(x1))
 q3(bl(x1)) -> bl(q4(x1))

Proof:
 Matrix Interpretation Processor:
  dimension: 2
  interpretation:
              [1 2]     [1]
   [q4](x0) = [0 0]x0 + [0],
   
              [1 8]     [3]
   [bl](x0) = [0 0]x0 + [0],
   
              [1 1]     [4]
   [q3](x0) = [0 1]x0 + [2],
   
              [1 1]     [5 ]
   [q2](x0) = [0 1]x0 + [10],
   
             [1 9]     [0 ]
   [b](x0) = [0 1]x0 + [13],
   
             [1 1]     [0]
   [y](x0) = [0 1]x0 + [8],
   
                  [1]
   [x](x0) = x0 + [1],
   
              [1 1]     [0]
   [q1](x0) = [0 1]x0 + [5],
   
              [1 1]     [1]
   [q0](x0) = [0 1]x0 + [2],
   
             [1 1]     [0]
   [a](x0) = [0 1]x0 + [6]
  orientation:
               [1 2]     [7]    [1 1]     [1]            
   q0(a(x1)) = [0 1]x1 + [8] >= [0 1]x1 + [6] = x(q1(x1))
   
               [1 2]     [6 ]    [1 2]     [5 ]            
   q1(a(x1)) = [0 1]x1 + [11] >= [0 1]x1 + [11] = a(q1(x1))
   
               [1 2]     [8 ]    [1 2]     [5 ]            
   q1(y(x1)) = [0 1]x1 + [13] >= [0 1]x1 + [13] = y(q1(x1))
   
                  [1  11]     [31]    [1 3]     [27]               
   a(q1(b(x1))) = [0  1 ]x1 + [24] >= [0 1]x1 + [24] = q2(a(y(x1)))
   
                  [1 3]     [27]    [1 3]     [23]               
   a(q2(a(x1))) = [0 1]x1 + [22] >= [0 1]x1 + [22] = q2(a(a(x1)))
   
                  [1 3]     [31]    [1 3]     [27]               
   a(q2(y(x1))) = [0 1]x1 + [24] >= [0 1]x1 + [24] = q2(a(y(x1)))
   
                  [1  11]     [31]    [1 3]     [29]               
   y(q1(b(x1))) = [0  1 ]x1 + [26] >= [0 1]x1 + [26] = q2(y(y(x1)))
   
                  [1 3]     [27]    [1 3]     [25]               
   y(q2(a(x1))) = [0 1]x1 + [24] >= [0 1]x1 + [24] = q2(y(a(x1)))
   
                  [1 3]     [31]    [1 3]     [29]               
   y(q2(y(x1))) = [0 1]x1 + [26] >= [0 1]x1 + [26] = q2(y(y(x1)))
   
               [1 1]     [7 ]    [1 1]     [2]            
   q2(x(x1)) = [0 1]x1 + [11] >= [0 1]x1 + [3] = x(q0(x1))
   
               [1 2]     [9 ]    [1 2]     [6 ]            
   q0(y(x1)) = [0 1]x1 + [10] >= [0 1]x1 + [10] = y(q3(x1))
   
               [1 2]     [12]    [1 2]     [6 ]            
   q3(y(x1)) = [0 1]x1 + [10] >= [0 1]x1 + [10] = y(q3(x1))
   
                [1 8]     [7]    [1 2]     [4]             
   q3(bl(x1)) = [0 0]x1 + [2] >= [0 0]x1 + [0] = bl(q4(x1))
  problem:
   
  Qed