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


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


YES

Problem:
 empty(nil()) -> true()
 empty(cons(x,y)) -> false()
 tail(nil()) -> nil()
 tail(cons(x,y)) -> y
 head(cons(x,y)) -> x
 zero(0()) -> true()
 zero(s(x)) -> false()
 p(0()) -> 0()
 p(s(0())) -> 0()
 p(s(s(x))) -> s(p(s(x)))
 intlist(x) -> if_intlist(empty(x),x)
 if_intlist(true(),x) -> nil()
 if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
 int(x,y) -> if_int(zero(x),zero(y),x,y)
 if_int(true(),b,x,y) -> if1(b,x,y)
 if_int(false(),b,x,y) -> if2(b,x,y)
 if1(true(),x,y) -> cons(0(),nil())
 if1(false(),x,y) -> cons(0(),int(s(0()),y))
 if2(true(),x,y) -> nil()
 if2(false(),x,y) -> intlist(int(p(x),p(y)))

Proof:
 DP Processor:
  DPs:
   p#(s(s(x))) -> p#(s(x))
   intlist#(x) -> empty#(x)
   intlist#(x) -> if_intlist#(empty(x),x)
   if_intlist#(false(),x) -> tail#(x)
   if_intlist#(false(),x) -> intlist#(tail(x))
   if_intlist#(false(),x) -> head#(x)
   int#(x,y) -> zero#(y)
   int#(x,y) -> zero#(x)
   int#(x,y) -> if_int#(zero(x),zero(y),x,y)
   if_int#(true(),b,x,y) -> if1#(b,x,y)
   if_int#(false(),b,x,y) -> if2#(b,x,y)
   if1#(false(),x,y) -> int#(s(0()),y)
   if2#(false(),x,y) -> p#(y)
   if2#(false(),x,y) -> p#(x)
   if2#(false(),x,y) -> int#(p(x),p(y))
   if2#(false(),x,y) -> intlist#(int(p(x),p(y)))
  TRS:
   empty(nil()) -> true()
   empty(cons(x,y)) -> false()
   tail(nil()) -> nil()
   tail(cons(x,y)) -> y
   head(cons(x,y)) -> x
   zero(0()) -> true()
   zero(s(x)) -> false()
   p(0()) -> 0()
   p(s(0())) -> 0()
   p(s(s(x))) -> s(p(s(x)))
   intlist(x) -> if_intlist(empty(x),x)
   if_intlist(true(),x) -> nil()
   if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
   int(x,y) -> if_int(zero(x),zero(y),x,y)
   if_int(true(),b,x,y) -> if1(b,x,y)
   if_int(false(),b,x,y) -> if2(b,x,y)
   if1(true(),x,y) -> cons(0(),nil())
   if1(false(),x,y) -> cons(0(),int(s(0()),y))
   if2(true(),x,y) -> nil()
   if2(false(),x,y) -> intlist(int(p(x),p(y)))
  TDG Processor:
   DPs:
    p#(s(s(x))) -> p#(s(x))
    intlist#(x) -> empty#(x)
    intlist#(x) -> if_intlist#(empty(x),x)
    if_intlist#(false(),x) -> tail#(x)
    if_intlist#(false(),x) -> intlist#(tail(x))
    if_intlist#(false(),x) -> head#(x)
    int#(x,y) -> zero#(y)
    int#(x,y) -> zero#(x)
    int#(x,y) -> if_int#(zero(x),zero(y),x,y)
    if_int#(true(),b,x,y) -> if1#(b,x,y)
    if_int#(false(),b,x,y) -> if2#(b,x,y)
    if1#(false(),x,y) -> int#(s(0()),y)
    if2#(false(),x,y) -> p#(y)
    if2#(false(),x,y) -> p#(x)
    if2#(false(),x,y) -> int#(p(x),p(y))
    if2#(false(),x,y) -> intlist#(int(p(x),p(y)))
   TRS:
    empty(nil()) -> true()
    empty(cons(x,y)) -> false()
    tail(nil()) -> nil()
    tail(cons(x,y)) -> y
    head(cons(x,y)) -> x
    zero(0()) -> true()
    zero(s(x)) -> false()
    p(0()) -> 0()
    p(s(0())) -> 0()
    p(s(s(x))) -> s(p(s(x)))
    intlist(x) -> if_intlist(empty(x),x)
    if_intlist(true(),x) -> nil()
    if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
    int(x,y) -> if_int(zero(x),zero(y),x,y)
    if_int(true(),b,x,y) -> if1(b,x,y)
    if_int(false(),b,x,y) -> if2(b,x,y)
    if1(true(),x,y) -> cons(0(),nil())
    if1(false(),x,y) -> cons(0(),int(s(0()),y))
    if2(true(),x,y) -> nil()
    if2(false(),x,y) -> intlist(int(p(x),p(y)))
   graph:
    if2#(false(),x,y) -> int#(p(x),p(y)) ->
    int#(x,y) -> if_int#(zero(x),zero(y),x,y)
    if2#(false(),x,y) -> int#(p(x),p(y)) ->
    int#(x,y) -> zero#(x)
    if2#(false(),x,y) -> int#(p(x),p(y)) ->
    int#(x,y) -> zero#(y)
    if2#(false(),x,y) -> intlist#(int(p(x),p(y))) ->
    intlist#(x) -> if_intlist#(empty(x),x)
    if2#(false(),x,y) -> intlist#(int(p(x),p(y))) ->
    intlist#(x) -> empty#(x)
    if2#(false(),x,y) -> p#(y) -> p#(s(s(x))) -> p#(s(x))
    if2#(false(),x,y) -> p#(x) -> p#(s(s(x))) -> p#(s(x))
    if1#(false(),x,y) -> int#(s(0()),y) ->
    int#(x,y) -> if_int#(zero(x),zero(y),x,y)
    if1#(false(),x,y) -> int#(s(0()),y) -> int#(x,y) -> zero#(x)
    if1#(false(),x,y) -> int#(s(0()),y) ->
    int#(x,y) -> zero#(y)
    if_int#(false(),b,x,y) -> if2#(b,x,y) ->
    if2#(false(),x,y) -> intlist#(int(p(x),p(y)))
    if_int#(false(),b,x,y) -> if2#(b,x,y) ->
    if2#(false(),x,y) -> int#(p(x),p(y))
    if_int#(false(),b,x,y) -> if2#(b,x,y) ->
    if2#(false(),x,y) -> p#(x)
    if_int#(false(),b,x,y) -> if2#(b,x,y) ->
    if2#(false(),x,y) -> p#(y)
    if_int#(true(),b,x,y) -> if1#(b,x,y) ->
    if1#(false(),x,y) -> int#(s(0()),y)
    int#(x,y) -> if_int#(zero(x),zero(y),x,y) ->
    if_int#(false(),b,x,y) -> if2#(b,x,y)
    int#(x,y) -> if_int#(zero(x),zero(y),x,y) ->
    if_int#(true(),b,x,y) -> if1#(b,x,y)
    if_intlist#(false(),x) -> intlist#(tail(x)) ->
    intlist#(x) -> if_intlist#(empty(x),x)
    if_intlist#(false(),x) -> intlist#(tail(x)) ->
    intlist#(x) -> empty#(x)
    intlist#(x) -> if_intlist#(empty(x),x) ->
    if_intlist#(false(),x) -> head#(x)
    intlist#(x) -> if_intlist#(empty(x),x) ->
    if_intlist#(false(),x) -> intlist#(tail(x))
    intlist#(x) -> if_intlist#(empty(x),x) ->
    if_intlist#(false(),x) -> tail#(x)
    p#(s(s(x))) -> p#(s(x)) -> p#(s(s(x))) -> p#(s(x))
   SCC Processor:
    #sccs: 3
    #rules: 8
    #arcs: 23/256
    DPs:
     if2#(false(),x,y) -> int#(p(x),p(y))
     int#(x,y) -> if_int#(zero(x),zero(y),x,y)
     if_int#(true(),b,x,y) -> if1#(b,x,y)
     if1#(false(),x,y) -> int#(s(0()),y)
     if_int#(false(),b,x,y) -> if2#(b,x,y)
    TRS:
     empty(nil()) -> true()
     empty(cons(x,y)) -> false()
     tail(nil()) -> nil()
     tail(cons(x,y)) -> y
     head(cons(x,y)) -> x
     zero(0()) -> true()
     zero(s(x)) -> false()
     p(0()) -> 0()
     p(s(0())) -> 0()
     p(s(s(x))) -> s(p(s(x)))
     intlist(x) -> if_intlist(empty(x),x)
     if_intlist(true(),x) -> nil()
     if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
     int(x,y) -> if_int(zero(x),zero(y),x,y)
     if_int(true(),b,x,y) -> if1(b,x,y)
     if_int(false(),b,x,y) -> if2(b,x,y)
     if1(true(),x,y) -> cons(0(),nil())
     if1(false(),x,y) -> cons(0(),int(s(0()),y))
     if2(true(),x,y) -> nil()
     if2(false(),x,y) -> intlist(int(p(x),p(y)))
    Usable Rule Processor:
     DPs:
      if2#(false(),x,y) -> int#(p(x),p(y))
      int#(x,y) -> if_int#(zero(x),zero(y),x,y)
      if_int#(true(),b,x,y) -> if1#(b,x,y)
      if1#(false(),x,y) -> int#(s(0()),y)
      if_int#(false(),b,x,y) -> if2#(b,x,y)
     TRS:
      p(0()) -> 0()
      p(s(0())) -> 0()
      p(s(s(x))) -> s(p(s(x)))
      zero(0()) -> true()
      zero(s(x)) -> false()
     Arctic Interpretation Processor:
      dimension: 1
      usable rules:
       p(0()) -> 0()
       p(s(0())) -> 0()
       p(s(s(x))) -> s(p(s(x)))
       zero(0()) -> true()
       zero(s(x)) -> false()
      interpretation:
       [if2#](x0, x1, x2) = x0 + x2,
       
       [if1#](x0, x1, x2) = -1x0 + x2,
       
       [if_int#](x0, x1, x2, x3) = x1 + x3,
       
       [int#](x0, x1) = x1 + 0,
       
       [p](x0) = -1x0 + 0,
       
       [s](x0) = 2x0 + 1,
       
       [zero](x0) = x0 + -8,
       
       [0] = 0,
       
       [false] = 1,
       
       [true] = 0
      orientation:
       if2#(false(),x,y) = y + 1 >= -1y + 0 = int#(p(x),p(y))
       
       int#(x,y) = y + 0 >= y + -8 = if_int#(zero(x),zero(y),x,y)
       
       if_int#(true(),b,x,y) = b + y >= -1b + y = if1#(b,x,y)
       
       if1#(false(),x,y) = y + 0 >= y + 0 = int#(s(0()),y)
       
       if_int#(false(),b,x,y) = b + y >= b + y = if2#(b,x,y)
       
       p(0()) = 0 >= 0 = 0()
       
       p(s(0())) = 1 >= 0 = 0()
       
       p(s(s(x))) = 3x + 2 >= 3x + 2 = s(p(s(x)))
       
       zero(0()) = 0 >= 0 = true()
       
       zero(s(x)) = 2x + 1 >= 1 = false()
      problem:
       DPs:
        int#(x,y) -> if_int#(zero(x),zero(y),x,y)
        if_int#(true(),b,x,y) -> if1#(b,x,y)
        if1#(false(),x,y) -> int#(s(0()),y)
        if_int#(false(),b,x,y) -> if2#(b,x,y)
       TRS:
        p(0()) -> 0()
        p(s(0())) -> 0()
        p(s(s(x))) -> s(p(s(x)))
        zero(0()) -> true()
        zero(s(x)) -> false()
      Restore Modifier:
       DPs:
        int#(x,y) -> if_int#(zero(x),zero(y),x,y)
        if_int#(true(),b,x,y) -> if1#(b,x,y)
        if1#(false(),x,y) -> int#(s(0()),y)
        if_int#(false(),b,x,y) -> if2#(b,x,y)
       TRS:
        empty(nil()) -> true()
        empty(cons(x,y)) -> false()
        tail(nil()) -> nil()
        tail(cons(x,y)) -> y
        head(cons(x,y)) -> x
        zero(0()) -> true()
        zero(s(x)) -> false()
        p(0()) -> 0()
        p(s(0())) -> 0()
        p(s(s(x))) -> s(p(s(x)))
        intlist(x) -> if_intlist(empty(x),x)
        if_intlist(true(),x) -> nil()
        if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
        int(x,y) -> if_int(zero(x),zero(y),x,y)
        if_int(true(),b,x,y) -> if1(b,x,y)
        if_int(false(),b,x,y) -> if2(b,x,y)
        if1(true(),x,y) -> cons(0(),nil())
        if1(false(),x,y) -> cons(0(),int(s(0()),y))
        if2(true(),x,y) -> nil()
        if2(false(),x,y) -> intlist(int(p(x),p(y)))
       SCC Processor:
        #sccs: 1
        #rules: 3
        #arcs: 6/16
        DPs:
         if1#(false(),x,y) -> int#(s(0()),y)
         int#(x,y) -> if_int#(zero(x),zero(y),x,y)
         if_int#(true(),b,x,y) -> if1#(b,x,y)
        TRS:
         empty(nil()) -> true()
         empty(cons(x,y)) -> false()
         tail(nil()) -> nil()
         tail(cons(x,y)) -> y
         head(cons(x,y)) -> x
         zero(0()) -> true()
         zero(s(x)) -> false()
         p(0()) -> 0()
         p(s(0())) -> 0()
         p(s(s(x))) -> s(p(s(x)))
         intlist(x) -> if_intlist(empty(x),x)
         if_intlist(true(),x) -> nil()
         if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
         int(x,y) -> if_int(zero(x),zero(y),x,y)
         if_int(true(),b,x,y) -> if1(b,x,y)
         if_int(false(),b,x,y) -> if2(b,x,y)
         if1(true(),x,y) -> cons(0(),nil())
         if1(false(),x,y) -> cons(0(),int(s(0()),y))
         if2(true(),x,y) -> nil()
         if2(false(),x,y) -> intlist(int(p(x),p(y)))
        Usable Rule Processor:
         DPs:
          if1#(false(),x,y) -> int#(s(0()),y)
          int#(x,y) -> if_int#(zero(x),zero(y),x,y)
          if_int#(true(),b,x,y) -> if1#(b,x,y)
         TRS:
          zero(0()) -> true()
          zero(s(x)) -> false()
         Arctic Interpretation Processor:
          dimension: 1
          usable rules:
           zero(0()) -> true()
           zero(s(x)) -> false()
          interpretation:
           [if1#](x0, x1, x2) = -16x1 + 6,
           
           [if_int#](x0, x1, x2, x3) = 2x0 + x2,
           
           [int#](x0, x1) = 4x0 + 0,
           
           [s](x0) = -2x0 + 0,
           
           [zero](x0) = 2x0,
           
           [0] = 2,
           
           [false] = 2,
           
           [true] = 4
          orientation:
           if1#(false(),x,y) = -16x + 6 >= 4 = int#(s(0()),y)
           
           int#(x,y) = 4x + 0 >= 4x = if_int#(zero(x),zero(y),x,y)
           
           if_int#(true(),b,x,y) = x + 6 >= -16x + 6 = if1#(b,x,y)
           
           zero(0()) = 4 >= 4 = true()
           
           zero(s(x)) = x + 2 >= 2 = false()
          problem:
           DPs:
            int#(x,y) -> if_int#(zero(x),zero(y),x,y)
            if_int#(true(),b,x,y) -> if1#(b,x,y)
           TRS:
            zero(0()) -> true()
            zero(s(x)) -> false()
          Restore Modifier:
           DPs:
            int#(x,y) -> if_int#(zero(x),zero(y),x,y)
            if_int#(true(),b,x,y) -> if1#(b,x,y)
           TRS:
            empty(nil()) -> true()
            empty(cons(x,y)) -> false()
            tail(nil()) -> nil()
            tail(cons(x,y)) -> y
            head(cons(x,y)) -> x
            zero(0()) -> true()
            zero(s(x)) -> false()
            p(0()) -> 0()
            p(s(0())) -> 0()
            p(s(s(x))) -> s(p(s(x)))
            intlist(x) -> if_intlist(empty(x),x)
            if_intlist(true(),x) -> nil()
            if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
            int(x,y) -> if_int(zero(x),zero(y),x,y)
            if_int(true(),b,x,y) -> if1(b,x,y)
            if_int(false(),b,x,y) -> if2(b,x,y)
            if1(true(),x,y) -> cons(0(),nil())
            if1(false(),x,y) -> cons(0(),int(s(0()),y))
            if2(true(),x,y) -> nil()
            if2(false(),x,y) -> intlist(int(p(x),p(y)))
           SCC Processor:
            #sccs: 0
            #rules: 0
            #arcs: 3/4
            
    
    DPs:
     intlist#(x) -> if_intlist#(empty(x),x)
     if_intlist#(false(),x) -> intlist#(tail(x))
    TRS:
     empty(nil()) -> true()
     empty(cons(x,y)) -> false()
     tail(nil()) -> nil()
     tail(cons(x,y)) -> y
     head(cons(x,y)) -> x
     zero(0()) -> true()
     zero(s(x)) -> false()
     p(0()) -> 0()
     p(s(0())) -> 0()
     p(s(s(x))) -> s(p(s(x)))
     intlist(x) -> if_intlist(empty(x),x)
     if_intlist(true(),x) -> nil()
     if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
     int(x,y) -> if_int(zero(x),zero(y),x,y)
     if_int(true(),b,x,y) -> if1(b,x,y)
     if_int(false(),b,x,y) -> if2(b,x,y)
     if1(true(),x,y) -> cons(0(),nil())
     if1(false(),x,y) -> cons(0(),int(s(0()),y))
     if2(true(),x,y) -> nil()
     if2(false(),x,y) -> intlist(int(p(x),p(y)))
    Usable Rule Processor:
     DPs:
      intlist#(x) -> if_intlist#(empty(x),x)
      if_intlist#(false(),x) -> intlist#(tail(x))
     TRS:
      empty(nil()) -> true()
      empty(cons(x,y)) -> false()
      tail(nil()) -> nil()
      tail(cons(x,y)) -> y
     Arctic Interpretation Processor:
      dimension: 1
      usable rules:
       empty(nil()) -> true()
       empty(cons(x,y)) -> false()
       tail(nil()) -> nil()
       tail(cons(x,y)) -> y
      interpretation:
       [if_intlist#](x0, x1) = x0 + -5x1 + 0,
       
       [intlist#](x0) = 3x0 + 1,
       
       [tail](x0) = -8x0 + 0,
       
       [false] = 3,
       
       [cons](x0, x1) = x0 + 11x1 + 11,
       
       [true] = 0,
       
       [empty](x0) = -7x0 + 0,
       
       [nil] = 0
      orientation:
       intlist#(x) = 3x + 1 >= -5x + 0 = if_intlist#(empty(x),x)
       
       if_intlist#(false(),x) = -5x + 3 >= -5x + 3 = intlist#(tail(x))
       
       empty(nil()) = 0 >= 0 = true()
       
       empty(cons(x,y)) = -7x + 4y + 4 >= 3 = false()
       
       tail(nil()) = 0 >= 0 = nil()
       
       tail(cons(x,y)) = -8x + 3y + 3 >= y = y
      problem:
       DPs:
        if_intlist#(false(),x) -> intlist#(tail(x))
       TRS:
        empty(nil()) -> true()
        empty(cons(x,y)) -> false()
        tail(nil()) -> nil()
        tail(cons(x,y)) -> y
      Restore Modifier:
       DPs:
        if_intlist#(false(),x) -> intlist#(tail(x))
       TRS:
        empty(nil()) -> true()
        empty(cons(x,y)) -> false()
        tail(nil()) -> nil()
        tail(cons(x,y)) -> y
        head(cons(x,y)) -> x
        zero(0()) -> true()
        zero(s(x)) -> false()
        p(0()) -> 0()
        p(s(0())) -> 0()
        p(s(s(x))) -> s(p(s(x)))
        intlist(x) -> if_intlist(empty(x),x)
        if_intlist(true(),x) -> nil()
        if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
        int(x,y) -> if_int(zero(x),zero(y),x,y)
        if_int(true(),b,x,y) -> if1(b,x,y)
        if_int(false(),b,x,y) -> if2(b,x,y)
        if1(true(),x,y) -> cons(0(),nil())
        if1(false(),x,y) -> cons(0(),int(s(0()),y))
        if2(true(),x,y) -> nil()
        if2(false(),x,y) -> intlist(int(p(x),p(y)))
       SCC Processor:
        #sccs: 0
        #rules: 0
        #arcs: 2/1
        
    
    DPs:
     p#(s(s(x))) -> p#(s(x))
    TRS:
     empty(nil()) -> true()
     empty(cons(x,y)) -> false()
     tail(nil()) -> nil()
     tail(cons(x,y)) -> y
     head(cons(x,y)) -> x
     zero(0()) -> true()
     zero(s(x)) -> false()
     p(0()) -> 0()
     p(s(0())) -> 0()
     p(s(s(x))) -> s(p(s(x)))
     intlist(x) -> if_intlist(empty(x),x)
     if_intlist(true(),x) -> nil()
     if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
     int(x,y) -> if_int(zero(x),zero(y),x,y)
     if_int(true(),b,x,y) -> if1(b,x,y)
     if_int(false(),b,x,y) -> if2(b,x,y)
     if1(true(),x,y) -> cons(0(),nil())
     if1(false(),x,y) -> cons(0(),int(s(0()),y))
     if2(true(),x,y) -> nil()
     if2(false(),x,y) -> intlist(int(p(x),p(y)))
    Subterm Criterion Processor:
     simple projection:
      pi(p#) = 0
     problem:
      DPs:
       
      TRS:
       empty(nil()) -> true()
       empty(cons(x,y)) -> false()
       tail(nil()) -> nil()
       tail(cons(x,y)) -> y
       head(cons(x,y)) -> x
       zero(0()) -> true()
       zero(s(x)) -> false()
       p(0()) -> 0()
       p(s(0())) -> 0()
       p(s(s(x))) -> s(p(s(x)))
       intlist(x) -> if_intlist(empty(x),x)
       if_intlist(true(),x) -> nil()
       if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
       int(x,y) -> if_int(zero(x),zero(y),x,y)
       if_int(true(),b,x,y) -> if1(b,x,y)
       if_int(false(),b,x,y) -> if2(b,x,y)
       if1(true(),x,y) -> cons(0(),nil())
       if1(false(),x,y) -> cons(0(),int(s(0()),y))
       if2(true(),x,y) -> nil()
       if2(false(),x,y) -> intlist(int(p(x),p(y)))
     Qed