YES

Problem:
 half(0()) -> 0()
 half(s(0())) -> 0()
 half(s(s(x))) -> s(half(x))
 lastbit(0()) -> 0()
 lastbit(s(0())) -> s(0())
 lastbit(s(s(x))) -> lastbit(x)
 zero(0()) -> true()
 zero(s(x)) -> false()
 conv(x) -> conviter(x,cons(0(),nil()))
 conviter(x,l) -> if(zero(x),x,l)
 if(true(),x,l) -> l
 if(false(),x,l) -> conviter(half(x),cons(lastbit(x),l))

Proof:
 DP Processor:
  DPs:
   half#(s(s(x))) -> half#(x)
   lastbit#(s(s(x))) -> lastbit#(x)
   conv#(x) -> conviter#(x,cons(0(),nil()))
   conviter#(x,l) -> zero#(x)
   conviter#(x,l) -> if#(zero(x),x,l)
   if#(false(),x,l) -> lastbit#(x)
   if#(false(),x,l) -> half#(x)
   if#(false(),x,l) -> conviter#(half(x),cons(lastbit(x),l))
  TRS:
   half(0()) -> 0()
   half(s(0())) -> 0()
   half(s(s(x))) -> s(half(x))
   lastbit(0()) -> 0()
   lastbit(s(0())) -> s(0())
   lastbit(s(s(x))) -> lastbit(x)
   zero(0()) -> true()
   zero(s(x)) -> false()
   conv(x) -> conviter(x,cons(0(),nil()))
   conviter(x,l) -> if(zero(x),x,l)
   if(true(),x,l) -> l
   if(false(),x,l) -> conviter(half(x),cons(lastbit(x),l))
  TDG Processor:
   DPs:
    half#(s(s(x))) -> half#(x)
    lastbit#(s(s(x))) -> lastbit#(x)
    conv#(x) -> conviter#(x,cons(0(),nil()))
    conviter#(x,l) -> zero#(x)
    conviter#(x,l) -> if#(zero(x),x,l)
    if#(false(),x,l) -> lastbit#(x)
    if#(false(),x,l) -> half#(x)
    if#(false(),x,l) -> conviter#(half(x),cons(lastbit(x),l))
   TRS:
    half(0()) -> 0()
    half(s(0())) -> 0()
    half(s(s(x))) -> s(half(x))
    lastbit(0()) -> 0()
    lastbit(s(0())) -> s(0())
    lastbit(s(s(x))) -> lastbit(x)
    zero(0()) -> true()
    zero(s(x)) -> false()
    conv(x) -> conviter(x,cons(0(),nil()))
    conviter(x,l) -> if(zero(x),x,l)
    if(true(),x,l) -> l
    if(false(),x,l) -> conviter(half(x),cons(lastbit(x),l))
   graph:
    if#(false(),x,l) -> conviter#(half(x),cons(lastbit(x),l)) ->
    conviter#(x,l) -> if#(zero(x),x,l)
    if#(false(),x,l) -> conviter#(half(x),cons(lastbit(x),l)) ->
    conviter#(x,l) -> zero#(x)
    if#(false(),x,l) -> lastbit#(x) -> lastbit#(s(s(x))) -> lastbit#(x)
    if#(false(),x,l) -> half#(x) -> half#(s(s(x))) -> half#(x)
    conviter#(x,l) -> if#(zero(x),x,l) ->
    if#(false(),x,l) -> conviter#(half(x),cons(lastbit(x),l))
    conviter#(x,l) -> if#(zero(x),x,l) ->
    if#(false(),x,l) -> half#(x)
    conviter#(x,l) -> if#(zero(x),x,l) ->
    if#(false(),x,l) -> lastbit#(x)
    conv#(x) -> conviter#(x,cons(0(),nil())) ->
    conviter#(x,l) -> if#(zero(x),x,l)
    conv#(x) -> conviter#(x,cons(0(),nil())) ->
    conviter#(x,l) -> zero#(x)
    lastbit#(s(s(x))) -> lastbit#(x) -> lastbit#(s(s(x))) -> lastbit#(x)
    half#(s(s(x))) -> half#(x) -> half#(s(s(x))) -> half#(x)
   SCC Processor:
    #sccs: 3
    #rules: 4
    #arcs: 11/64
    DPs:
     if#(false(),x,l) -> conviter#(half(x),cons(lastbit(x),l))
     conviter#(x,l) -> if#(zero(x),x,l)
    TRS:
     half(0()) -> 0()
     half(s(0())) -> 0()
     half(s(s(x))) -> s(half(x))
     lastbit(0()) -> 0()
     lastbit(s(0())) -> s(0())
     lastbit(s(s(x))) -> lastbit(x)
     zero(0()) -> true()
     zero(s(x)) -> false()
     conv(x) -> conviter(x,cons(0(),nil()))
     conviter(x,l) -> if(zero(x),x,l)
     if(true(),x,l) -> l
     if(false(),x,l) -> conviter(half(x),cons(lastbit(x),l))
    Matrix Interpretation Processor: dim=1
     
     interpretation:
      [if#](x0, x1, x2) = 2x0 + x1 + 2x2,
      
      [conviter#](x0, x1) = 2x0 + 2x1 + 1/2,
      
      [if](x0, x1, x2) = 2x1 + x2 + 5/2,
      
      [conviter](x0, x1) = 2x0 + x1 + 5/2,
      
      [cons](x0, x1) = x1,
      
      [nil] = 1/2,
      
      [conv](x0) = 2x0 + 7/2,
      
      [false] = 1/2,
      
      [true] = 0,
      
      [zero](x0) = 1/2x0,
      
      [lastbit](x0) = 5/2,
      
      [s](x0) = 3x0 + 1,
      
      [half](x0) = 1/2x0,
      
      [0] = 0
     orientation:
      if#(false(),x,l) = 2l + x + 1 >= 2l + x + 1/2 = conviter#(half(x),cons(lastbit(x),l))
      
      conviter#(x,l) = 2l + 2x + 1/2 >= 2l + 2x = if#(zero(x),x,l)
      
      half(0()) = 0 >= 0 = 0()
      
      half(s(0())) = 1/2 >= 0 = 0()
      
      half(s(s(x))) = 9/2x + 2 >= 3/2x + 1 = s(half(x))
      
      lastbit(0()) = 5/2 >= 0 = 0()
      
      lastbit(s(0())) = 5/2 >= 1 = s(0())
      
      lastbit(s(s(x))) = 5/2 >= 5/2 = lastbit(x)
      
      zero(0()) = 0 >= 0 = true()
      
      zero(s(x)) = 3/2x + 1/2 >= 1/2 = false()
      
      conv(x) = 2x + 7/2 >= 2x + 3 = conviter(x,cons(0(),nil()))
      
      conviter(x,l) = l + 2x + 5/2 >= l + 2x + 5/2 = if(zero(x),x,l)
      
      if(true(),x,l) = l + 2x + 5/2 >= l = l
      
      if(false(),x,l) = l + 2x + 5/2 >= l + x + 5/2 = conviter(half(x),cons(lastbit(x),l))
     problem:
      DPs:
       
      TRS:
       half(0()) -> 0()
       half(s(0())) -> 0()
       half(s(s(x))) -> s(half(x))
       lastbit(0()) -> 0()
       lastbit(s(0())) -> s(0())
       lastbit(s(s(x))) -> lastbit(x)
       zero(0()) -> true()
       zero(s(x)) -> false()
       conv(x) -> conviter(x,cons(0(),nil()))
       conviter(x,l) -> if(zero(x),x,l)
       if(true(),x,l) -> l
       if(false(),x,l) -> conviter(half(x),cons(lastbit(x),l))
     Qed
    
    DPs:
     half#(s(s(x))) -> half#(x)
    TRS:
     half(0()) -> 0()
     half(s(0())) -> 0()
     half(s(s(x))) -> s(half(x))
     lastbit(0()) -> 0()
     lastbit(s(0())) -> s(0())
     lastbit(s(s(x))) -> lastbit(x)
     zero(0()) -> true()
     zero(s(x)) -> false()
     conv(x) -> conviter(x,cons(0(),nil()))
     conviter(x,l) -> if(zero(x),x,l)
     if(true(),x,l) -> l
     if(false(),x,l) -> conviter(half(x),cons(lastbit(x),l))
    KBO Processor:
     argument filtering:
      pi(0) = []
      pi(half) = 0
      pi(s) = [0]
      pi(lastbit) = 0
      pi(zero) = [0]
      pi(true) = []
      pi(false) = []
      pi(conv) = [0]
      pi(nil) = []
      pi(cons) = 1
      pi(conviter) = 1
      pi(if) = 2
      pi(half#) = 0
     weight function:
      w0 = 1
      w(if) = w(cons) = w(nil) = w(conv) = w(false) = w(true) = w(zero) = w(
      lastbit) = w(0) = 1
      w(half#) = w(conviter) = w(s) = w(half) = 0
     precedence:
      half# ~ nil ~ conv ~ false ~ true ~ s > if ~ conviter ~ cons ~ zero ~ lastbit ~ half ~ 0
     problem:
      DPs:
       
      TRS:
       half(0()) -> 0()
       half(s(0())) -> 0()
       half(s(s(x))) -> s(half(x))
       lastbit(0()) -> 0()
       lastbit(s(0())) -> s(0())
       lastbit(s(s(x))) -> lastbit(x)
       zero(0()) -> true()
       zero(s(x)) -> false()
       conv(x) -> conviter(x,cons(0(),nil()))
       conviter(x,l) -> if(zero(x),x,l)
       if(true(),x,l) -> l
       if(false(),x,l) -> conviter(half(x),cons(lastbit(x),l))
     Qed
    
    DPs:
     lastbit#(s(s(x))) -> lastbit#(x)
    TRS:
     half(0()) -> 0()
     half(s(0())) -> 0()
     half(s(s(x))) -> s(half(x))
     lastbit(0()) -> 0()
     lastbit(s(0())) -> s(0())
     lastbit(s(s(x))) -> lastbit(x)
     zero(0()) -> true()
     zero(s(x)) -> false()
     conv(x) -> conviter(x,cons(0(),nil()))
     conviter(x,l) -> if(zero(x),x,l)
     if(true(),x,l) -> l
     if(false(),x,l) -> conviter(half(x),cons(lastbit(x),l))
    KBO Processor:
     argument filtering:
      pi(0) = []
      pi(half) = 0
      pi(s) = [0]
      pi(lastbit) = 0
      pi(zero) = [0]
      pi(true) = []
      pi(false) = []
      pi(conv) = [0]
      pi(nil) = []
      pi(cons) = 1
      pi(conviter) = 1
      pi(if) = 2
      pi(lastbit#) = 0
     weight function:
      w0 = 1
      w(if) = w(cons) = w(nil) = w(conv) = w(false) = w(true) = w(zero) = w(
      lastbit) = w(0) = 1
      w(lastbit#) = w(conviter) = w(s) = w(half) = 0
     precedence:
      lastbit# ~ nil ~ conv ~ false ~ true ~ s > if ~ conviter ~ cons ~ zero ~ lastbit ~ half ~ 0
     problem:
      DPs:
       
      TRS:
       half(0()) -> 0()
       half(s(0())) -> 0()
       half(s(s(x))) -> s(half(x))
       lastbit(0()) -> 0()
       lastbit(s(0())) -> s(0())
       lastbit(s(s(x))) -> lastbit(x)
       zero(0()) -> true()
       zero(s(x)) -> false()
       conv(x) -> conviter(x,cons(0(),nil()))
       conviter(x,l) -> if(zero(x),x,l)
       if(true(),x,l) -> l
       if(false(),x,l) -> conviter(half(x),cons(lastbit(x),l))
     Qed