YES

Problem:
 isEmpty(cons(x,xs)) -> false()
 isEmpty(nil()) -> true()
 isZero(0()) -> true()
 isZero(s(x)) -> false()
 head(cons(x,xs)) -> x
 tail(cons(x,xs)) -> xs
 tail(nil()) -> nil()
 p(s(s(x))) -> s(p(s(x)))
 p(s(0())) -> 0()
 p(0()) -> 0()
 inc(s(x)) -> s(inc(x))
 inc(0()) -> s(0())
 sumList(xs,y) -> if(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
 if(true(),b,y,xs,ys,x) -> y
 if(false(),true(),y,xs,ys,x) -> sumList(xs,y)
 if(false(),false(),y,xs,ys,x) -> sumList(ys,x)
 sum(xs) -> sumList(xs,0())

Proof:
 DP Processor:
  DPs:
   p#(s(s(x))) -> p#(s(x))
   inc#(s(x)) -> inc#(x)
   sumList#(xs,y) -> inc#(y)
   sumList#(xs,y) -> p#(head(xs))
   sumList#(xs,y) -> tail#(xs)
   sumList#(xs,y) -> head#(xs)
   sumList#(xs,y) -> isZero#(head(xs))
   sumList#(xs,y) -> isEmpty#(xs)
   sumList#(xs,y) -> if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
   if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y)
   if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x)
   sum#(xs) -> sumList#(xs,0())
  TRS:
   isEmpty(cons(x,xs)) -> false()
   isEmpty(nil()) -> true()
   isZero(0()) -> true()
   isZero(s(x)) -> false()
   head(cons(x,xs)) -> x
   tail(cons(x,xs)) -> xs
   tail(nil()) -> nil()
   p(s(s(x))) -> s(p(s(x)))
   p(s(0())) -> 0()
   p(0()) -> 0()
   inc(s(x)) -> s(inc(x))
   inc(0()) -> s(0())
   sumList(xs,y) -> if(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
   if(true(),b,y,xs,ys,x) -> y
   if(false(),true(),y,xs,ys,x) -> sumList(xs,y)
   if(false(),false(),y,xs,ys,x) -> sumList(ys,x)
   sum(xs) -> sumList(xs,0())
  TDG Processor:
   DPs:
    p#(s(s(x))) -> p#(s(x))
    inc#(s(x)) -> inc#(x)
    sumList#(xs,y) -> inc#(y)
    sumList#(xs,y) -> p#(head(xs))
    sumList#(xs,y) -> tail#(xs)
    sumList#(xs,y) -> head#(xs)
    sumList#(xs,y) -> isZero#(head(xs))
    sumList#(xs,y) -> isEmpty#(xs)
    sumList#(xs,y) ->
    if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
    if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y)
    if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x)
    sum#(xs) -> sumList#(xs,0())
   TRS:
    isEmpty(cons(x,xs)) -> false()
    isEmpty(nil()) -> true()
    isZero(0()) -> true()
    isZero(s(x)) -> false()
    head(cons(x,xs)) -> x
    tail(cons(x,xs)) -> xs
    tail(nil()) -> nil()
    p(s(s(x))) -> s(p(s(x)))
    p(s(0())) -> 0()
    p(0()) -> 0()
    inc(s(x)) -> s(inc(x))
    inc(0()) -> s(0())
    sumList(xs,y) -> if(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
    if(true(),b,y,xs,ys,x) -> y
    if(false(),true(),y,xs,ys,x) -> sumList(xs,y)
    if(false(),false(),y,xs,ys,x) -> sumList(ys,x)
    sum(xs) -> sumList(xs,0())
   graph:
    sum#(xs) -> sumList#(xs,0()) ->
    sumList#(xs,y) ->
    if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
    sum#(xs) -> sumList#(xs,0()) -> sumList#(xs,y) -> isEmpty#(xs)
    sum#(xs) -> sumList#(xs,0()) -> sumList#(xs,y) -> isZero#(head(xs))
    sum#(xs) -> sumList#(xs,0()) -> sumList#(xs,y) -> head#(xs)
    sum#(xs) -> sumList#(xs,0()) -> sumList#(xs,y) -> tail#(xs)
    sum#(xs) -> sumList#(xs,0()) -> sumList#(xs,y) -> p#(head(xs))
    sum#(xs) -> sumList#(xs,0()) ->
    sumList#(xs,y) -> inc#(y)
    if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y) ->
    sumList#(xs,y) ->
    if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
    if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y) ->
    sumList#(xs,y) -> isEmpty#(xs)
    if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y) ->
    sumList#(xs,y) -> isZero#(head(xs))
    if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y) ->
    sumList#(xs,y) -> head#(xs)
    if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y) ->
    sumList#(xs,y) -> tail#(xs)
    if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y) ->
    sumList#(xs,y) -> p#(head(xs))
    if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y) ->
    sumList#(xs,y) -> inc#(y)
    if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x) ->
    sumList#(xs,y) ->
    if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
    if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x) ->
    sumList#(xs,y) -> isEmpty#(xs)
    if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x) ->
    sumList#(xs,y) -> isZero#(head(xs))
    if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x) ->
    sumList#(xs,y) -> head#(xs)
    if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x) ->
    sumList#(xs,y) -> tail#(xs)
    if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x) ->
    sumList#(xs,y) -> p#(head(xs))
    if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x) ->
    sumList#(xs,y) -> inc#(y)
    sumList#(xs,y) ->
    if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y)) ->
    if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x)
    sumList#(xs,y) ->
    if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y)) ->
    if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y)
    sumList#(xs,y) -> inc#(y) -> inc#(s(x)) -> inc#(x)
    sumList#(xs,y) -> p#(head(xs)) -> p#(s(s(x))) -> p#(s(x))
    inc#(s(x)) -> inc#(x) -> inc#(s(x)) -> inc#(x)
    p#(s(s(x))) -> p#(s(x)) -> p#(s(s(x))) -> p#(s(x))
   SCC Processor:
    #sccs: 3
    #rules: 5
    #arcs: 27/144
    DPs:
     sumList#(xs,y) ->
     if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
     if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y)
     if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x)
    TRS:
     isEmpty(cons(x,xs)) -> false()
     isEmpty(nil()) -> true()
     isZero(0()) -> true()
     isZero(s(x)) -> false()
     head(cons(x,xs)) -> x
     tail(cons(x,xs)) -> xs
     tail(nil()) -> nil()
     p(s(s(x))) -> s(p(s(x)))
     p(s(0())) -> 0()
     p(0()) -> 0()
     inc(s(x)) -> s(inc(x))
     inc(0()) -> s(0())
     sumList(xs,y) -> if(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
     if(true(),b,y,xs,ys,x) -> y
     if(false(),true(),y,xs,ys,x) -> sumList(xs,y)
     if(false(),false(),y,xs,ys,x) -> sumList(ys,x)
     sum(xs) -> sumList(xs,0())
    Usable Rule Processor:
     DPs:
      sumList#(xs,y) ->
      if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
      if#(false(),true(),y,xs,ys,x) -> sumList#(xs,y)
      if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x)
     TRS:
      inc(s(x)) -> s(inc(x))
      inc(0()) -> s(0())
      p(s(s(x))) -> s(p(s(x)))
      p(s(0())) -> 0()
      p(0()) -> 0()
      head(cons(x,xs)) -> x
      tail(cons(x,xs)) -> xs
      tail(nil()) -> nil()
      isZero(0()) -> true()
      isZero(s(x)) -> false()
      isEmpty(cons(x,xs)) -> false()
      isEmpty(nil()) -> true()
     Arctic Interpretation Processor:
      dimension: 1
      usable rules:
       inc(s(x)) -> s(inc(x))
       inc(0()) -> s(0())
       p(s(s(x))) -> s(p(s(x)))
       p(s(0())) -> 0()
       p(0()) -> 0()
       head(cons(x,xs)) -> x
       tail(cons(x,xs)) -> xs
       tail(nil()) -> nil()
       isZero(0()) -> true()
       isZero(s(x)) -> false()
      interpretation:
       [if#](x0, x1, x2, x3, x4, x5) = -2x1 + 3x3 + 2x4 + -8x5 + 4,
       
       [sumList#](x0, x1) = 2x0 + 4,
       
       [inc](x0) = 3,
       
       [p](x0) = x0 + -1,
       
       [tail](x0) = -1x0 + 0,
       
       [head](x0) = x0 + -8,
       
       [s](x0) = x0 + 2,
       
       [isZero](x0) = 4x0 + -16,
       
       [0] = 3,
       
       [true] = 7,
       
       [nil] = 0,
       
       [false] = 5,
       
       [isEmpty](x0) = 7x0 + 7,
       
       [cons](x0, x1) = x0 + 1x1 + 0
      orientation:
       sumList#(xs,y) = 2xs + 4 >= 2xs + 4 = if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
       
       if#(false(),true(),y,xs,ys,x) = -8x + 3xs + 2ys + 5 >= 2xs + 4 = sumList#(xs,y)
       
       if#(false(),false(),y,xs,ys,x) = -8x + 3xs + 2ys + 4 >= 2ys + 4 = sumList#(ys,x)
       
       inc(s(x)) = 3 >= 3 = s(inc(x))
       
       inc(0()) = 3 >= 3 = s(0())
       
       p(s(s(x))) = x + 2 >= x + 2 = s(p(s(x)))
       
       p(s(0())) = 3 >= 3 = 0()
       
       p(0()) = 3 >= 3 = 0()
       
       head(cons(x,xs)) = x + 1xs + 0 >= x = x
       
       tail(cons(x,xs)) = -1x + xs + 0 >= xs = xs
       
       tail(nil()) = 0 >= 0 = nil()
       
       isZero(0()) = 7 >= 7 = true()
       
       isZero(s(x)) = 4x + 6 >= 5 = false()
       
       isEmpty(cons(x,xs)) = 7x + 8xs + 7 >= 5 = false()
       
       isEmpty(nil()) = 7 >= 7 = true()
      problem:
       DPs:
        sumList#(xs,y) ->
        if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
        if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x)
       TRS:
        inc(s(x)) -> s(inc(x))
        inc(0()) -> s(0())
        p(s(s(x))) -> s(p(s(x)))
        p(s(0())) -> 0()
        p(0()) -> 0()
        head(cons(x,xs)) -> x
        tail(cons(x,xs)) -> xs
        tail(nil()) -> nil()
        isZero(0()) -> true()
        isZero(s(x)) -> false()
        isEmpty(cons(x,xs)) -> false()
        isEmpty(nil()) -> true()
      Restore Modifier:
       DPs:
        sumList#(xs,y) ->
        if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
        if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x)
       TRS:
        isEmpty(cons(x,xs)) -> false()
        isEmpty(nil()) -> true()
        isZero(0()) -> true()
        isZero(s(x)) -> false()
        head(cons(x,xs)) -> x
        tail(cons(x,xs)) -> xs
        tail(nil()) -> nil()
        p(s(s(x))) -> s(p(s(x)))
        p(s(0())) -> 0()
        p(0()) -> 0()
        inc(s(x)) -> s(inc(x))
        inc(0()) -> s(0())
        sumList(xs,y) ->
        if(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
        if(true(),b,y,xs,ys,x) -> y
        if(false(),true(),y,xs,ys,x) -> sumList(xs,y)
        if(false(),false(),y,xs,ys,x) -> sumList(ys,x)
        sum(xs) -> sumList(xs,0())
       Usable Rule Processor:
        DPs:
         sumList#(xs,y) ->
         if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
         if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x)
        TRS:
         inc(s(x)) -> s(inc(x))
         inc(0()) -> s(0())
         p(s(s(x))) -> s(p(s(x)))
         p(s(0())) -> 0()
         p(0()) -> 0()
         head(cons(x,xs)) -> x
         tail(cons(x,xs)) -> xs
         tail(nil()) -> nil()
         isZero(0()) -> true()
         isZero(s(x)) -> false()
         isEmpty(cons(x,xs)) -> false()
         isEmpty(nil()) -> true()
        Arctic Interpretation Processor:
         dimension: 1
         usable rules:
          p(s(s(x))) -> s(p(s(x)))
          p(s(0())) -> 0()
          p(0()) -> 0()
          head(cons(x,xs)) -> x
          isZero(0()) -> true()
          isZero(s(x)) -> false()
         interpretation:
          [if#](x0, x1, x2, x3, x4, x5) = 1x1 + 3x4,
          
          [sumList#](x0, x1) = 3x0 + 5,
          
          [inc](x0) = x0 + 5,
          
          [p](x0) = -1x0 + 0,
          
          [tail](x0) = x0 + 2,
          
          [head](x0) = 1x0,
          
          [s](x0) = 2x0 + 4,
          
          [isZero](x0) = x0,
          
          [0] = 0,
          
          [true] = 0,
          
          [nil] = 4,
          
          [false] = 4,
          
          [isEmpty](x0) = x0,
          
          [cons](x0, x1) = -1x0 + 1
         orientation:
          sumList#(xs,y) = 3xs + 5 >= 2xs + 4 = if#(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
          
          if#(false(),false(),y,xs,ys,x) = 3ys + 5 >= 3ys + 5 = sumList#(ys,x)
          
          inc(s(x)) = 2x + 5 >= 2x + 7 = s(inc(x))
          
          inc(0()) = 5 >= 4 = s(0())
          
          p(s(s(x))) = 3x + 5 >= 3x + 5 = s(p(s(x)))
          
          p(s(0())) = 3 >= 0 = 0()
          
          p(0()) = 0 >= 0 = 0()
          
          head(cons(x,xs)) = x + 2 >= x = x
          
          tail(cons(x,xs)) = -1x + 2 >= xs = xs
          
          tail(nil()) = 4 >= 4 = nil()
          
          isZero(0()) = 0 >= 0 = true()
          
          isZero(s(x)) = 2x + 4 >= 4 = false()
          
          isEmpty(cons(x,xs)) = -1x + 1 >= 4 = false()
          
          isEmpty(nil()) = 4 >= 0 = true()
         problem:
          DPs:
           if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x)
          TRS:
           inc(s(x)) -> s(inc(x))
           inc(0()) -> s(0())
           p(s(s(x))) -> s(p(s(x)))
           p(s(0())) -> 0()
           p(0()) -> 0()
           head(cons(x,xs)) -> x
           tail(cons(x,xs)) -> xs
           tail(nil()) -> nil()
           isZero(0()) -> true()
           isZero(s(x)) -> false()
           isEmpty(cons(x,xs)) -> false()
           isEmpty(nil()) -> true()
         Restore Modifier:
          DPs:
           if#(false(),false(),y,xs,ys,x) -> sumList#(ys,x)
          TRS:
           isEmpty(cons(x,xs)) -> false()
           isEmpty(nil()) -> true()
           isZero(0()) -> true()
           isZero(s(x)) -> false()
           head(cons(x,xs)) -> x
           tail(cons(x,xs)) -> xs
           tail(nil()) -> nil()
           p(s(s(x))) -> s(p(s(x)))
           p(s(0())) -> 0()
           p(0()) -> 0()
           inc(s(x)) -> s(inc(x))
           inc(0()) -> s(0())
           sumList(xs,y) ->
           if(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
           if(true(),b,y,xs,ys,x) -> y
           if(false(),true(),y,xs,ys,x) -> sumList(xs,y)
           if(false(),false(),y,xs,ys,x) -> sumList(ys,x)
           sum(xs) -> sumList(xs,0())
          SCC Processor:
           #sccs: 0
           #rules: 0
           #arcs: 4/1
           
    
    DPs:
     p#(s(s(x))) -> p#(s(x))
    TRS:
     isEmpty(cons(x,xs)) -> false()
     isEmpty(nil()) -> true()
     isZero(0()) -> true()
     isZero(s(x)) -> false()
     head(cons(x,xs)) -> x
     tail(cons(x,xs)) -> xs
     tail(nil()) -> nil()
     p(s(s(x))) -> s(p(s(x)))
     p(s(0())) -> 0()
     p(0()) -> 0()
     inc(s(x)) -> s(inc(x))
     inc(0()) -> s(0())
     sumList(xs,y) -> if(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
     if(true(),b,y,xs,ys,x) -> y
     if(false(),true(),y,xs,ys,x) -> sumList(xs,y)
     if(false(),false(),y,xs,ys,x) -> sumList(ys,x)
     sum(xs) -> sumList(xs,0())
    Subterm Criterion Processor:
     simple projection:
      pi(p#) = 0
     problem:
      DPs:
       
      TRS:
       isEmpty(cons(x,xs)) -> false()
       isEmpty(nil()) -> true()
       isZero(0()) -> true()
       isZero(s(x)) -> false()
       head(cons(x,xs)) -> x
       tail(cons(x,xs)) -> xs
       tail(nil()) -> nil()
       p(s(s(x))) -> s(p(s(x)))
       p(s(0())) -> 0()
       p(0()) -> 0()
       inc(s(x)) -> s(inc(x))
       inc(0()) -> s(0())
       sumList(xs,y) ->
       if(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
       if(true(),b,y,xs,ys,x) -> y
       if(false(),true(),y,xs,ys,x) -> sumList(xs,y)
       if(false(),false(),y,xs,ys,x) -> sumList(ys,x)
       sum(xs) -> sumList(xs,0())
     Qed
    
    DPs:
     inc#(s(x)) -> inc#(x)
    TRS:
     isEmpty(cons(x,xs)) -> false()
     isEmpty(nil()) -> true()
     isZero(0()) -> true()
     isZero(s(x)) -> false()
     head(cons(x,xs)) -> x
     tail(cons(x,xs)) -> xs
     tail(nil()) -> nil()
     p(s(s(x))) -> s(p(s(x)))
     p(s(0())) -> 0()
     p(0()) -> 0()
     inc(s(x)) -> s(inc(x))
     inc(0()) -> s(0())
     sumList(xs,y) -> if(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
     if(true(),b,y,xs,ys,x) -> y
     if(false(),true(),y,xs,ys,x) -> sumList(xs,y)
     if(false(),false(),y,xs,ys,x) -> sumList(ys,x)
     sum(xs) -> sumList(xs,0())
    Subterm Criterion Processor:
     simple projection:
      pi(inc#) = 0
     problem:
      DPs:
       
      TRS:
       isEmpty(cons(x,xs)) -> false()
       isEmpty(nil()) -> true()
       isZero(0()) -> true()
       isZero(s(x)) -> false()
       head(cons(x,xs)) -> x
       tail(cons(x,xs)) -> xs
       tail(nil()) -> nil()
       p(s(s(x))) -> s(p(s(x)))
       p(s(0())) -> 0()
       p(0()) -> 0()
       inc(s(x)) -> s(inc(x))
       inc(0()) -> s(0())
       sumList(xs,y) ->
       if(isEmpty(xs),isZero(head(xs)),y,tail(xs),cons(p(head(xs)),tail(xs)),inc(y))
       if(true(),b,y,xs,ys,x) -> y
       if(false(),true(),y,xs,ys,x) -> sumList(xs,y)
       if(false(),false(),y,xs,ys,x) -> sumList(ys,x)
       sum(xs) -> sumList(xs,0())
     Qed