TRS:
 {       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)}
 POP* + Boolean Semantic Labelling:
  Normal positions:
  pi(rem_sl=1) = [1,2], pi(rem_sl=0) = [1], pi(f_sl=1) = [1,2], pi(f_sl=0) = [1,2], pi(norm_sl=1) = [1], pi(norm_sl=0) = [1]
  
Safe positions:
   pi(rem_sl=0) = [2], pi(g_sl=1) = [1,2], pi(g_sl=0) = [1,2], pi(s_sl=1) = [1], pi(s_sl=0) = [1]
  
Precedence:
   norm_sl=0 > s_sl=0, 
   norm_sl=0 > 0_sl=0, 
   f_sl=0 > g_sl=0, 
   f_sl=0 > nil_sl=0, 
   rem_sl=1 > rem_sl=0
   empty
  
Interpretation:
   0^(0):
    | 0
   norm^(1):
   0 | 0
   1 | 0
   nil^(0):
    | 0
   s^(1):
   0 | 0
   1 | 0
   g^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 0
   f^(2):
   00 | 0
   01 | 1
   10 | 0
   11 | 1
   rem^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 0
   
  
Labelling:
   0^(0):
    | 0
   norm^(1):
   0 | 0
   1 | 0
   nil^(0):
    | 0
   s^(1):
   0 | 0
   1 | 0
   g^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 0
   f^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 0
   rem^(2):
   00 | 1
   01 | 0
   10 | 0
   11 | 0
   
  
Labelled predicative System:
   {            norm_sl=0(nil_sl=0();) -> 0_sl=0(),
              norm_sl=0(g_sl=0(;x,y);) -> s_sl=0(;norm_sl=0(x;)),
              norm_sl=0(g_sl=0(;x,y);) -> s_sl=0(;norm_sl=0(x;)),
              norm_sl=0(g_sl=0(;x,y);) -> s_sl=0(;norm_sl=0(x;)),
              norm_sl=0(g_sl=0(;x,y);) -> s_sl=0(;norm_sl=0(x;)),
                 f_sl=0(x,nil_sl=0();) -> g_sl=0(;nil_sl=0(),x),
                 f_sl=0(x,nil_sl=0();) -> g_sl=0(;nil_sl=0(),x),
               f_sl=0(x,g_sl=0(;y,z);) -> g_sl=0(;f_sl=0(x,y;),z),
               f_sl=0(x,g_sl=0(;y,z);) -> g_sl=0(;f_sl=0(x,y;),z),
               f_sl=0(x,g_sl=0(;y,z);) -> g_sl=0(;f_sl=0(x,y;),z),
               f_sl=0(x,g_sl=0(;y,z);) -> g_sl=0(;f_sl=0(x,y;),z),
               f_sl=0(x,g_sl=0(;y,z);) -> g_sl=0(;f_sl=0(x,y;),z),
               f_sl=0(x,g_sl=0(;y,z);) -> g_sl=0(;f_sl=0(x,y;),z),
               f_sl=0(x,g_sl=0(;y,z);) -> g_sl=0(;f_sl=0(x,y;),z),
               f_sl=0(x,g_sl=0(;y,z);) -> g_sl=0(;f_sl=0(x,y;),z),
               rem_sl=1(nil_sl=0(),y;) -> nil_sl=0(),
                rem_sl=0(nil_sl=0();y) -> nil_sl=0(),
      rem_sl=1(g_sl=0(;x,y),0_sl=0();) -> g_sl=0(;x,y),
      rem_sl=1(g_sl=0(;x,y),0_sl=0();) -> g_sl=0(;x,y),
      rem_sl=1(g_sl=0(;x,y),0_sl=0();) -> g_sl=0(;x,y),
      rem_sl=1(g_sl=0(;x,y),0_sl=0();) -> g_sl=0(;x,y),
    rem_sl=1(g_sl=0(;x,y),s_sl=0(;z);) -> rem_sl=1(x,z;),
    rem_sl=1(g_sl=0(;x,y),s_sl=0(;z);) -> rem_sl=0(x;z),
    rem_sl=1(g_sl=0(;x,y),s_sl=0(;z);) -> rem_sl=1(x,z;),
    rem_sl=1(g_sl=0(;x,y),s_sl=0(;z);) -> rem_sl=0(x;z),
    rem_sl=1(g_sl=0(;x,y),s_sl=0(;z);) -> rem_sl=0(x;z),
    rem_sl=1(g_sl=0(;x,y),s_sl=0(;z);) -> rem_sl=0(x;z),
    rem_sl=1(g_sl=0(;x,y),s_sl=0(;z);) -> rem_sl=0(x;z),
    rem_sl=1(g_sl=0(;x,y),s_sl=0(;z);) -> rem_sl=0(x;z)}
  

  Qed