MAYBE
* Step 1: Failure MAYBE
  + Considered Problem:
      - Strict TRS:
          addNat#2(0(),x16) -> x16
          addNat#2(S(x4),x2) -> S(addNat#2(x4,x2))
          carry#2(x2,Nil()) -> Cons(x2,Nil())
          carry#2(x6,Cons(x4,x2)) -> cond_carry_w_xs_1(lt#2(x6,x4),x6,x4,x2)
          cond_carry_w_xs_1(False(),x3,x2,x1) -> carry#2(mult#2(S(S(0())),x3),x1)
          cond_carry_w_xs_1(True(),x3,x2,x1) -> Cons(x3,Cons(x2,x1))
          lt#2(0(),0()) -> False()
          lt#2(0(),S(x16)) -> True()
          lt#2(S(x16),0()) -> False()
          lt#2(S(x4),S(x2)) -> lt#2(x4,x2)
          main(x2,x1) -> carry#2(x2,x1)
          mult#2(0(),x2) -> 0()
          mult#2(S(x4),x2) -> addNat#2(mult#2(x4,x2),x2)
      - Signature:
          {addNat#2/2,carry#2/2,cond_carry_w_xs_1/4,lt#2/2,main/2,mult#2/2} / {0/0,Cons/2,False/0,Nil/0,S/1,True/0}
      - Obligation:
          innermost runtime complexity wrt. defined symbols {addNat#2,carry#2,cond_carry_w_xs_1,lt#2,main
          ,mult#2} and constructors {0,Cons,False,Nil,S,True}
  + Applied Processor:
      EmptyProcessor
  + Details:
      The problem is still open.
MAYBE