/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:
 empty(nil()) -> true()
 empty(cons(x,l)) -> false()
 head(cons(x,l)) -> x
 tail(nil()) -> nil()
 tail(cons(x,l)) -> l
 rev(nil()) -> nil()
 rev(cons(x,l)) -> cons(rev1(x,l),rev2(x,l))
 last(x,l) -> if(empty(l),x,l)
 if(true(),x,l) -> x
 if(false(),x,l) -> last(head(l),tail(l))
 rev2(x,nil()) -> nil()
 rev2(x,cons(y,l)) -> rev(cons(x,rev2(y,l)))

Proof:
 DP Processor:
  DPs:
   rev#(cons(x,l)) -> rev2#(x,l)
   last#(x,l) -> empty#(l)
   last#(x,l) -> if#(empty(l),x,l)
   if#(false(),x,l) -> tail#(l)
   if#(false(),x,l) -> head#(l)
   if#(false(),x,l) -> last#(head(l),tail(l))
   rev2#(x,cons(y,l)) -> rev2#(y,l)
   rev2#(x,cons(y,l)) -> rev#(cons(x,rev2(y,l)))
  TRS:
   empty(nil()) -> true()
   empty(cons(x,l)) -> false()
   head(cons(x,l)) -> x
   tail(nil()) -> nil()
   tail(cons(x,l)) -> l
   rev(nil()) -> nil()
   rev(cons(x,l)) -> cons(rev1(x,l),rev2(x,l))
   last(x,l) -> if(empty(l),x,l)
   if(true(),x,l) -> x
   if(false(),x,l) -> last(head(l),tail(l))
   rev2(x,nil()) -> nil()
   rev2(x,cons(y,l)) -> rev(cons(x,rev2(y,l)))
  TDG Processor:
   DPs:
    rev#(cons(x,l)) -> rev2#(x,l)
    last#(x,l) -> empty#(l)
    last#(x,l) -> if#(empty(l),x,l)
    if#(false(),x,l) -> tail#(l)
    if#(false(),x,l) -> head#(l)
    if#(false(),x,l) -> last#(head(l),tail(l))
    rev2#(x,cons(y,l)) -> rev2#(y,l)
    rev2#(x,cons(y,l)) -> rev#(cons(x,rev2(y,l)))
   TRS:
    empty(nil()) -> true()
    empty(cons(x,l)) -> false()
    head(cons(x,l)) -> x
    tail(nil()) -> nil()
    tail(cons(x,l)) -> l
    rev(nil()) -> nil()
    rev(cons(x,l)) -> cons(rev1(x,l),rev2(x,l))
    last(x,l) -> if(empty(l),x,l)
    if(true(),x,l) -> x
    if(false(),x,l) -> last(head(l),tail(l))
    rev2(x,nil()) -> nil()
    rev2(x,cons(y,l)) -> rev(cons(x,rev2(y,l)))
   graph:
    if#(false(),x,l) -> last#(head(l),tail(l)) ->
    last#(x,l) -> if#(empty(l),x,l)
    if#(false(),x,l) -> last#(head(l),tail(l)) ->
    last#(x,l) -> empty#(l)
    last#(x,l) -> if#(empty(l),x,l) ->
    if#(false(),x,l) -> last#(head(l),tail(l))
    last#(x,l) -> if#(empty(l),x,l) -> if#(false(),x,l) -> head#(l)
    last#(x,l) -> if#(empty(l),x,l) -> if#(false(),x,l) -> tail#(l)
    rev2#(x,cons(y,l)) -> rev2#(y,l) ->
    rev2#(x,cons(y,l)) -> rev#(cons(x,rev2(y,l)))
    rev2#(x,cons(y,l)) -> rev2#(y,l) ->
    rev2#(x,cons(y,l)) -> rev2#(y,l)
    rev2#(x,cons(y,l)) -> rev#(cons(x,rev2(y,l))) ->
    rev#(cons(x,l)) -> rev2#(x,l)
    rev#(cons(x,l)) -> rev2#(x,l) ->
    rev2#(x,cons(y,l)) -> rev#(cons(x,rev2(y,l)))
    rev#(cons(x,l)) -> rev2#(x,l) -> rev2#(x,cons(y,l)) -> rev2#(y,l)
   SCC Processor:
    #sccs: 2
    #rules: 5
    #arcs: 10/64
    DPs:
     rev2#(x,cons(y,l)) -> rev2#(y,l)
     rev2#(x,cons(y,l)) -> rev#(cons(x,rev2(y,l)))
     rev#(cons(x,l)) -> rev2#(x,l)
    TRS:
     empty(nil()) -> true()
     empty(cons(x,l)) -> false()
     head(cons(x,l)) -> x
     tail(nil()) -> nil()
     tail(cons(x,l)) -> l
     rev(nil()) -> nil()
     rev(cons(x,l)) -> cons(rev1(x,l),rev2(x,l))
     last(x,l) -> if(empty(l),x,l)
     if(true(),x,l) -> x
     if(false(),x,l) -> last(head(l),tail(l))
     rev2(x,nil()) -> nil()
     rev2(x,cons(y,l)) -> rev(cons(x,rev2(y,l)))
    Subterm Criterion Processor:
     simple projection:
      pi(cons) = [1,1]
      pi(rev) = 0
      pi(rev2) = 1
      pi(rev#) = [0,0]
      pi(rev2#) = [1,1]
     problem:
      DPs:
       rev2#(x,cons(y,l)) -> rev#(cons(x,rev2(y,l)))
      TRS:
       empty(nil()) -> true()
       empty(cons(x,l)) -> false()
       head(cons(x,l)) -> x
       tail(nil()) -> nil()
       tail(cons(x,l)) -> l
       rev(nil()) -> nil()
       rev(cons(x,l)) -> cons(rev1(x,l),rev2(x,l))
       last(x,l) -> if(empty(l),x,l)
       if(true(),x,l) -> x
       if(false(),x,l) -> last(head(l),tail(l))
       rev2(x,nil()) -> nil()
       rev2(x,cons(y,l)) -> rev(cons(x,rev2(y,l)))
     SCC Processor:
      #sccs: 0
      #rules: 0
      #arcs: 5/1
      
    
    DPs:
     if#(false(),x,l) -> last#(head(l),tail(l))
     last#(x,l) -> if#(empty(l),x,l)
    TRS:
     empty(nil()) -> true()
     empty(cons(x,l)) -> false()
     head(cons(x,l)) -> x
     tail(nil()) -> nil()
     tail(cons(x,l)) -> l
     rev(nil()) -> nil()
     rev(cons(x,l)) -> cons(rev1(x,l),rev2(x,l))
     last(x,l) -> if(empty(l),x,l)
     if(true(),x,l) -> x
     if(false(),x,l) -> last(head(l),tail(l))
     rev2(x,nil()) -> nil()
     rev2(x,cons(y,l)) -> rev(cons(x,rev2(y,l)))
    Usable Rule Processor:
     DPs:
      if#(false(),x,l) -> last#(head(l),tail(l))
      last#(x,l) -> if#(empty(l),x,l)
     TRS:
      tail(nil()) -> nil()
      tail(cons(x,l)) -> l
      head(cons(x,l)) -> x
      empty(nil()) -> true()
      empty(cons(x,l)) -> false()
     Arctic Interpretation Processor:
      dimension: 1
      usable rules:
       tail(nil()) -> nil()
       tail(cons(x,l)) -> l
       head(cons(x,l)) -> x
       empty(nil()) -> true()
       empty(cons(x,l)) -> false()
      interpretation:
       [if#](x0, x1, x2) = -1x0 + -16x1 + 2x2,
       
       [last#](x0, x1) = x0 + 3x1 + 0,
       
       [tail](x0) = -2x0 + 1,
       
       [head](x0) = x0 + 0,
       
       [false] = 5,
       
       [cons](x0, x1) = x0 + 2x1 + 5,
       
       [true] = 0,
       
       [empty](x0) = x0 + 0,
       
       [nil] = 1
      orientation:
       if#(false(),x,l) = 2l + -16x + 4 >= 1l + 4 = last#(head(l),tail(l))
       
       last#(x,l) = 3l + x + 0 >= 2l + -16x + -1 = if#(empty(l),x,l)
       
       tail(nil()) = 1 >= 1 = nil()
       
       tail(cons(x,l)) = l + -2x + 3 >= l = l
       
       head(cons(x,l)) = 2l + x + 5 >= x = x
       
       empty(nil()) = 1 >= 0 = true()
       
       empty(cons(x,l)) = 2l + x + 5 >= 5 = false()
      problem:
       DPs:
        if#(false(),x,l) -> last#(head(l),tail(l))
       TRS:
        tail(nil()) -> nil()
        tail(cons(x,l)) -> l
        head(cons(x,l)) -> x
        empty(nil()) -> true()
        empty(cons(x,l)) -> false()
      Restore Modifier:
       DPs:
        if#(false(),x,l) -> last#(head(l),tail(l))
       TRS:
        empty(nil()) -> true()
        empty(cons(x,l)) -> false()
        head(cons(x,l)) -> x
        tail(nil()) -> nil()
        tail(cons(x,l)) -> l
        rev(nil()) -> nil()
        rev(cons(x,l)) -> cons(rev1(x,l),rev2(x,l))
        last(x,l) -> if(empty(l),x,l)
        if(true(),x,l) -> x
        if(false(),x,l) -> last(head(l),tail(l))
        rev2(x,nil()) -> nil()
        rev2(x,cons(y,l)) -> rev(cons(x,rev2(y,l)))
       SCC Processor:
        #sccs: 0
        #rules: 0
        #arcs: 2/1