YES

Problem:
 le(0(),y) -> true()
 le(s(x),0()) -> false()
 le(s(x),s(y)) -> le(x,y)
 pred(s(x)) -> x
 minus(x,0()) -> x
 minus(x,s(y)) -> pred(minus(x,y))
 gcd(0(),y) -> y
 gcd(s(x),0()) -> s(x)
 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y))
 if_gcd(true(),s(x),s(y)) -> gcd(minus(x,y),s(y))
 if_gcd(false(),s(x),s(y)) -> gcd(minus(y,x),s(x))

Proof:
 DP Processor:
  DPs:
   le#(s(x),s(y)) -> le#(x,y)
   minus#(x,s(y)) -> minus#(x,y)
   minus#(x,s(y)) -> pred#(minus(x,y))
   gcd#(s(x),s(y)) -> le#(y,x)
   gcd#(s(x),s(y)) -> if_gcd#(le(y,x),s(x),s(y))
   if_gcd#(true(),s(x),s(y)) -> minus#(x,y)
   if_gcd#(true(),s(x),s(y)) -> gcd#(minus(x,y),s(y))
   if_gcd#(false(),s(x),s(y)) -> minus#(y,x)
   if_gcd#(false(),s(x),s(y)) -> gcd#(minus(y,x),s(x))
  TRS:
   le(0(),y) -> true()
   le(s(x),0()) -> false()
   le(s(x),s(y)) -> le(x,y)
   pred(s(x)) -> x
   minus(x,0()) -> x
   minus(x,s(y)) -> pred(minus(x,y))
   gcd(0(),y) -> y
   gcd(s(x),0()) -> s(x)
   gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y))
   if_gcd(true(),s(x),s(y)) -> gcd(minus(x,y),s(y))
   if_gcd(false(),s(x),s(y)) -> gcd(minus(y,x),s(x))
  KBO Processor:
   argument filtering:
    pi(0) = []
    pi(le) = []
    pi(true) = []
    pi(s) = [0]
    pi(false) = []
    pi(pred) = 0
    pi(minus) = 0
    pi(gcd) = [0,1]
    pi(if_gcd) = [1,2]
    pi(le#) = 0
    pi(pred#) = []
    pi(minus#) = 1
    pi(gcd#) = [0,1]
    pi(if_gcd#) = [1,2]
   weight function:
    w0 = 1
    w(minus#) = w(pred#) = w(le#) = w(minus) = w(false) = w(s) = w(true) = w(
    le) = w(0) = 1
    w(if_gcd#) = w(gcd#) = w(if_gcd) = w(gcd) = w(pred) = 0
   precedence:
    gcd# ~ minus# ~ pred# ~ le# ~ s ~ 0 > gcd ~ le > if_gcd# ~ if_gcd ~ minus ~ pred ~ false ~ true
   problem:
    DPs:
     
    TRS:
     le(0(),y) -> true()
     le(s(x),0()) -> false()
     le(s(x),s(y)) -> le(x,y)
     pred(s(x)) -> x
     minus(x,0()) -> x
     minus(x,s(y)) -> pred(minus(x,y))
     gcd(0(),y) -> y
     gcd(s(x),0()) -> s(x)
     gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y))
     if_gcd(true(),s(x),s(y)) -> gcd(minus(x,y),s(y))
     if_gcd(false(),s(x),s(y)) -> gcd(minus(y,x),s(x))
   Qed