MAYBE

Problem:
 strict:
  min(x,0()) -> 0()
  min(0(),y) -> 0()
  min(s(x),s(y)) -> s(min(x,y))
  max(x,0()) -> x
  max(0(),y) -> y
  max(s(x),s(y)) -> s(max(x,y))
  -(x,0()) -> x
  -(s(x),s(y)) -> -(x,y)
  gcd(nil()) -> 0()
  gcd(cons(x,nil())) -> x
  gcd(cons(0(),y)) -> gcd(y)
  gcd(cons(x,cons(0(),y))) -> gcd(cons(x,y))
  gcd(cons(s(x),cons(s(y),z))) -> gcd(cons(-(max(x,y),min(x,y)),cons(s(min(x,y)),z)))
 weak:
  cons(x,cons(y,z)) -> cons(y,cons(x,z))

Proof:
 Open