YES

Problem:
 norm(nil()) -> 0()
 norm(g(x,y)) -> s(norm(x))
 f(x,nil()) -> g(nil(),x)
 f(x,g(y,z)) -> g(f(x,y),z)
 rem(nil(),y) -> nil()
 rem(g(x,y),0()) -> g(x,y)
 rem(g(x,y),s(z)) -> rem(x,z)

Proof:
 Matrix Interpretation Processor: dim=1
  
  interpretation:
   [s](x0) = x0,
   
   [norm](x0) = x0 + 2,
   
   [g](x0, x1) = x0 + 4x1 + 3,
   
   [f](x0, x1) = 4x0 + 4x1 + 3,
   
   [nil] = 0,
   
   [rem](x0, x1) = 4x0 + x1 + 4,
   
   [0] = 0
  orientation:
   norm(nil()) = 2 >= 0 = 0()
   
   norm(g(x,y)) = x + 4y + 5 >= x + 2 = s(norm(x))
   
   f(x,nil()) = 4x + 3 >= 4x + 3 = g(nil(),x)
   
   f(x,g(y,z)) = 4x + 4y + 16z + 15 >= 4x + 4y + 4z + 6 = g(f(x,y),z)
   
   rem(nil(),y) = y + 4 >= 0 = nil()
   
   rem(g(x,y),0()) = 4x + 16y + 16 >= x + 4y + 3 = g(x,y)
   
   rem(g(x,y),s(z)) = 4x + 16y + z + 16 >= 4x + z + 4 = rem(x,z)
  problem:
   f(x,nil()) -> g(nil(),x)
  Matrix Interpretation Processor: dim=3
   
   interpretation:
                  [1 0 0]     [1 0 0]  
    [g](x0, x1) = [0 0 0]x0 + [0 0 0]x1
                  [0 0 0]     [0 0 0]  ,
    
                  [1 0 0]     [1 0 0]     [1]
    [f](x0, x1) = [0 0 0]x0 + [0 0 0]x1 + [0]
                  [0 0 0]     [0 0 0]     [0],
    
            [0]
    [nil] = [0]
            [0]
   orientation:
                 [1 0 0]    [1]    [1 0 0]              
    f(x,nil()) = [0 0 0]x + [0] >= [0 0 0]x = g(nil(),x)
                 [0 0 0]    [0]    [0 0 0]              
   problem:
    
   Qed