YES(?,O(n^2))

Problem:
 app(id(),x) -> x
 app(plus(),0()) -> id()
 app(app(plus(),app(s(),x)),y) -> app(s(),app(app(plus(),x),y))

Proof:
 RT Transformation Processor:
  strict:
   app(id(),x) -> x
   app(plus(),0()) -> id()
   app(app(plus(),app(s(),x)),y) -> app(s(),app(app(plus(),x),y))
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   interpretation:
    [s] = 12,
    
    [0] = 16,
    
    [plus] = 4,
    
    [app](x0, x1) = x0 + x1 + 5,
    
    [id] = 8
   orientation:
    app(id(),x) = x + 13 >= x = x
    
    app(plus(),0()) = 25 >= 8 = id()
    
    app(app(plus(),app(s(),x)),y) = x + y + 31 >= x + y + 31 = app(s(),app(app(plus(),x),y))
   problem:
    strict:
     app(app(plus(),app(s(),x)),y) -> app(s(),app(app(plus(),x),y))
    weak:
     app(id(),x) -> x
     app(plus(),0()) -> id()
   Matrix Interpretation Processor:
    dimension: 2
    interpretation:
           [0]
     [s] = [0],
     
           [4 ]
     [0] = [13],
     
              [0]
     [plus] = [0],
     
                     [1 4]          [0]
     [app](x0, x1) = [0 1]x0 + x1 + [2],
     
            [0]
     [id] = [0]
    orientation:
                                     [1 4]        [16]    [1 4]        [8]                                
     app(app(plus(),app(s(),x)),y) = [0 1]x + y + [6 ] >= [0 1]x + y + [6] = app(s(),app(app(plus(),x),y))
     
                       [0]         
     app(id(),x) = x + [2] >= x = x
     
                       [4 ]    [0]       
     app(plus(),0()) = [15] >= [0] = id()
    problem:
     strict:
      
     weak:
      app(app(plus(),app(s(),x)),y) -> app(s(),app(app(plus(),x),y))
      app(id(),x) -> x
      app(plus(),0()) -> id()
    Qed