YES(?,O(n^2))

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

Proof:
 RT Transformation Processor:
  strict:
   +(x,0()) -> x
   +(x,s(y)) -> s(+(x,y))
   +(0(),s(y)) -> s(y)
   s(+(0(),y)) -> s(y)
  weak:
   
  Bounds Processor:
   bound: 0
   enrichment: match-rt
   automaton:
    final states: {4,5}
    transitions:
     +0(4,4) -> 4*
     +0(5,5) -> 4*
     +0(4,5) -> 4*
     +0(5,4) -> 4*
     00() -> 5*
     s0(5) -> 4*
     s0(4) -> 4*
     5 -> 4*
   problem:
    strict:
     +(x,s(y)) -> s(+(x,y))
     +(0(),s(y)) -> s(y)
     s(+(0(),y)) -> s(y)
    weak:
     +(x,0()) -> x
   Matrix Interpretation Processor:
    dimension: 1
    interpretation:
     [s](x0) = x0,
     
     [+](x0, x1) = x0 + x1 + 31,
     
     [0] = 8
    orientation:
     +(x,s(y)) = x + y + 31 >= x + y + 31 = s(+(x,y))
     
     +(0(),s(y)) = y + 39 >= y = s(y)
     
     s(+(0(),y)) = y + 39 >= y = s(y)
     
     +(x,0()) = x + 39 >= x = x
    problem:
     strict:
      +(x,s(y)) -> s(+(x,y))
     weak:
      +(0(),s(y)) -> s(y)
      s(+(0(),y)) -> s(y)
      +(x,0()) -> x
    Matrix Interpretation Processor:
     dimension: 2
     interpretation:
                     [3]
      [s](x0) = x0 + [2],
      
                    [1 8]     [1 4]  
      [+](x0, x1) = [0 1]x0 + [0 1]x1,
      
            [5]
      [0] = [0]
     orientation:
                  [1 8]    [1 4]    [11]    [1 8]    [1 4]    [3]            
      +(x,s(y)) = [0 1]x + [0 1]y + [2 ] >= [0 1]x + [0 1]y + [2] = s(+(x,y))
      
                    [1 4]    [16]        [3]       
      +(0(),s(y)) = [0 1]y + [2 ] >= y + [2] = s(y)
      
                    [1 4]    [8]        [3]       
      s(+(0(),y)) = [0 1]y + [2] >= y + [2] = s(y)
      
                 [1 8]    [5]         
      +(x,0()) = [0 1]x + [0] >= x = x
     problem:
      strict:
       
      weak:
       +(x,s(y)) -> s(+(x,y))
       +(0(),s(y)) -> s(y)
       s(+(0(),y)) -> s(y)
       +(x,0()) -> x
     Qed