TRS:
 {f(0(), 1(), x) -> f(g(x), g(x), x),
   f(g(x), y, z) -> g(f(x, y, z)),
   f(x, g(y), z) -> g(f(x, y, z)),
   f(x, y, g(z)) -> g(f(x, y, z))}
 POP* + Boolean Semantic Labelling:
  Normal positions:
  pi(f_sl=1) = [1,2,3], pi(f_sl=0) = [1,2,3]
  
Safe positions:
   pi(g_sl=1) = [1], pi(g_sl=0) = [1]
  
Precedence:
   f_sl=1 > f_sl=0, 
   f_sl=1 > g_sl=0, 
   f_sl=1 > g_sl=1, 
   f_sl=0 > g_sl=1
   empty
  
Interpretation:
   f^(3):
   000 | 0
   001 | 0
   010 | 0
   011 | 0
   100 | 0
   101 | 0
   110 | 0
   111 | 0
   g^(1):
   0 | 0
   1 | 1
   0^(0):
    | 1
   1^(0):
    | 0
   
  
Labelling:
   f^(3):
   000 | 0
   001 | 0
   010 | 0
   011 | 0
   100 | 1
   101 | 1
   110 | 0
   111 | 0
   g^(1):
   0 | 1
   1 | 0
   0^(0):
    | 0
   1^(0):
    | 0
   
  
Labelled predicative System:
   {f_sl=1(0_sl=0(),1_sl=0(),x;) -> f_sl=0(g_sl=1(;x),g_sl=1(;x),x;),
    f_sl=1(0_sl=0(),1_sl=0(),x;) -> f_sl=0(g_sl=0(;x),g_sl=0(;x),x;),
         f_sl=0(g_sl=1(;x),y,z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(g_sl=1(;x),y,z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(g_sl=1(;x),y,z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(g_sl=1(;x),y,z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=1(g_sl=0(;x),y,z;) -> g_sl=1(;f_sl=1(x,y,z;)),
         f_sl=1(g_sl=0(;x),y,z;) -> g_sl=1(;f_sl=1(x,y,z;)),
         f_sl=0(g_sl=0(;x),y,z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(g_sl=0(;x),y,z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(x,g_sl=1(;y),z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(x,g_sl=1(;y),z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(x,g_sl=0(;y),z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(x,g_sl=0(;y),z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=1(x,g_sl=1(;y),z;) -> g_sl=1(;f_sl=1(x,y,z;)),
         f_sl=1(x,g_sl=1(;y),z;) -> g_sl=1(;f_sl=1(x,y,z;)),
         f_sl=0(x,g_sl=0(;y),z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(x,g_sl=0(;y),z;) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(x,y,g_sl=1(;z);) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(x,y,g_sl=0(;z);) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(x,y,g_sl=1(;z);) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(x,y,g_sl=0(;z);) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=1(x,y,g_sl=1(;z);) -> g_sl=1(;f_sl=1(x,y,z;)),
         f_sl=1(x,y,g_sl=0(;z);) -> g_sl=1(;f_sl=1(x,y,z;)),
         f_sl=0(x,y,g_sl=1(;z);) -> g_sl=1(;f_sl=0(x,y,z;)),
         f_sl=0(x,y,g_sl=0(;z);) -> g_sl=1(;f_sl=0(x,y,z;))}
  

  Qed