YES

Problem:
 is_empty(nil()) -> true()
 is_empty(cons(x,l)) -> false()
 hd(cons(x,l)) -> x
 tl(cons(x,l)) -> l
 append(l1,l2) -> ifappend(l1,l2,is_empty(l1))
 ifappend(l1,l2,true()) -> l2
 ifappend(l1,l2,false()) -> cons(hd(l1),append(tl(l1),l2))

Proof:
 DP Processor:
  DPs:
   append#(l1,l2) -> is_empty#(l1)
   append#(l1,l2) -> ifappend#(l1,l2,is_empty(l1))
   ifappend#(l1,l2,false()) -> tl#(l1)
   ifappend#(l1,l2,false()) -> append#(tl(l1),l2)
   ifappend#(l1,l2,false()) -> hd#(l1)
  TRS:
   is_empty(nil()) -> true()
   is_empty(cons(x,l)) -> false()
   hd(cons(x,l)) -> x
   tl(cons(x,l)) -> l
   append(l1,l2) -> ifappend(l1,l2,is_empty(l1))
   ifappend(l1,l2,true()) -> l2
   ifappend(l1,l2,false()) -> cons(hd(l1),append(tl(l1),l2))
  TDG Processor:
   DPs:
    append#(l1,l2) -> is_empty#(l1)
    append#(l1,l2) -> ifappend#(l1,l2,is_empty(l1))
    ifappend#(l1,l2,false()) -> tl#(l1)
    ifappend#(l1,l2,false()) -> append#(tl(l1),l2)
    ifappend#(l1,l2,false()) -> hd#(l1)
   TRS:
    is_empty(nil()) -> true()
    is_empty(cons(x,l)) -> false()
    hd(cons(x,l)) -> x
    tl(cons(x,l)) -> l
    append(l1,l2) -> ifappend(l1,l2,is_empty(l1))
    ifappend(l1,l2,true()) -> l2
    ifappend(l1,l2,false()) -> cons(hd(l1),append(tl(l1),l2))
   graph:
    ifappend#(l1,l2,false()) -> append#(tl(l1),l2) ->
    append#(l1,l2) -> ifappend#(l1,l2,is_empty(l1))
    ifappend#(l1,l2,false()) -> append#(tl(l1),l2) ->
    append#(l1,l2) -> is_empty#(l1)
    append#(l1,l2) -> ifappend#(l1,l2,is_empty(l1)) ->
    ifappend#(l1,l2,false()) -> hd#(l1)
    append#(l1,l2) -> ifappend#(l1,l2,is_empty(l1)) ->
    ifappend#(l1,l2,false()) -> append#(tl(l1),l2)
    append#(l1,l2) -> ifappend#(l1,l2,is_empty(l1)) -> ifappend#(l1,l2,false()) -> tl#(l1)
   SCC Processor:
    #sccs: 1
    #rules: 2
    #arcs: 5/25
    DPs:
     ifappend#(l1,l2,false()) -> append#(tl(l1),l2)
     append#(l1,l2) -> ifappend#(l1,l2,is_empty(l1))
    TRS:
     is_empty(nil()) -> true()
     is_empty(cons(x,l)) -> false()
     hd(cons(x,l)) -> x
     tl(cons(x,l)) -> l
     append(l1,l2) -> ifappend(l1,l2,is_empty(l1))
     ifappend(l1,l2,true()) -> l2
     ifappend(l1,l2,false()) -> cons(hd(l1),append(tl(l1),l2))
    Usable Rule Processor:
     DPs:
      ifappend#(l1,l2,false()) -> append#(tl(l1),l2)
      append#(l1,l2) -> ifappend#(l1,l2,is_empty(l1))
     TRS:
      tl(cons(x,l)) -> l
      is_empty(nil()) -> true()
      is_empty(cons(x,l)) -> false()
     Arctic Interpretation Processor:
      dimension: 1
      usable rules:
       tl(cons(x,l)) -> l
       is_empty(nil()) -> true()
       is_empty(cons(x,l)) -> false()
      interpretation:
       [false] = 1,
       
       [is_empty](x0) = x0,
       
       [cons](x0, x1) = x0 + 8x1 + 1,
       
       [nil] = 1,
       
       [append#](x0, x1) = 1x0 + 1,
       
       [ifappend#](x0, x1, x2) = x0 + x2 + 0,
       
       [tl](x0) = -8x0 + 0,
       
       [true] = 0
      orientation:
       ifappend#(l1,l2,false()) = l1 + 1 >= -7l1 + 1 = append#(tl(l1),l2)
       
       append#(l1,l2) = 1l1 + 1 >= l1 + 0 = ifappend#(l1,l2,is_empty(l1))
       
       tl(cons(x,l)) = l + -8x + 0 >= l = l
       
       is_empty(nil()) = 1 >= 0 = true()
       
       is_empty(cons(x,l)) = 8l + x + 1 >= 1 = false()
      problem:
       DPs:
        ifappend#(l1,l2,false()) -> append#(tl(l1),l2)
       TRS:
        tl(cons(x,l)) -> l
        is_empty(nil()) -> true()
        is_empty(cons(x,l)) -> false()
      Restore Modifier:
       DPs:
        ifappend#(l1,l2,false()) -> append#(tl(l1),l2)
       TRS:
        is_empty(nil()) -> true()
        is_empty(cons(x,l)) -> false()
        hd(cons(x,l)) -> x
        tl(cons(x,l)) -> l
        append(l1,l2) -> ifappend(l1,l2,is_empty(l1))
        ifappend(l1,l2,true()) -> l2
        ifappend(l1,l2,false()) -> cons(hd(l1),append(tl(l1),l2))
       SCC Processor:
        #sccs: 0
        #rules: 0
        #arcs: 2/1