/export/starexec/sandbox2/solver/bin/starexec_run_ttt2-1.17+nonreach /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


YES

Problem:
 isEmpty(nil()) -> true()
 isEmpty(cons(x,xs)) -> false()
 last(cons(x,nil())) -> x
 last(cons(x,cons(y,ys))) -> last(cons(y,ys))
 dropLast(nil()) -> nil()
 dropLast(cons(x,nil())) -> nil()
 dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
 append(nil(),ys) -> ys
 append(cons(x,xs),ys) -> cons(x,append(xs,ys))
 reverse(xs) -> rev(xs,nil())
 rev(xs,ys) -> if(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
 if(true(),xs,ys,zs) -> zs
 if(false(),xs,ys,zs) -> rev(xs,ys)

Proof:
 DP Processor:
  DPs:
   last#(cons(x,cons(y,ys))) -> last#(cons(y,ys))
   dropLast#(cons(x,cons(y,ys))) -> dropLast#(cons(y,ys))
   append#(cons(x,xs),ys) -> append#(xs,ys)
   reverse#(xs) -> rev#(xs,nil())
   rev#(xs,ys) -> last#(xs)
   rev#(xs,ys) -> append#(ys,last(xs))
   rev#(xs,ys) -> dropLast#(xs)
   rev#(xs,ys) -> isEmpty#(xs)
   rev#(xs,ys) -> if#(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
   if#(false(),xs,ys,zs) -> rev#(xs,ys)
  TRS:
   isEmpty(nil()) -> true()
   isEmpty(cons(x,xs)) -> false()
   last(cons(x,nil())) -> x
   last(cons(x,cons(y,ys))) -> last(cons(y,ys))
   dropLast(nil()) -> nil()
   dropLast(cons(x,nil())) -> nil()
   dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
   append(nil(),ys) -> ys
   append(cons(x,xs),ys) -> cons(x,append(xs,ys))
   reverse(xs) -> rev(xs,nil())
   rev(xs,ys) -> if(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
   if(true(),xs,ys,zs) -> zs
   if(false(),xs,ys,zs) -> rev(xs,ys)
  TDG Processor:
   DPs:
    last#(cons(x,cons(y,ys))) -> last#(cons(y,ys))
    dropLast#(cons(x,cons(y,ys))) -> dropLast#(cons(y,ys))
    append#(cons(x,xs),ys) -> append#(xs,ys)
    reverse#(xs) -> rev#(xs,nil())
    rev#(xs,ys) -> last#(xs)
    rev#(xs,ys) -> append#(ys,last(xs))
    rev#(xs,ys) -> dropLast#(xs)
    rev#(xs,ys) -> isEmpty#(xs)
    rev#(xs,ys) -> if#(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
    if#(false(),xs,ys,zs) -> rev#(xs,ys)
   TRS:
    isEmpty(nil()) -> true()
    isEmpty(cons(x,xs)) -> false()
    last(cons(x,nil())) -> x
    last(cons(x,cons(y,ys))) -> last(cons(y,ys))
    dropLast(nil()) -> nil()
    dropLast(cons(x,nil())) -> nil()
    dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
    append(nil(),ys) -> ys
    append(cons(x,xs),ys) -> cons(x,append(xs,ys))
    reverse(xs) -> rev(xs,nil())
    rev(xs,ys) -> if(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
    if(true(),xs,ys,zs) -> zs
    if(false(),xs,ys,zs) -> rev(xs,ys)
   graph:
    if#(false(),xs,ys,zs) -> rev#(xs,ys) ->
    rev#(xs,ys) -> if#(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
    if#(false(),xs,ys,zs) -> rev#(xs,ys) ->
    rev#(xs,ys) -> isEmpty#(xs)
    if#(false(),xs,ys,zs) -> rev#(xs,ys) ->
    rev#(xs,ys) -> dropLast#(xs)
    if#(false(),xs,ys,zs) -> rev#(xs,ys) ->
    rev#(xs,ys) -> append#(ys,last(xs))
    if#(false(),xs,ys,zs) -> rev#(xs,ys) ->
    rev#(xs,ys) -> last#(xs)
    rev#(xs,ys) -> if#(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys) ->
    if#(false(),xs,ys,zs) -> rev#(xs,ys)
    rev#(xs,ys) -> append#(ys,last(xs)) ->
    append#(cons(x,xs),ys) -> append#(xs,ys)
    rev#(xs,ys) -> dropLast#(xs) ->
    dropLast#(cons(x,cons(y,ys))) -> dropLast#(cons(y,ys))
    rev#(xs,ys) -> last#(xs) ->
    last#(cons(x,cons(y,ys))) -> last#(cons(y,ys))
    reverse#(xs) -> rev#(xs,nil()) ->
    rev#(xs,ys) -> if#(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
    reverse#(xs) -> rev#(xs,nil()) -> rev#(xs,ys) -> isEmpty#(xs)
    reverse#(xs) -> rev#(xs,nil()) -> rev#(xs,ys) -> dropLast#(xs)
    reverse#(xs) -> rev#(xs,nil()) ->
    rev#(xs,ys) -> append#(ys,last(xs))
    reverse#(xs) -> rev#(xs,nil()) ->
    rev#(xs,ys) -> last#(xs)
    append#(cons(x,xs),ys) -> append#(xs,ys) ->
    append#(cons(x,xs),ys) -> append#(xs,ys)
    dropLast#(cons(x,cons(y,ys))) -> dropLast#(cons(y,ys)) ->
    dropLast#(cons(x,cons(y,ys))) -> dropLast#(cons(y,ys))
    last#(cons(x,cons(y,ys))) -> last#(cons(y,ys)) ->
    last#(cons(x,cons(y,ys))) -> last#(cons(y,ys))
   SCC Processor:
    #sccs: 4
    #rules: 5
    #arcs: 17/100
    DPs:
     if#(false(),xs,ys,zs) -> rev#(xs,ys)
     rev#(xs,ys) -> if#(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
    TRS:
     isEmpty(nil()) -> true()
     isEmpty(cons(x,xs)) -> false()
     last(cons(x,nil())) -> x
     last(cons(x,cons(y,ys))) -> last(cons(y,ys))
     dropLast(nil()) -> nil()
     dropLast(cons(x,nil())) -> nil()
     dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
     append(nil(),ys) -> ys
     append(cons(x,xs),ys) -> cons(x,append(xs,ys))
     reverse(xs) -> rev(xs,nil())
     rev(xs,ys) -> if(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
     if(true(),xs,ys,zs) -> zs
     if(false(),xs,ys,zs) -> rev(xs,ys)
    Usable Rule Processor:
     DPs:
      if#(false(),xs,ys,zs) -> rev#(xs,ys)
      rev#(xs,ys) -> if#(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
     TRS:
      last(cons(x,nil())) -> x
      last(cons(x,cons(y,ys))) -> last(cons(y,ys))
      append(nil(),ys) -> ys
      append(cons(x,xs),ys) -> cons(x,append(xs,ys))
      dropLast(nil()) -> nil()
      dropLast(cons(x,nil())) -> nil()
      dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
      isEmpty(nil()) -> true()
      isEmpty(cons(x,xs)) -> false()
     Arctic Interpretation Processor:
      dimension: 1
      usable rules:
       dropLast(nil()) -> nil()
       dropLast(cons(x,nil())) -> nil()
       dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
       isEmpty(nil()) -> true()
       isEmpty(cons(x,xs)) -> false()
      interpretation:
       [if#](x0, x1, x2, x3) = 1x0 + 2x1,
       
       [rev#](x0, x1) = 2x0 + 4,
       
       [append](x0, x1) = 2x1 + -10,
       
       [dropLast](x0) = -1x0 + 0,
       
       [last](x0) = x0 + -10,
       
       [false] = 3,
       
       [cons](x0, x1) = 2x1 + 3,
       
       [true] = 0,
       
       [isEmpty](x0) = x0,
       
       [nil] = 0
      orientation:
       if#(false(),xs,ys,zs) = 2xs + 4 >= 2xs + 4 = rev#(xs,ys)
       
       rev#(xs,ys) = 2xs + 4 >= 1xs + 2 = if#(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
       
       last(cons(x,nil())) = 3 >= x = x
       
       last(cons(x,cons(y,ys))) = 4ys + 5 >= 2ys + 3 = last(cons(y,ys))
       
       append(nil(),ys) = 2ys + -10 >= ys = ys
       
       append(cons(x,xs),ys) = 2ys + -10 >= 4ys + 3 = cons(x,append(xs,ys))
       
       dropLast(nil()) = 0 >= 0 = nil()
       
       dropLast(cons(x,nil())) = 2 >= 0 = nil()
       
       dropLast(cons(x,cons(y,ys))) = 3ys + 4 >= 3ys + 4 = cons(x,dropLast(cons(y,ys)))
       
       isEmpty(nil()) = 0 >= 0 = true()
       
       isEmpty(cons(x,xs)) = 2xs + 3 >= 3 = false()
      problem:
       DPs:
        if#(false(),xs,ys,zs) -> rev#(xs,ys)
       TRS:
        last(cons(x,nil())) -> x
        last(cons(x,cons(y,ys))) -> last(cons(y,ys))
        append(nil(),ys) -> ys
        append(cons(x,xs),ys) -> cons(x,append(xs,ys))
        dropLast(nil()) -> nil()
        dropLast(cons(x,nil())) -> nil()
        dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
        isEmpty(nil()) -> true()
        isEmpty(cons(x,xs)) -> false()
      Restore Modifier:
       DPs:
        if#(false(),xs,ys,zs) -> rev#(xs,ys)
       TRS:
        isEmpty(nil()) -> true()
        isEmpty(cons(x,xs)) -> false()
        last(cons(x,nil())) -> x
        last(cons(x,cons(y,ys))) -> last(cons(y,ys))
        dropLast(nil()) -> nil()
        dropLast(cons(x,nil())) -> nil()
        dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
        append(nil(),ys) -> ys
        append(cons(x,xs),ys) -> cons(x,append(xs,ys))
        reverse(xs) -> rev(xs,nil())
        rev(xs,ys) -> if(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
        if(true(),xs,ys,zs) -> zs
        if(false(),xs,ys,zs) -> rev(xs,ys)
       SCC Processor:
        #sccs: 0
        #rules: 0
        #arcs: 2/1
        
    
    DPs:
     dropLast#(cons(x,cons(y,ys))) -> dropLast#(cons(y,ys))
    TRS:
     isEmpty(nil()) -> true()
     isEmpty(cons(x,xs)) -> false()
     last(cons(x,nil())) -> x
     last(cons(x,cons(y,ys))) -> last(cons(y,ys))
     dropLast(nil()) -> nil()
     dropLast(cons(x,nil())) -> nil()
     dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
     append(nil(),ys) -> ys
     append(cons(x,xs),ys) -> cons(x,append(xs,ys))
     reverse(xs) -> rev(xs,nil())
     rev(xs,ys) -> if(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
     if(true(),xs,ys,zs) -> zs
     if(false(),xs,ys,zs) -> rev(xs,ys)
    Subterm Criterion Processor:
     simple projection:
      pi(dropLast#) = 0
     problem:
      DPs:
       
      TRS:
       isEmpty(nil()) -> true()
       isEmpty(cons(x,xs)) -> false()
       last(cons(x,nil())) -> x
       last(cons(x,cons(y,ys))) -> last(cons(y,ys))
       dropLast(nil()) -> nil()
       dropLast(cons(x,nil())) -> nil()
       dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
       append(nil(),ys) -> ys
       append(cons(x,xs),ys) -> cons(x,append(xs,ys))
       reverse(xs) -> rev(xs,nil())
       rev(xs,ys) -> if(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
       if(true(),xs,ys,zs) -> zs
       if(false(),xs,ys,zs) -> rev(xs,ys)
     Qed
    
    DPs:
     append#(cons(x,xs),ys) -> append#(xs,ys)
    TRS:
     isEmpty(nil()) -> true()
     isEmpty(cons(x,xs)) -> false()
     last(cons(x,nil())) -> x
     last(cons(x,cons(y,ys))) -> last(cons(y,ys))
     dropLast(nil()) -> nil()
     dropLast(cons(x,nil())) -> nil()
     dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
     append(nil(),ys) -> ys
     append(cons(x,xs),ys) -> cons(x,append(xs,ys))
     reverse(xs) -> rev(xs,nil())
     rev(xs,ys) -> if(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
     if(true(),xs,ys,zs) -> zs
     if(false(),xs,ys,zs) -> rev(xs,ys)
    Subterm Criterion Processor:
     simple projection:
      pi(append#) = 0
     problem:
      DPs:
       
      TRS:
       isEmpty(nil()) -> true()
       isEmpty(cons(x,xs)) -> false()
       last(cons(x,nil())) -> x
       last(cons(x,cons(y,ys))) -> last(cons(y,ys))
       dropLast(nil()) -> nil()
       dropLast(cons(x,nil())) -> nil()
       dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
       append(nil(),ys) -> ys
       append(cons(x,xs),ys) -> cons(x,append(xs,ys))
       reverse(xs) -> rev(xs,nil())
       rev(xs,ys) -> if(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
       if(true(),xs,ys,zs) -> zs
       if(false(),xs,ys,zs) -> rev(xs,ys)
     Qed
    
    DPs:
     last#(cons(x,cons(y,ys))) -> last#(cons(y,ys))
    TRS:
     isEmpty(nil()) -> true()
     isEmpty(cons(x,xs)) -> false()
     last(cons(x,nil())) -> x
     last(cons(x,cons(y,ys))) -> last(cons(y,ys))
     dropLast(nil()) -> nil()
     dropLast(cons(x,nil())) -> nil()
     dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
     append(nil(),ys) -> ys
     append(cons(x,xs),ys) -> cons(x,append(xs,ys))
     reverse(xs) -> rev(xs,nil())
     rev(xs,ys) -> if(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
     if(true(),xs,ys,zs) -> zs
     if(false(),xs,ys,zs) -> rev(xs,ys)
    Subterm Criterion Processor:
     simple projection:
      pi(last#) = 0
     problem:
      DPs:
       
      TRS:
       isEmpty(nil()) -> true()
       isEmpty(cons(x,xs)) -> false()
       last(cons(x,nil())) -> x
       last(cons(x,cons(y,ys))) -> last(cons(y,ys))
       dropLast(nil()) -> nil()
       dropLast(cons(x,nil())) -> nil()
       dropLast(cons(x,cons(y,ys))) -> cons(x,dropLast(cons(y,ys)))
       append(nil(),ys) -> ys
       append(cons(x,xs),ys) -> cons(x,append(xs,ys))
       reverse(xs) -> rev(xs,nil())
       rev(xs,ys) -> if(isEmpty(xs),dropLast(xs),append(ys,last(xs)),ys)
       if(true(),xs,ys,zs) -> zs
       if(false(),xs,ys,zs) -> rev(xs,ys)
     Qed