MAYBE

Problem:
 half(0()) -> 0()
 half(s(0())) -> 0()
 half(s(s(x))) -> s(half(x))
 le(0(),y) -> true()
 le(s(x),0()) -> false()
 le(s(x),s(y)) -> le(x,y)
 inc(0()) -> 0()
 inc(s(x)) -> s(inc(x))
 log(x) -> log2(x,0())
 log2(x,y) -> if(le(x,s(0())),x,inc(y))
 if(true(),x,s(y)) -> y
 if(false(),x,y) -> log2(half(x),y)

Proof:
 DP Processor:
  DPs:
   half#(s(s(x))) -> half#(x)
   le#(s(x),s(y)) -> le#(x,y)
   inc#(s(x)) -> inc#(x)
   log#(x) -> log2#(x,0())
   log2#(x,y) -> inc#(y)
   log2#(x,y) -> le#(x,s(0()))
   log2#(x,y) -> if#(le(x,s(0())),x,inc(y))
   if#(false(),x,y) -> half#(x)
   if#(false(),x,y) -> log2#(half(x),y)
  TRS:
   half(0()) -> 0()
   half(s(0())) -> 0()
   half(s(s(x))) -> s(half(x))
   le(0(),y) -> true()
   le(s(x),0()) -> false()
   le(s(x),s(y)) -> le(x,y)
   inc(0()) -> 0()
   inc(s(x)) -> s(inc(x))
   log(x) -> log2(x,0())
   log2(x,y) -> if(le(x,s(0())),x,inc(y))
   if(true(),x,s(y)) -> y
   if(false(),x,y) -> log2(half(x),y)
  Usable Rule Processor:
   DPs:
    half#(s(s(x))) -> half#(x)
    le#(s(x),s(y)) -> le#(x,y)
    inc#(s(x)) -> inc#(x)
    log#(x) -> log2#(x,0())
    log2#(x,y) -> inc#(y)
    log2#(x,y) -> le#(x,s(0()))
    log2#(x,y) -> if#(le(x,s(0())),x,inc(y))
    if#(false(),x,y) -> half#(x)
    if#(false(),x,y) -> log2#(half(x),y)
   TRS:
    f16(x,y) -> x
    f16(x,y) -> y
    inc(0()) -> 0()
    inc(s(x)) -> s(inc(x))
    le(0(),y) -> true()
    le(s(x),s(y)) -> le(x,y)
    le(s(x),0()) -> false()
    half(0()) -> 0()
    half(s(0())) -> 0()
    half(s(s(x))) -> s(half(x))
   EDG Processor:
    DPs:
     half#(s(s(x))) -> half#(x)
     le#(s(x),s(y)) -> le#(x,y)
     inc#(s(x)) -> inc#(x)
     log#(x) -> log2#(x,0())
     log2#(x,y) -> inc#(y)
     log2#(x,y) -> le#(x,s(0()))
     log2#(x,y) -> if#(le(x,s(0())),x,inc(y))
     if#(false(),x,y) -> half#(x)
     if#(false(),x,y) -> log2#(half(x),y)
    TRS:
     f16(x,y) -> x
     f16(x,y) -> y
     inc(0()) -> 0()
     inc(s(x)) -> s(inc(x))
     le(0(),y) -> true()
     le(s(x),s(y)) -> le(x,y)
     le(s(x),0()) -> false()
     half(0()) -> 0()
     half(s(0())) -> 0()
     half(s(s(x))) -> s(half(x))
    graph:
     if#(false(),x,y) -> log2#(half(x),y) ->
     log2#(x,y) -> inc#(y)
     if#(false(),x,y) -> log2#(half(x),y) ->
     log2#(x,y) -> le#(x,s(0()))
     if#(false(),x,y) -> log2#(half(x),y) ->
     log2#(x,y) -> if#(le(x,s(0())),x,inc(y))
     if#(false(),x,y) -> half#(x) ->
     half#(s(s(x))) -> half#(x)
     log2#(x,y) -> if#(le(x,s(0())),x,inc(y)) ->
     if#(false(),x,y) -> half#(x)
     log2#(x,y) -> if#(le(x,s(0())),x,inc(y)) ->
     if#(false(),x,y) -> log2#(half(x),y)
     log2#(x,y) -> inc#(y) -> inc#(s(x)) -> inc#(x)
     log2#(x,y) -> le#(x,s(0())) -> le#(s(x),s(y)) -> le#(x,y)
     log#(x) -> log2#(x,0()) -> log2#(x,y) -> inc#(y)
     log#(x) -> log2#(x,0()) -> log2#(x,y) -> le#(x,s(0()))
     log#(x) -> log2#(x,0()) -> log2#(x,y) -> if#(le(x,s(0())),x,inc(y))
     inc#(s(x)) -> inc#(x) -> inc#(s(x)) -> inc#(x)
     le#(s(x),s(y)) -> le#(x,y) -> le#(s(x),s(y)) -> le#(x,y)
     half#(s(s(x))) -> half#(x) -> half#(s(s(x))) -> half#(x)
    Restore Modifier:
     DPs:
      half#(s(s(x))) -> half#(x)
      le#(s(x),s(y)) -> le#(x,y)
      inc#(s(x)) -> inc#(x)
      log#(x) -> log2#(x,0())
      log2#(x,y) -> inc#(y)
      log2#(x,y) -> le#(x,s(0()))
      log2#(x,y) -> if#(le(x,s(0())),x,inc(y))
      if#(false(),x,y) -> half#(x)
      if#(false(),x,y) -> log2#(half(x),y)
     TRS:
      half(0()) -> 0()
      half(s(0())) -> 0()
      half(s(s(x))) -> s(half(x))
      le(0(),y) -> true()
      le(s(x),0()) -> false()
      le(s(x),s(y)) -> le(x,y)
      inc(0()) -> 0()
      inc(s(x)) -> s(inc(x))
      log(x) -> log2(x,0())
      log2(x,y) -> if(le(x,s(0())),x,inc(y))
      if(true(),x,s(y)) -> y
      if(false(),x,y) -> log2(half(x),y)
     SCC Processor:
      #sccs: 4
      #rules: 5
      #arcs: 14/81
      DPs:
       if#(false(),x,y) -> log2#(half(x),y)
       log2#(x,y) -> if#(le(x,s(0())),x,inc(y))
      TRS:
       half(0()) -> 0()
       half(s(0())) -> 0()
       half(s(s(x))) -> s(half(x))
       le(0(),y) -> true()
       le(s(x),0()) -> false()
       le(s(x),s(y)) -> le(x,y)
       inc(0()) -> 0()
       inc(s(x)) -> s(inc(x))
       log(x) -> log2(x,0())
       log2(x,y) -> if(le(x,s(0())),x,inc(y))
       if(true(),x,s(y)) -> y
       if(false(),x,y) -> log2(half(x),y)
      Open
      
      DPs:
       inc#(s(x)) -> inc#(x)
      TRS:
       half(0()) -> 0()
       half(s(0())) -> 0()
       half(s(s(x))) -> s(half(x))
       le(0(),y) -> true()
       le(s(x),0()) -> false()
       le(s(x),s(y)) -> le(x,y)
       inc(0()) -> 0()
       inc(s(x)) -> s(inc(x))
       log(x) -> log2(x,0())
       log2(x,y) -> if(le(x,s(0())),x,inc(y))
       if(true(),x,s(y)) -> y
       if(false(),x,y) -> log2(half(x),y)
      Matrix Interpretation Processor:
       dimension: 1
       interpretation:
        [inc#](x0) = x0,
        
        [if](x0, x1, x2) = x2,
        
        [log2](x0, x1) = x1,
        
        [log](x0) = 1,
        
        [inc](x0) = x0,
        
        [false] = 0,
        
        [true] = 1,
        
        [le](x0, x1) = x0 + 1,
        
        [s](x0) = x0 + 1,
        
        [half](x0) = x0,
        
        [0] = 0
       orientation:
        inc#(s(x)) = x + 1 >= x = inc#(x)
        
        half(0()) = 0 >= 0 = 0()
        
        half(s(0())) = 1 >= 0 = 0()
        
        half(s(s(x))) = x + 2 >= x + 1 = s(half(x))
        
        le(0(),y) = 1 >= 1 = true()
        
        le(s(x),0()) = x + 2 >= 0 = false()
        
        le(s(x),s(y)) = x + 2 >= x + 1 = le(x,y)
        
        inc(0()) = 0 >= 0 = 0()
        
        inc(s(x)) = x + 1 >= x + 1 = s(inc(x))
        
        log(x) = 1 >= 0 = log2(x,0())
        
        log2(x,y) = y >= y = if(le(x,s(0())),x,inc(y))
        
        if(true(),x,s(y)) = y + 1 >= y = y
        
        if(false(),x,y) = y >= y = log2(half(x),y)
       problem:
        DPs:
         
        TRS:
         half(0()) -> 0()
         half(s(0())) -> 0()
         half(s(s(x))) -> s(half(x))
         le(0(),y) -> true()
         le(s(x),0()) -> false()
         le(s(x),s(y)) -> le(x,y)
         inc(0()) -> 0()
         inc(s(x)) -> s(inc(x))
         log(x) -> log2(x,0())
         log2(x,y) -> if(le(x,s(0())),x,inc(y))
         if(true(),x,s(y)) -> y
         if(false(),x,y) -> log2(half(x),y)
       Qed
      
      DPs:
       le#(s(x),s(y)) -> le#(x,y)
      TRS:
       half(0()) -> 0()
       half(s(0())) -> 0()
       half(s(s(x))) -> s(half(x))
       le(0(),y) -> true()
       le(s(x),0()) -> false()
       le(s(x),s(y)) -> le(x,y)
       inc(0()) -> 0()
       inc(s(x)) -> s(inc(x))
       log(x) -> log2(x,0())
       log2(x,y) -> if(le(x,s(0())),x,inc(y))
       if(true(),x,s(y)) -> y
       if(false(),x,y) -> log2(half(x),y)
      Matrix Interpretation Processor:
       dimension: 1
       interpretation:
        [le#](x0, x1) = x1 + 1,
        
        [if](x0, x1, x2) = x2,
        
        [log2](x0, x1) = x1,
        
        [log](x0) = 0,
        
        [inc](x0) = x0,
        
        [false] = 0,
        
        [true] = 0,
        
        [le](x0, x1) = 0,
        
        [s](x0) = x0 + 1,
        
        [half](x0) = x0,
        
        [0] = 0
       orientation:
        le#(s(x),s(y)) = y + 2 >= y + 1 = le#(x,y)
        
        half(0()) = 0 >= 0 = 0()
        
        half(s(0())) = 1 >= 0 = 0()
        
        half(s(s(x))) = x + 2 >= x + 1 = s(half(x))
        
        le(0(),y) = 0 >= 0 = true()
        
        le(s(x),0()) = 0 >= 0 = false()
        
        le(s(x),s(y)) = 0 >= 0 = le(x,y)
        
        inc(0()) = 0 >= 0 = 0()
        
        inc(s(x)) = x + 1 >= x + 1 = s(inc(x))
        
        log(x) = 0 >= 0 = log2(x,0())
        
        log2(x,y) = y >= y = if(le(x,s(0())),x,inc(y))
        
        if(true(),x,s(y)) = y + 1 >= y = y
        
        if(false(),x,y) = y >= y = log2(half(x),y)
       problem:
        DPs:
         
        TRS:
         half(0()) -> 0()
         half(s(0())) -> 0()
         half(s(s(x))) -> s(half(x))
         le(0(),y) -> true()
         le(s(x),0()) -> false()
         le(s(x),s(y)) -> le(x,y)
         inc(0()) -> 0()
         inc(s(x)) -> s(inc(x))
         log(x) -> log2(x,0())
         log2(x,y) -> if(le(x,s(0())),x,inc(y))
         if(true(),x,s(y)) -> y
         if(false(),x,y) -> log2(half(x),y)
       Qed
      
      DPs:
       half#(s(s(x))) -> half#(x)
      TRS:
       half(0()) -> 0()
       half(s(0())) -> 0()
       half(s(s(x))) -> s(half(x))
       le(0(),y) -> true()
       le(s(x),0()) -> false()
       le(s(x),s(y)) -> le(x,y)
       inc(0()) -> 0()
       inc(s(x)) -> s(inc(x))
       log(x) -> log2(x,0())
       log2(x,y) -> if(le(x,s(0())),x,inc(y))
       if(true(),x,s(y)) -> y
       if(false(),x,y) -> log2(half(x),y)
      Matrix Interpretation Processor:
       dimension: 1
       interpretation:
        [half#](x0) = x0,
        
        [if](x0, x1, x2) = x2,
        
        [log2](x0, x1) = x1,
        
        [log](x0) = 0,
        
        [inc](x0) = x0,
        
        [false] = 0,
        
        [true] = 0,
        
        [le](x0, x1) = 0,
        
        [s](x0) = x0 + 1,
        
        [half](x0) = x0,
        
        [0] = 0
       orientation:
        half#(s(s(x))) = x + 2 >= x = half#(x)
        
        half(0()) = 0 >= 0 = 0()
        
        half(s(0())) = 1 >= 0 = 0()
        
        half(s(s(x))) = x + 2 >= x + 1 = s(half(x))
        
        le(0(),y) = 0 >= 0 = true()
        
        le(s(x),0()) = 0 >= 0 = false()
        
        le(s(x),s(y)) = 0 >= 0 = le(x,y)
        
        inc(0()) = 0 >= 0 = 0()
        
        inc(s(x)) = x + 1 >= x + 1 = s(inc(x))
        
        log(x) = 0 >= 0 = log2(x,0())
        
        log2(x,y) = y >= y = if(le(x,s(0())),x,inc(y))
        
        if(true(),x,s(y)) = y + 1 >= y = y
        
        if(false(),x,y) = y >= y = log2(half(x),y)
       problem:
        DPs:
         
        TRS:
         half(0()) -> 0()
         half(s(0())) -> 0()
         half(s(s(x))) -> s(half(x))
         le(0(),y) -> true()
         le(s(x),0()) -> false()
         le(s(x),s(y)) -> le(x,y)
         inc(0()) -> 0()
         inc(s(x)) -> s(inc(x))
         log(x) -> log2(x,0())
         log2(x,y) -> if(le(x,s(0())),x,inc(y))
         if(true(),x,s(y)) -> y
         if(false(),x,y) -> log2(half(x),y)
       Qed