YES(?,O(n^2))

Problem:
 +(0(),y) -> y
 +(s(x),y) -> s(+(x,y))
 +(s(x),y) -> +(x,s(y))

Proof:
 Matrix Interpretation Processor:
  dimension: 2
  interpretation:
                  [8]
   [s](x0) = x0 + [2],
   
                 [1 1]          [1]
   [+](x0, x1) = [0 1]x0 + x1 + [0],
   
         [1]
   [0] = [0]
  orientation:
                  [2]         
   +(0(),y) = y + [0] >= y = y
   
               [1 1]        [11]    [1 1]        [9]            
   +(s(x),y) = [0 1]x + y + [2 ] >= [0 1]x + y + [2] = s(+(x,y))
   
               [1 1]        [11]    [1 1]        [9]            
   +(s(x),y) = [0 1]x + y + [2 ] >= [0 1]x + y + [2] = +(x,s(y))
  problem:
   
  Qed