MAYBE

Problem:
 lt(0(),s(x)) -> true()
 lt(x,0()) -> false()
 lt(s(x),s(y)) -> lt(x,y)
 fibo(0()) -> fib(0())
 fibo(s(0())) -> fib(s(0()))
 fibo(s(s(x))) -> sum(fibo(s(x)),fibo(x))
 fib(0()) -> s(0())
 fib(s(0())) -> s(0())
 fib(s(s(x))) -> if(true(),0(),s(s(x)),0(),0())
 if(true(),c,s(s(x)),a,b) -> if(lt(s(c),s(s(x))),s(c),s(s(x)),b,c)
 if(false(),c,s(s(x)),a,b) -> sum(fibo(a),fibo(b))
 sum(x,0()) -> x
 sum(x,s(y)) -> s(sum(x,y))

Proof:
 DP Processor:
  DPs:
   lt#(s(x),s(y)) -> lt#(x,y)
   fibo#(0()) -> fib#(0())
   fibo#(s(0())) -> fib#(s(0()))
   fibo#(s(s(x))) -> fibo#(x)
   fibo#(s(s(x))) -> fibo#(s(x))
   fibo#(s(s(x))) -> sum#(fibo(s(x)),fibo(x))
   fib#(s(s(x))) -> if#(true(),0(),s(s(x)),0(),0())
   if#(true(),c,s(s(x)),a,b) -> lt#(s(c),s(s(x)))
   if#(true(),c,s(s(x)),a,b) -> if#(lt(s(c),s(s(x))),s(c),s(s(x)),b,c)
   if#(false(),c,s(s(x)),a,b) -> fibo#(b)
   if#(false(),c,s(s(x)),a,b) -> fibo#(a)
   if#(false(),c,s(s(x)),a,b) -> sum#(fibo(a),fibo(b))
   sum#(x,s(y)) -> sum#(x,y)
  TRS:
   lt(0(),s(x)) -> true()
   lt(x,0()) -> false()
   lt(s(x),s(y)) -> lt(x,y)
   fibo(0()) -> fib(0())
   fibo(s(0())) -> fib(s(0()))
   fibo(s(s(x))) -> sum(fibo(s(x)),fibo(x))
   fib(0()) -> s(0())
   fib(s(0())) -> s(0())
   fib(s(s(x))) -> if(true(),0(),s(s(x)),0(),0())
   if(true(),c,s(s(x)),a,b) -> if(lt(s(c),s(s(x))),s(c),s(s(x)),b,c)
   if(false(),c,s(s(x)),a,b) -> sum(fibo(a),fibo(b))
   sum(x,0()) -> x
   sum(x,s(y)) -> s(sum(x,y))
  Usable Rule Processor:
   DPs:
    lt#(s(x),s(y)) -> lt#(x,y)
    fibo#(0()) -> fib#(0())
    fibo#(s(0())) -> fib#(s(0()))
    fibo#(s(s(x))) -> fibo#(x)
    fibo#(s(s(x))) -> fibo#(s(x))
    fibo#(s(s(x))) -> sum#(fibo(s(x)),fibo(x))
    fib#(s(s(x))) -> if#(true(),0(),s(s(x)),0(),0())
    if#(true(),c,s(s(x)),a,b) -> lt#(s(c),s(s(x)))
    if#(true(),c,s(s(x)),a,b) -> if#(lt(s(c),s(s(x))),s(c),s(s(x)),b,c)
    if#(false(),c,s(s(x)),a,b) -> fibo#(b)
    if#(false(),c,s(s(x)),a,b) -> fibo#(a)
    if#(false(),c,s(s(x)),a,b) -> sum#(fibo(a),fibo(b))
    sum#(x,s(y)) -> sum#(x,y)
   TRS:
    fibo(0()) -> fib(0())
    fibo(s(0())) -> fib(s(0()))
    fibo(s(s(x))) -> sum(fibo(s(x)),fibo(x))
    fib(0()) -> s(0())
    fib(s(0())) -> s(0())
    sum(x,0()) -> x
    sum(x,s(y)) -> s(sum(x,y))
    lt(s(x),s(y)) -> lt(x,y)
    lt(0(),s(x)) -> true()
    lt(x,0()) -> false()
   Open