/export/starexec/sandbox/solver/bin/starexec_run_ttt2 /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


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


YES

Problem:
 lt(0(),s(X)) -> true()
 lt(s(X),0()) -> false()
 lt(s(X),s(Y)) -> lt(X,Y)
 append(nil(),Y) -> Y
 append(add(N,X),Y) -> add(N,append(X,Y))
 split(N,nil()) -> pair(nil(),nil())
 split(N,add(M,Y)) -> f_1(split(N,Y),N,M,Y)
 f_1(pair(X,Z),N,M,Y) -> f_2(lt(N,M),N,M,Y,X,Z)
 f_2(true(),N,M,Y,X,Z) -> pair(X,add(M,Z))
 f_2(false(),N,M,Y,X,Z) -> pair(add(M,X),Z)
 qsort(nil()) -> nil()
 qsort(add(N,X)) -> f_3(split(N,X),N,X)
 f_3(pair(Y,Z),N,X) -> append(qsort(Y),add(X,qsort(Z)))

Proof:
 DP Processor:
  DPs:
   lt#(s(X),s(Y)) -> lt#(X,Y)
   append#(add(N,X),Y) -> append#(X,Y)
   split#(N,add(M,Y)) -> split#(N,Y)
   split#(N,add(M,Y)) -> f_1#(split(N,Y),N,M,Y)
   f_1#(pair(X,Z),N,M,Y) -> lt#(N,M)
   f_1#(pair(X,Z),N,M,Y) -> f_2#(lt(N,M),N,M,Y,X,Z)
   qsort#(add(N,X)) -> split#(N,X)
   qsort#(add(N,X)) -> f_3#(split(N,X),N,X)
   f_3#(pair(Y,Z),N,X) -> qsort#(Z)
   f_3#(pair(Y,Z),N,X) -> qsort#(Y)
   f_3#(pair(Y,Z),N,X) -> append#(qsort(Y),add(X,qsort(Z)))
  TRS:
   lt(0(),s(X)) -> true()
   lt(s(X),0()) -> false()
   lt(s(X),s(Y)) -> lt(X,Y)
   append(nil(),Y) -> Y
   append(add(N,X),Y) -> add(N,append(X,Y))
   split(N,nil()) -> pair(nil(),nil())
   split(N,add(M,Y)) -> f_1(split(N,Y),N,M,Y)
   f_1(pair(X,Z),N,M,Y) -> f_2(lt(N,M),N,M,Y,X,Z)
   f_2(true(),N,M,Y,X,Z) -> pair(X,add(M,Z))
   f_2(false(),N,M,Y,X,Z) -> pair(add(M,X),Z)
   qsort(nil()) -> nil()
   qsort(add(N,X)) -> f_3(split(N,X),N,X)
   f_3(pair(Y,Z),N,X) -> append(qsort(Y),add(X,qsort(Z)))
  TDG Processor:
   DPs:
    lt#(s(X),s(Y)) -> lt#(X,Y)
    append#(add(N,X),Y) -> append#(X,Y)
    split#(N,add(M,Y)) -> split#(N,Y)
    split#(N,add(M,Y)) -> f_1#(split(N,Y),N,M,Y)
    f_1#(pair(X,Z),N,M,Y) -> lt#(N,M)
    f_1#(pair(X,Z),N,M,Y) -> f_2#(lt(N,M),N,M,Y,X,Z)
    qsort#(add(N,X)) -> split#(N,X)
    qsort#(add(N,X)) -> f_3#(split(N,X),N,X)
    f_3#(pair(Y,Z),N,X) -> qsort#(Z)
    f_3#(pair(Y,Z),N,X) -> qsort#(Y)
    f_3#(pair(Y,Z),N,X) -> append#(qsort(Y),add(X,qsort(Z)))
   TRS:
    lt(0(),s(X)) -> true()
    lt(s(X),0()) -> false()
    lt(s(X),s(Y)) -> lt(X,Y)
    append(nil(),Y) -> Y
    append(add(N,X),Y) -> add(N,append(X,Y))
    split(N,nil()) -> pair(nil(),nil())
    split(N,add(M,Y)) -> f_1(split(N,Y),N,M,Y)
    f_1(pair(X,Z),N,M,Y) -> f_2(lt(N,M),N,M,Y,X,Z)
    f_2(true(),N,M,Y,X,Z) -> pair(X,add(M,Z))
    f_2(false(),N,M,Y,X,Z) -> pair(add(M,X),Z)
    qsort(nil()) -> nil()
    qsort(add(N,X)) -> f_3(split(N,X),N,X)
    f_3(pair(Y,Z),N,X) -> append(qsort(Y),add(X,qsort(Z)))
   graph:
    f_3#(pair(Y,Z),N,X) -> qsort#(Z) ->
    qsort#(add(N,X)) -> f_3#(split(N,X),N,X)
    f_3#(pair(Y,Z),N,X) -> qsort#(Z) ->
    qsort#(add(N,X)) -> split#(N,X)
    f_3#(pair(Y,Z),N,X) -> qsort#(Y) ->
    qsort#(add(N,X)) -> f_3#(split(N,X),N,X)
    f_3#(pair(Y,Z),N,X) -> qsort#(Y) ->
    qsort#(add(N,X)) -> split#(N,X)
    f_3#(pair(Y,Z),N,X) -> append#(qsort(Y),add(X,qsort(Z))) ->
    append#(add(N,X),Y) -> append#(X,Y)
    qsort#(add(N,X)) -> f_3#(split(N,X),N,X) ->
    f_3#(pair(Y,Z),N,X) -> append#(qsort(Y),add(X,qsort(Z)))
    qsort#(add(N,X)) -> f_3#(split(N,X),N,X) ->
    f_3#(pair(Y,Z),N,X) -> qsort#(Y)
    qsort#(add(N,X)) -> f_3#(split(N,X),N,X) ->
    f_3#(pair(Y,Z),N,X) -> qsort#(Z)
    qsort#(add(N,X)) -> split#(N,X) ->
    split#(N,add(M,Y)) -> f_1#(split(N,Y),N,M,Y)
    qsort#(add(N,X)) -> split#(N,X) ->
    split#(N,add(M,Y)) -> split#(N,Y)
    f_1#(pair(X,Z),N,M,Y) -> lt#(N,M) ->
    lt#(s(X),s(Y)) -> lt#(X,Y)
    split#(N,add(M,Y)) -> f_1#(split(N,Y),N,M,Y) ->
    f_1#(pair(X,Z),N,M,Y) -> f_2#(lt(N,M),N,M,Y,X,Z)
    split#(N,add(M,Y)) -> f_1#(split(N,Y),N,M,Y) ->
    f_1#(pair(X,Z),N,M,Y) -> lt#(N,M)
    split#(N,add(M,Y)) -> split#(N,Y) ->
    split#(N,add(M,Y)) -> f_1#(split(N,Y),N,M,Y)
    split#(N,add(M,Y)) -> split#(N,Y) ->
    split#(N,add(M,Y)) -> split#(N,Y)
    append#(add(N,X),Y) -> append#(X,Y) ->
    append#(add(N,X),Y) -> append#(X,Y)
    lt#(s(X),s(Y)) -> lt#(X,Y) -> lt#(s(X),s(Y)) -> lt#(X,Y)
   SCC Processor:
    #sccs: 4
    #rules: 6
    #arcs: 17/121
    DPs:
     f_3#(pair(Y,Z),N,X) -> qsort#(Z)
     qsort#(add(N,X)) -> f_3#(split(N,X),N,X)
     f_3#(pair(Y,Z),N,X) -> qsort#(Y)
    TRS:
     lt(0(),s(X)) -> true()
     lt(s(X),0()) -> false()
     lt(s(X),s(Y)) -> lt(X,Y)
     append(nil(),Y) -> Y
     append(add(N,X),Y) -> add(N,append(X,Y))
     split(N,nil()) -> pair(nil(),nil())
     split(N,add(M,Y)) -> f_1(split(N,Y),N,M,Y)
     f_1(pair(X,Z),N,M,Y) -> f_2(lt(N,M),N,M,Y,X,Z)
     f_2(true(),N,M,Y,X,Z) -> pair(X,add(M,Z))
     f_2(false(),N,M,Y,X,Z) -> pair(add(M,X),Z)
     qsort(nil()) -> nil()
     qsort(add(N,X)) -> f_3(split(N,X),N,X)
     f_3(pair(Y,Z),N,X) -> append(qsort(Y),add(X,qsort(Z)))
    Subterm Criterion Processor:
     simple projection:
      pi(add) = [0,0,1,1,1]
      pi(split) = [1,1]
      pi(pair) = [0,1]
      pi(f_1) = [0,0,0,2,2]
      pi(f_2) = [2,2,4,4,4,5,5,5]
      pi(qsort#) = [0,0]
      pi(f_3#) = [0,0,0]
     problem:
      DPs:
       
      TRS:
       lt(0(),s(X)) -> true()
       lt(s(X),0()) -> false()
       lt(s(X),s(Y)) -> lt(X,Y)
       append(nil(),Y) -> Y
       append(add(N,X),Y) -> add(N,append(X,Y))
       split(N,nil()) -> pair(nil(),nil())
       split(N,add(M,Y)) -> f_1(split(N,Y),N,M,Y)
       f_1(pair(X,Z),N,M,Y) -> f_2(lt(N,M),N,M,Y,X,Z)
       f_2(true(),N,M,Y,X,Z) -> pair(X,add(M,Z))
       f_2(false(),N,M,Y,X,Z) -> pair(add(M,X),Z)
       qsort(nil()) -> nil()
       qsort(add(N,X)) -> f_3(split(N,X),N,X)
       f_3(pair(Y,Z),N,X) -> append(qsort(Y),add(X,qsort(Z)))
     Qed
    
    DPs:
     append#(add(N,X),Y) -> append#(X,Y)
    TRS:
     lt(0(),s(X)) -> true()
     lt(s(X),0()) -> false()
     lt(s(X),s(Y)) -> lt(X,Y)
     append(nil(),Y) -> Y
     append(add(N,X),Y) -> add(N,append(X,Y))
     split(N,nil()) -> pair(nil(),nil())
     split(N,add(M,Y)) -> f_1(split(N,Y),N,M,Y)
     f_1(pair(X,Z),N,M,Y) -> f_2(lt(N,M),N,M,Y,X,Z)
     f_2(true(),N,M,Y,X,Z) -> pair(X,add(M,Z))
     f_2(false(),N,M,Y,X,Z) -> pair(add(M,X),Z)
     qsort(nil()) -> nil()
     qsort(add(N,X)) -> f_3(split(N,X),N,X)
     f_3(pair(Y,Z),N,X) -> append(qsort(Y),add(X,qsort(Z)))
    Subterm Criterion Processor:
     simple projection:
      pi(append#) = 0
     problem:
      DPs:
       
      TRS:
       lt(0(),s(X)) -> true()
       lt(s(X),0()) -> false()
       lt(s(X),s(Y)) -> lt(X,Y)
       append(nil(),Y) -> Y
       append(add(N,X),Y) -> add(N,append(X,Y))
       split(N,nil()) -> pair(nil(),nil())
       split(N,add(M,Y)) -> f_1(split(N,Y),N,M,Y)
       f_1(pair(X,Z),N,M,Y) -> f_2(lt(N,M),N,M,Y,X,Z)
       f_2(true(),N,M,Y,X,Z) -> pair(X,add(M,Z))
       f_2(false(),N,M,Y,X,Z) -> pair(add(M,X),Z)
       qsort(nil()) -> nil()
       qsort(add(N,X)) -> f_3(split(N,X),N,X)
       f_3(pair(Y,Z),N,X) -> append(qsort(Y),add(X,qsort(Z)))
     Qed
    
    DPs:
     split#(N,add(M,Y)) -> split#(N,Y)
    TRS:
     lt(0(),s(X)) -> true()
     lt(s(X),0()) -> false()
     lt(s(X),s(Y)) -> lt(X,Y)
     append(nil(),Y) -> Y
     append(add(N,X),Y) -> add(N,append(X,Y))
     split(N,nil()) -> pair(nil(),nil())
     split(N,add(M,Y)) -> f_1(split(N,Y),N,M,Y)
     f_1(pair(X,Z),N,M,Y) -> f_2(lt(N,M),N,M,Y,X,Z)
     f_2(true(),N,M,Y,X,Z) -> pair(X,add(M,Z))
     f_2(false(),N,M,Y,X,Z) -> pair(add(M,X),Z)
     qsort(nil()) -> nil()
     qsort(add(N,X)) -> f_3(split(N,X),N,X)
     f_3(pair(Y,Z),N,X) -> append(qsort(Y),add(X,qsort(Z)))
    Subterm Criterion Processor:
     simple projection:
      pi(split#) = 1
     problem:
      DPs:
       
      TRS:
       lt(0(),s(X)) -> true()
       lt(s(X),0()) -> false()
       lt(s(X),s(Y)) -> lt(X,Y)
       append(nil(),Y) -> Y
       append(add(N,X),Y) -> add(N,append(X,Y))
       split(N,nil()) -> pair(nil(),nil())
       split(N,add(M,Y)) -> f_1(split(N,Y),N,M,Y)
       f_1(pair(X,Z),N,M,Y) -> f_2(lt(N,M),N,M,Y,X,Z)
       f_2(true(),N,M,Y,X,Z) -> pair(X,add(M,Z))
       f_2(false(),N,M,Y,X,Z) -> pair(add(M,X),Z)
       qsort(nil()) -> nil()
       qsort(add(N,X)) -> f_3(split(N,X),N,X)
       f_3(pair(Y,Z),N,X) -> append(qsort(Y),add(X,qsort(Z)))
     Qed
    
    DPs:
     lt#(s(X),s(Y)) -> lt#(X,Y)
    TRS:
     lt(0(),s(X)) -> true()
     lt(s(X),0()) -> false()
     lt(s(X),s(Y)) -> lt(X,Y)
     append(nil(),Y) -> Y
     append(add(N,X),Y) -> add(N,append(X,Y))
     split(N,nil()) -> pair(nil(),nil())
     split(N,add(M,Y)) -> f_1(split(N,Y),N,M,Y)
     f_1(pair(X,Z),N,M,Y) -> f_2(lt(N,M),N,M,Y,X,Z)
     f_2(true(),N,M,Y,X,Z) -> pair(X,add(M,Z))
     f_2(false(),N,M,Y,X,Z) -> pair(add(M,X),Z)
     qsort(nil()) -> nil()
     qsort(add(N,X)) -> f_3(split(N,X),N,X)
     f_3(pair(Y,Z),N,X) -> append(qsort(Y),add(X,qsort(Z)))
    Subterm Criterion Processor:
     simple projection:
      pi(lt#) = 0
     problem:
      DPs:
       
      TRS:
       lt(0(),s(X)) -> true()
       lt(s(X),0()) -> false()
       lt(s(X),s(Y)) -> lt(X,Y)
       append(nil(),Y) -> Y
       append(add(N,X),Y) -> add(N,append(X,Y))
       split(N,nil()) -> pair(nil(),nil())
       split(N,add(M,Y)) -> f_1(split(N,Y),N,M,Y)
       f_1(pair(X,Z),N,M,Y) -> f_2(lt(N,M),N,M,Y,X,Z)
       f_2(true(),N,M,Y,X,Z) -> pair(X,add(M,Z))
       f_2(false(),N,M,Y,X,Z) -> pair(add(M,X),Z)
       qsort(nil()) -> nil()
       qsort(add(N,X)) -> f_3(split(N,X),N,X)
       f_3(pair(Y,Z),N,X) -> append(qsort(Y),add(X,qsort(Z)))
     Qed