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))
    Arctic Interpretation Processor:
     dimension: 1
     interpretation:
      [if#](x0, x1, x2) = x0 + -2x1 + -5x2 + -6,
      
      [conviter#](x0, x1) = x0 + -5x1 + -6,
      
      [if](x0, x1, x2) = 4x1 + x2 + 4,
      
      [conviter](x0, x1) = 4x0 + x1 + 4,
      
      [cons](x0, x1) = 2x0,
      
      [nil] = 1,
      
      [conv](x0) = 9x0 + 4,
      
      [false] = 4,
      
      [true] = 0,
      
      [zero](x0) = x0 + -8,
      
      [lastbit](x0) = x0,
      
      [s](x0) = 3x0 + 4,
      
      [half](x0) = -3x0 + 0,
      
      [0] = 0
     orientation:
      if#(false(),x,l) = -5l + -2x + 4 >= -3x + 0 = conviter#(half(x),cons(lastbit(x),l))
      
      conviter#(x,l) = -5l + x + -6 >= -5l + x + -6 = if#(zero(x),x,l)
      
      half(0()) = 0 >= 0 = 0()
      
      half(s(0())) = 1 >= 0 = 0()
      
      half(s(s(x))) = 3x + 4 >= x + 4 = s(half(x))
      
      lastbit(0()) = 0 >= 0 = 0()
      
      lastbit(s(0())) = 4 >= 4 = s(0())
      
      lastbit(s(s(x))) = 6x + 7 >= x = lastbit(x)
      
      zero(0()) = 0 >= 0 = true()
      
      zero(s(x)) = 3x + 4 >= 4 = false()
      
      conv(x) = 9x + 4 >= 4x + 4 = conviter(x,cons(0(),nil()))
      
      conviter(x,l) = l + 4x + 4 >= l + 4x + 4 = if(zero(x),x,l)
      
      if(true(),x,l) = l + 4x + 4 >= l = l
      
      if(false(),x,l) = l + 4x + 4 >= 2x + 4 = conviter(half(x),cons(lastbit(x),l))
     problem:
      DPs:
       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))
     SCC Processor:
      #sccs: 0
      #rules: 0
      #arcs: 2/1
      
    
    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))
    Subterm Criterion Processor:
     simple projection:
      pi(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))
    Subterm Criterion Processor:
     simple projection:
      pi(lastbit#) = 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