TRS:
 {         a__f(0()) -> cons(0(), f(s(0()))),
        a__f(s(0())) -> a__f(a__p(s(0()))),
        a__p(s(0())) -> 0(),
          mark(f(X)) -> a__f(mark(X)),
          mark(p(X)) -> a__p(mark(X)),
           mark(0()) -> 0(),
  mark(cons(X1, X2)) -> cons(mark(X1), X2),
          mark(s(X)) -> s(mark(X)),
             a__f(X) -> f(X),
             a__p(X) -> p(X)}
 POP* + Boolean Semantic Labelling:
  Normal positions:
  pi(mark_sl=1) = [1], pi(mark_sl=0) = [1], pi(a__p_sl=0) = [1]
  
Safe positions:
   pi(p_sl=1) = [1], pi(p_sl=0) = [1], pi(a__p_sl=1) = [1], pi(a__f_sl=1) = [1], pi(a__f_sl=0) = [1], pi(s_sl=1) = [1], pi(s_sl=0) = [1], pi(f_sl=1) = [1], pi(f_sl=0) = [1], pi(cons_sl=1) = [1,2], pi(cons_sl=0) = [1,2]
  
Precedence:
   mark_sl=0 > cons_sl=0, 
   mark_sl=0 > s_sl=0, 
   mark_sl=0 > a__f_sl=0, 
   mark_sl=0 > a__f_sl=1, 
   mark_sl=0 > a__p_sl=1, 
   a__f_sl=1 > cons_sl=0, 
   a__f_sl=1 > 0_sl=0, 
   a__f_sl=1 > f_sl=0, 
   a__f_sl=1 > s_sl=0, 
   a__f_sl=0 > a__p_sl=1, 
   a__f_sl=0 > a__f_sl=1, 
   a__f_sl=0 > s_sl=0, 
   a__f_sl=0 > f_sl=0, 
   a__f_sl=0 > 0_sl=0, 
   a__p_sl=1 > p_sl=0
   empty
  
Interpretation:
   cons^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 0
   0^(0):
    | 1
   f^(1):
   0 | 0
   1 | 0
   s^(1):
   0 | 0
   1 | 0
   a__f^(1):
   0 | 0
   1 | 0
   a__p^(1):
   0 | 1
   1 | 0
   mark^(1):
   0 | 0
   1 | 1
   p^(1):
   0 | 1
   1 | 0
   
  
Labelling:
   cons^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 0
   0^(0):
    | 0
   f^(1):
   0 | 0
   1 | 0
   s^(1):
   0 | 0
   1 | 0
   a__f^(1):
   0 | 0
   1 | 1
   a__p^(1):
   0 | 1
   1 | 1
   mark^(1):
   0 | 0
   1 | 0
   p^(1):
   0 | 0
   1 | 0
   
  
Labelled predicative System:
   {         a__f_sl=1(;0_sl=0()) -> cons_sl=0(;0_sl=0(),f_sl=0(;s_sl=0(;0_sl=0()))),
    a__f_sl=0(;s_sl=0(;0_sl=0())) -> a__f_sl=1(;a__p_sl=1(;s_sl=0(;0_sl=0()))),
    a__p_sl=1(;s_sl=0(;0_sl=0())) -> 0_sl=0(),
           mark_sl=0(f_sl=0(;X);) -> a__f_sl=0(;mark_sl=0(X;)),
           mark_sl=0(f_sl=0(;X);) -> a__f_sl=1(;mark_sl=0(X;)),
           mark_sl=0(p_sl=0(;X);) -> a__p_sl=1(;mark_sl=0(X;)),
           mark_sl=0(p_sl=0(;X);) -> a__p_sl=1(;mark_sl=0(X;)),
             mark_sl=0(0_sl=0();) -> 0_sl=0(),
    mark_sl=0(cons_sl=0(;X1,X2);) -> cons_sl=0(;mark_sl=0(X1;),X2),
    mark_sl=0(cons_sl=0(;X1,X2);) -> cons_sl=0(;mark_sl=0(X1;),X2),
    mark_sl=0(cons_sl=0(;X1,X2);) -> cons_sl=0(;mark_sl=0(X1;),X2),
    mark_sl=0(cons_sl=0(;X1,X2);) -> cons_sl=0(;mark_sl=0(X1;),X2),
           mark_sl=0(s_sl=0(;X);) -> s_sl=0(;mark_sl=0(X;)),
           mark_sl=0(s_sl=0(;X);) -> s_sl=0(;mark_sl=0(X;)),
                    a__f_sl=0(;X) -> f_sl=0(;X),
                    a__f_sl=1(;X) -> f_sl=0(;X),
                    a__p_sl=1(;X) -> p_sl=0(;X),
                    a__p_sl=1(;X) -> p_sl=0(;X)}
  

  Qed