MAYBE
* Step 1: Failure MAYBE
  + Considered Problem:
      - Strict TRS:
          bool2Nat(False()) -> 0()
          bool2Nat(True()) -> S(0())
          e1(a,b,res,t) -> e2(a,b,res,<(a,b))
          e2(a,b,res,False()) -> False()
          e2(a,b,res,True()) -> e3(a,b,res,True())
          e3(a,b,res,t) -> e4(a,b,res,<(b,a))
          e4(a,b,res,False()) -> False()
          e4(a,b,res,True()) -> True()
          e5(a,b,res,t) -> True()
          e6(a,b,res,t) -> False()
          e7(a,b,res,t) -> False()
          e8(a,b,res,t) -> res
          equal0(a,b) -> e1(a,b,False(),False())
          gcd(x,y) -> l1(x,y,0(),False(),False(),False())
          help1(0()) -> False()
          help1(S(0())) -> False()
          help1(S(S(x))) -> True()
          l1(x,y,res,tmp,mtmp,t) -> l2(x,y,res,tmp,mtmp,False())
          l10(x,y,res,tmp,mtmp,t) -> l11(x,y,res,tmp,mtmp,<(x,y))
          l11(x,y,res,tmp,mtmp,False()) -> l14(x,y,res,tmp,mtmp,False())
          l11(x,y,res,tmp,mtmp,True()) -> l12(x,y,res,tmp,mtmp,True())
          l12(x,y,res,tmp,mtmp,t) -> l13(x,y,res,tmp,monus(x,y),t)
          l13(x,y,res,tmp,False(),t) -> l16(x,y,gcd(0(),y),tmp,False(),t)
          l13(x,y,res,tmp,True(),t) -> l16(x,y,gcd(S(0()),y),tmp,True(),t)
          l14(x,y,res,tmp,mtmp,t) -> l15(x,y,res,tmp,monus(x,y),t)
          l15(x,y,res,tmp,False(),t) -> l16(x,y,gcd(y,0()),tmp,False(),t)
          l15(x,y,res,tmp,True(),t) -> l16(x,y,gcd(y,S(0())),tmp,True(),t)
          l16(x,y,res,tmp,mtmp,t) -> res
          l2(x,y,res,tmp,mtmp,False()) -> l3(x,y,res,tmp,mtmp,False())
          l2(x,y,res,tmp,mtmp,True()) -> res
          l3(x,y,res,tmp,mtmp,t) -> l4(x,y,0(),tmp,mtmp,t)
          l4(x',x,res,tmp,mtmp,t) -> l5(x',x,res,tmp,mtmp,False())
          l5(x,y,res,tmp,mtmp,False()) -> l7(x,y,res,tmp,mtmp,False())
          l5(x,y,res,tmp,mtmp,True()) -> 0()
          l6(x,y,res,tmp,mtmp,t) -> 0()
          l7(x,y,res,tmp,mtmp,t) -> l8(x,y,res,equal0(x,y),mtmp,t)
          l8(res,y,res',True(),mtmp,t) -> res
          l8(x,y,res,False(),mtmp,t) -> l10(x,y,res,False(),mtmp,t)
          l9(res,y,res',tmp,mtmp,t) -> res
          m1(a,x,res,t) -> m2(a,x,res,False())
          m2(a,b,res,False()) -> m4(a,b,res,False())
          m2(0(),b,res,True()) -> False()
          m2(S(0()),b,res,True()) -> False()
          m2(S(S(x)),b,res,True()) -> True()
          m3(0(),b,res,t) -> False()
          m3(S(0()),b,res,t) -> False()
          m3(S(S(x)),b,res,t) -> True()
          m4(S(x'),S(x),res,t) -> m5(S(x'),S(x),monus(x',x),t)
          m5(a,b,res,t) -> res
          monus(a,b) -> m1(a,b,False(),False())
      - Weak TRS:
          <(x,0()) -> False()
          <(0(),S(y)) -> True()
          <(S(x),S(y)) -> <(x,y)
      - Signature:
          {</2,bool2Nat/1,e1/4,e2/4,e3/4,e4/4,e5/4,e6/4,e7/4,e8/4,equal0/2,gcd/2,help1/1,l1/6,l10/6,l11/6,l12/6,l13/6
          ,l14/6,l15/6,l16/6,l2/6,l3/6,l4/6,l5/6,l6/6,l7/6,l8/6,l9/6,m1/4,m2/4,m3/4,m4/4,m5/4,monus/2} / {0/0,False/0
          ,S/1,True/0}
      - Obligation:
          innermost runtime complexity wrt. defined symbols {<,bool2Nat,e1,e2,e3,e4,e5,e6,e7,e8,equal0,gcd,help1,l1
          ,l10,l11,l12,l13,l14,l15,l16,l2,l3,l4,l5,l6,l7,l8,l9,m1,m2,m3,m4,m5,monus} and constructors {0,False,S,True}
  + Applied Processor:
      NaturalPI {shape = Mixed 3, restrict = NoRestrict, uargs = UArgs, urules = URules, selector = Nothing}
  + Details:
      Incompatible
MAYBE