YES(?,O(n^2))

Problem:
 app(app(plus(),0()),y) -> y
 app(app(plus(),app(s(),x)),y) -> app(s(),app(app(plus(),x),y))
 app(app(app(curry(),f),x),y) -> app(app(f,x),y)
 add() -> app(curry(),plus())

Proof:
 RT Transformation Processor:
  strict:
   app(app(plus(),0()),y) -> y
   app(app(plus(),app(s(),x)),y) -> app(s(),app(app(plus(),x),y))
   app(app(app(curry(),f),x),y) -> app(app(f,x),y)
   add() -> app(curry(),plus())
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   interpretation:
    [add] = 17,
    
    [curry] = 12,
    
    [s] = 17,
    
    [app](x0, x1) = x0 + x1,
    
    [0] = 16,
    
    [plus] = 4
   orientation:
    app(app(plus(),0()),y) = y + 20 >= y = y
    
    app(app(plus(),app(s(),x)),y) = x + y + 21 >= x + y + 21 = app(s(),app(app(plus(),x),y))
    
    app(app(app(curry(),f),x),y) = f + x + y + 12 >= f + x + y = app(app(f,x),y)
    
    add() = 17 >= 16 = app(curry(),plus())
   problem:
    strict:
     app(app(plus(),app(s(),x)),y) -> app(s(),app(app(plus(),x),y))
    weak:
     app(app(plus(),0()),y) -> y
     app(app(app(curry(),f),x),y) -> app(app(f,x),y)
     add() -> app(curry(),plus())
   Matrix Interpretation Processor:
    dimension: 2
    interpretation:
             [8 ]
     [add] = [10],
     
               [2]
     [curry] = [0],
     
           [9]
     [s] = [1],
     
                     [1 1]          [0]
     [app](x0, x1) = [0 1]x0 + x1 + [4],
     
           [0]
     [0] = [0],
     
              [0]
     [plus] = [5]
    orientation:
                                     [1 1]        [29]    [1 1]        [24]                                
     app(app(plus(),app(s(),x)),y) = [0 1]x + y + [18] >= [0 1]x + y + [18] = app(s(),app(app(plus(),x),y))
     
                                  [14]         
     app(app(plus(),0()),y) = y + [13] >= y = y
     
                                    [1 2]    [1 1]        [14]    [1 2]    [1 1]        [4]                  
     app(app(app(curry(),f),x),y) = [0 1]f + [0 1]x + y + [12] >= [0 1]f + [0 1]x + y + [8] = app(app(f,x),y)
     
             [8 ]    [2]                      
     add() = [10] >= [9] = app(curry(),plus())
    problem:
     strict:
      
     weak:
      app(app(plus(),app(s(),x)),y) -> app(s(),app(app(plus(),x),y))
      app(app(plus(),0()),y) -> y
      app(app(app(curry(),f),x),y) -> app(app(f,x),y)
      add() -> app(curry(),plus())
    Qed