TRS:
 {    gcd(x, 0()) -> x,
      gcd(0(), y) -> y,
  gcd(s(x), s(y)) -> if(<(x, y), gcd(s(x), -(y, x)), gcd(-(x, y), s(y)))}
 POP* + Boolean Semantic Labelling:
  Normal positions:
  pi(gcd_sl=1) = [1,2]
  
Safe positions:
   pi(-_sl=1) = [1,2], pi(-_sl=0) = [1,2], pi(s_sl=1) = [1], pi(s_sl=0) = [1], pi(<_sl=1) = [1,2], pi(<_sl=0) = [1,2], pi(if_sl=1) = [1,2,3], pi(if_sl=0) = [1,2,3], pi(gcd_sl=0) = [1,2]
  
Precedence:
   gcd_sl=1 > gcd_sl=0, 
   gcd_sl=1 > if_sl=0, 
   gcd_sl=1 > <_sl=0, 
   gcd_sl=1 > -_sl=0
   empty
  
Interpretation:
   gcd^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 1
   0^(0):
    | 1
   if^(3):
   000 | 1
   001 | 0
   010 | 0
   011 | 0
   100 | 1
   101 | 0
   110 | 0
   111 | 0
   <^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 1
   s^(1):
   0 | 1
   1 | 1
   -^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 0
   
  
Labelling:
   gcd^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 1
   0^(0):
    | 0
   if^(3):
   000 | 0
   001 | 0
   010 | 0
   011 | 0
   100 | 0
   101 | 0
   110 | 0
   111 | 0
   <^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 0
   s^(1):
   0 | 0
   1 | 0
   -^(2):
   00 | 0
   01 | 0
   10 | 0
   11 | 0
   
  
Labelled predicative System:
   {           gcd_sl=0(;x,0_sl=0()) -> x,
               gcd_sl=1(x,0_sl=0();) -> x,
               gcd_sl=0(;0_sl=0(),y) -> y,
               gcd_sl=1(0_sl=0(),y;) -> y,
    gcd_sl=1(s_sl=0(;x),s_sl=0(;y);) -> if_sl=0(;<_sl=0(;x,y),gcd_sl=0(;s_sl=0(;x),-_sl=0(;y,x)),gcd_sl=0(;-_sl=0(;x,y),s_sl=0(;y))),
    gcd_sl=1(s_sl=0(;x),s_sl=0(;y);) -> if_sl=0(;<_sl=0(;x,y),gcd_sl=0(;s_sl=0(;x),-_sl=0(;y,x)),gcd_sl=0(;-_sl=0(;x,y),s_sl=0(;y))),
    gcd_sl=1(s_sl=0(;x),s_sl=0(;y);) -> if_sl=0(;<_sl=0(;x,y),gcd_sl=0(;s_sl=0(;x),-_sl=0(;y,x)),gcd_sl=0(;-_sl=0(;x,y),s_sl=0(;y))),
    gcd_sl=1(s_sl=0(;x),s_sl=0(;y);) -> if_sl=0(;<_sl=0(;x,y),gcd_sl=0(;s_sl=0(;x),-_sl=0(;y,x)),gcd_sl=0(;-_sl=0(;x,y),s_sl=0(;y)))}
  

  Qed