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))
    Usable Rule Processor:
     DPs:
      if#(false(),x,l) -> conviter#(half(x),cons(lastbit(x),l))
      conviter#(x,l) -> if#(zero(x),x,l)
     TRS:
      lastbit(0()) -> 0()
      lastbit(s(0())) -> s(0())
      lastbit(s(s(x))) -> lastbit(x)
      half(0()) -> 0()
      half(s(0())) -> 0()
      half(s(s(x))) -> s(half(x))
      zero(0()) -> true()
      zero(s(x)) -> false()
     Arctic Interpretation Processor:
      dimension: 1
      usable rules:
       lastbit(0()) -> 0()
       lastbit(s(0())) -> s(0())
       lastbit(s(s(x))) -> lastbit(x)
       half(0()) -> 0()
       half(s(0())) -> 0()
       half(s(s(x))) -> s(half(x))
       zero(0()) -> true()
       zero(s(x)) -> false()
      interpretation:
       [if#](x0, x1, x2) = x0 + x1 + x2 + -16,
       
       [conviter#](x0, x1) = 1x0 + 3x1 + 0,
       
       [cons](x0, x1) = -3x0 + 0,
       
       [false] = 3,
       
       [true] = 0,
       
       [zero](x0) = x0 + -8,
       
       [lastbit](x0) = 3,
       
       [s](x0) = 3x0 + 3,
       
       [half](x0) = -1x0 + 2,
       
       [0] = 0
      orientation:
       if#(false(),x,l) = l + x + 3 >= x + 3 = conviter#(half(x),cons(lastbit(x),l))
       
       conviter#(x,l) = 3l + 1x + 0 >= l + x + -8 = if#(zero(x),x,l)
       
       lastbit(0()) = 3 >= 0 = 0()
       
       lastbit(s(0())) = 3 >= 3 = s(0())
       
       lastbit(s(s(x))) = 3 >= 3 = lastbit(x)
       
       half(0()) = 2 >= 0 = 0()
       
       half(s(0())) = 2 >= 0 = 0()
       
       half(s(s(x))) = 5x + 5 >= 2x + 5 = s(half(x))
       
       zero(0()) = 0 >= 0 = true()
       
       zero(s(x)) = 3x + 3 >= 3 = false()
      problem:
       DPs:
        if#(false(),x,l) -> conviter#(half(x),cons(lastbit(x),l))
       TRS:
        lastbit(0()) -> 0()
        lastbit(s(0())) -> s(0())
        lastbit(s(s(x))) -> lastbit(x)
        half(0()) -> 0()
        half(s(0())) -> 0()
        half(s(s(x))) -> s(half(x))
        zero(0()) -> true()
        zero(s(x)) -> false()
      Restore Modifier:
       DPs:
        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))
       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