/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


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


YES

We split firstr-order part and higher-order part, and do modular checking by a general modularity.

******** FO SN check ********
Check SN using NaTT (Nagoya Termination Tool)
Input TRS:
    1: append(W,nil()) -> W
    2: append(nil(),P) -> P
    3: append(cons(X1,Y1),U1) -> cons(X1,append(Y1,U1))
    4: zip(nil(),V1) -> V1
    5: zip(W1,nil()) -> W1
    6: zip(cons(P1,X2),cons(Y2,U2)) -> cons(append(P1,Y2),zip(X2,U2))
    7: combine(V2,nil()) -> V2
    8: combine(W2,cons(P2,X3)) -> combine(zip(W2,P2),X3)
    9: _(X1,X2) -> X1
    10: _(X1,X2) -> X2
Number of strict rules: 10
Direct POLO(bPol) ... removes: 4 8 1 5 10 7 9 6 2
      _ 	w: 2 * x1 + x2 + 1
      append	w: x1 + x2 + 3226
      combine	w: x1 + 2 * x2 + 1889
      nil	w: 0
      cons	w: 2 * x1 + x2 + 6414
      zip	w: x1 + 2 * x2 + 12826
Number of strict rules: 1
Direct POLO(bPol) ... removes: 3
      _ 	w: 2 * x1 + x2 + 1
      append	w: 2 * x1 + 2 * x2 + 9969
      combine	w: x1 + 2 * x2 + 6058
      nil	w: 0
      cons	w: x1 + x2 + 2791
      zip	w: x1 + 2 * x2 + 4418
Number of strict rules: 0

...
Input TRS:
    1: append(W,nil()) -> W
    2: append(nil(),P) -> P
    3: append(cons(X1,Y1),U1) -> cons(X1,append(Y1,U1))
    4: zip(nil(),V1) -> V1
    5: zip(W1,nil()) -> W1
    6: zip(cons(P1,X2),cons(Y2,U2)) -> cons(append(P1,Y2),zip(X2,U2))
    7: combine(V2,nil()) -> V2
    8: combine(W2,cons(P2,X3)) -> combine(zip(W2,P2),X3)
    9: _(X1,X2) -> X1
    10: _(X1,X2) -> X2
Number of strict rules: 10
Direct POLO(bPol) ... removes: 4 8 1 5 10 7 9 6 2
      _ 	w: 2 * x1 + x2 + 1
      append	w: x1 + x2 + 3226
      combine	w: x1 + 2 * x2 + 1889
      nil	w: 0
      cons	w: 2 * x1 + x2 + 6414
      zip	w: x1 + 2 * x2 + 12826
Number of strict rules: 1
Direct POLO(bPol) ... removes: 3
      _ 	w: 2 * x1 + x2 + 1
      append	w: 2 * x1 + 2 * x2 + 9969
      combine	w: x1 + 2 * x2 + 6058
      nil	w: 0
      cons	w: x1 + x2 + 2791
      zip	w: x1 + 2 * x2 + 4418
Number of strict rules: 0
>>YES

******** Signature ********
 map : ((a -> a),a) -> a
 nil : a
 cons : (a,a) -> a
 levels : a -> a
 node : (a,a) -> a
 combine : (a,a) -> a
******** Computation rules ********
 (1)  map(F,nil) => nil
 (2)  map(Z,cons(U,V)) => cons(Z[U],map(Z,V))
 (11)  levels(node(Y3,U3)) => cons(cons(Y3,nil),combine(nil,map(levels,U3)))


******** General Schema criterion ********
Found constructors: cons, nil, node
Checking type order >>OK
Checking positivity of constructors >>OK
Checking function dependency >>OK
Checking  (1) map(F,nil) => nil
 (fun map>nil) >>True
Checking  (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V))
 (fun map>cons)
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta U)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in U] 
 (fun map=map) subterm comparison of args w. LR LR
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta V)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in V]  >>True
Checking  (3) append(W,nil) => W
 (meta W)[is acc in W,nil] [is acc in W]  >>True
Checking  (4) append(nil,P) => P
 (meta P)[is acc in nil,P] [is positive in nil] [is acc in P]  >>True
Checking  (5) append(cons(X1,Y1),U1) => cons(X1,append(Y1,U1))
 (fun append>cons)
 (meta X1)[is acc in cons(X1,Y1),U1] [is positive in cons(X1,Y1)] [is acc in X1] 
 (fun append=append) subterm comparison of args w. LR LR
 (meta Y1)[is acc in cons(X1,Y1),U1] [is positive in cons(X1,Y1)] [is acc in Y1] 
 (meta U1)[is acc in cons(X1,Y1),U1] [is positive in cons(X1,Y1)] [is acc in U1]  >>True
Checking  (6) zip(nil,V1) => V1
 (meta V1)[is acc in nil,V1] [is positive in nil] [is acc in V1]  >>True
Checking  (7) zip(W1,nil) => W1
 (meta W1)[is acc in W1,nil] [is acc in W1]  >>True
Checking  (8) zip(cons(P1,X2),cons(Y2,U2)) => cons(append(P1,Y2),zip(X2,U2))
 (fun zip>cons)
 (fun zip>append)
 (meta P1)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is acc in P1] 
 (meta Y2)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is positive in cons(Y2,U2)] [is acc in Y2] 
 (fun zip=zip) subterm comparison of args w. LR LR
 (meta X2)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is acc in X2] 
 (meta U2)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is positive in cons(Y2,U2)] [is acc in U2]  >>True
Checking  (9) combine(V2,nil) => V2
 (meta V2)[is acc in V2,nil] [is acc in V2]  >>True
Checking  (10) combine(W2,cons(P2,X3)) => combine(zip(W2,P2),X3)
 (fun combine=combine) subterm comparison of args w. LR LR >>False

Try again using status RL
Checking  (1) map(F,nil) => nil
 (fun map>nil) >>True
Checking  (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V))
 (fun map>cons)
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta U)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in U] 
 (fun map=map) subterm comparison of args w. RL RL
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta V)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in V]  >>True
Checking  (3) append(W,nil) => W
 (meta W)[is acc in W,nil] [is acc in W]  >>True
Checking  (4) append(nil,P) => P
 (meta P)[is acc in nil,P] [is positive in nil] [is acc in P]  >>True
Checking  (5) append(cons(X1,Y1),U1) => cons(X1,append(Y1,U1))
 (fun append>cons)
 (meta X1)[is acc in cons(X1,Y1),U1] [is positive in cons(X1,Y1)] [is acc in X1] 
 (fun append=append) subterm comparison of args w. RL RL
 (meta Y1)[is acc in cons(X1,Y1),U1] [is positive in cons(X1,Y1)] [is acc in Y1] 
 (meta U1)[is acc in cons(X1,Y1),U1] [is positive in cons(X1,Y1)] [is acc in U1]  >>True
Checking  (6) zip(nil,V1) => V1
 (meta V1)[is acc in nil,V1] [is positive in nil] [is acc in V1]  >>True
Checking  (7) zip(W1,nil) => W1
 (meta W1)[is acc in W1,nil] [is acc in W1]  >>True
Checking  (8) zip(cons(P1,X2),cons(Y2,U2)) => cons(append(P1,Y2),zip(X2,U2))
 (fun zip>cons)
 (fun zip>append)
 (meta P1)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is acc in P1] 
 (meta Y2)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is positive in cons(Y2,U2)] [is acc in Y2] 
 (fun zip=zip) subterm comparison of args w. RL RL
 (meta X2)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is acc in X2] 
 (meta U2)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is positive in cons(Y2,U2)] [is acc in U2]  >>True
Checking  (9) combine(V2,nil) => V2
 (meta V2)[is acc in V2,nil] [is acc in V2]  >>True
Checking  (10) combine(W2,cons(P2,X3)) => combine(zip(W2,P2),X3)
 (fun combine=combine) subterm comparison of args w. RL RL
 (fun combine>zip)
 (meta W2)[is acc in W2,cons(P2,X3)] [is acc in W2] 
 (meta P2)[is acc in W2,cons(P2,X3)] [is positive in cons(P2,X3)] [is acc in P2] 
 (meta X3)[is acc in W2,cons(P2,X3)] [is positive in cons(P2,X3)] [is acc in X3]  >>True
Checking  (11) levels(node(Y3,U3)) => cons(cons(Y3,nil),combine(nil,map(levels,U3)))
 (fun levels>cons)
 (fun levels>cons)
 (meta Y3)[is acc in node(Y3,U3)] [is positive in node(Y3,U3)] [is acc in Y3] 
 (fun levels>nil)
 (fun levels>combine)
 (fun levels>nil)
 (fun levels>map)
 (fun levels=levels) subterm comparison of args w. RL RL >>False

Try again using status Mul
Checking  (1) map(F,nil) => nil
 (fun map>nil) >>True
Checking  (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V))
 (fun map>cons)
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta U)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in U] 
 (fun map=map) subterm comparison of args w. Mul Mul
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta V)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in V]  >>True
Checking  (3) append(W,nil) => W
 (meta W)[is acc in W,nil] [is acc in W]  >>True
Checking  (4) append(nil,P) => P
 (meta P)[is acc in nil,P] [is positive in nil] [is acc in P]  >>True
Checking  (5) append(cons(X1,Y1),U1) => cons(X1,append(Y1,U1))
 (fun append>cons)
 (meta X1)[is acc in cons(X1,Y1),U1] [is positive in cons(X1,Y1)] [is acc in X1] 
 (fun append=append) subterm comparison of args w. Mul Mul
 (meta Y1)[is acc in cons(X1,Y1),U1] [is positive in cons(X1,Y1)] [is acc in Y1] 
 (meta U1)[is acc in cons(X1,Y1),U1] [is positive in cons(X1,Y1)] [is acc in U1]  >>True
Checking  (6) zip(nil,V1) => V1
 (meta V1)[is acc in nil,V1] [is positive in nil] [is acc in V1]  >>True
Checking  (7) zip(W1,nil) => W1
 (meta W1)[is acc in W1,nil] [is acc in W1]  >>True
Checking  (8) zip(cons(P1,X2),cons(Y2,U2)) => cons(append(P1,Y2),zip(X2,U2))
 (fun zip>cons)
 (fun zip>append)
 (meta P1)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is acc in P1] 
 (meta Y2)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is positive in cons(Y2,U2)] [is acc in Y2] 
 (fun zip=zip) subterm comparison of args w. Mul Mul
 (meta X2)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is acc in X2] 
 (meta U2)[is acc in cons(P1,X2),cons(Y2,U2)] [is positive in cons(P1,X2)] [is positive in cons(Y2,U2)] [is acc in U2]  >>True
Checking  (9) combine(V2,nil) => V2
 (meta V2)[is acc in V2,nil] [is acc in V2]  >>True
Checking  (10) combine(W2,cons(P2,X3)) => combine(zip(W2,P2),X3)
 (fun combine=combine) subterm comparison of args w. Mul Mul >>False
Found constructors: nil, cons, node, combine
Checking type order >>OK
Checking positivity of constructors >>OK
Checking function dependency >>OK
Checking  (1) map(F,nil) => nil
 (fun map>nil) >>True
Checking  (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V))
 (fun map>cons)
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta U)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in U] 
 (fun map=map) subterm comparison of args w. LR LR
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta V)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in V]  >>True
Checking  (11) levels(node(Y3,U3)) => cons(cons(Y3,nil),combine(nil,map(levels,U3)))
 (fun levels>cons)
 (fun levels>cons)
 (meta Y3)[is acc in node(Y3,U3)] [is positive in node(Y3,U3)] [is acc in Y3] 
 (fun levels>nil)
 (fun levels>combine)
 (fun levels>nil)
 (fun levels>map)
 (fun levels=levels) subterm comparison of args w. LR LR >>False

Try again using status RL
Checking  (1) map(F,nil) => nil
 (fun map>nil) >>True
Checking  (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V))
 (fun map>cons)
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta U)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in U] 
 (fun map=map) subterm comparison of args w. RL RL
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta V)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in V]  >>True
Checking  (11) levels(node(Y3,U3)) => cons(cons(Y3,nil),combine(nil,map(levels,U3)))
 (fun levels>cons)
 (fun levels>cons)
 (meta Y3)[is acc in node(Y3,U3)] [is positive in node(Y3,U3)] [is acc in Y3] 
 (fun levels>nil)
 (fun levels>combine)
 (fun levels>nil)
 (fun levels>map)
 (fun levels=levels) subterm comparison of args w. RL RL >>False

Try again using status Mul
Checking  (1) map(F,nil) => nil
 (fun map>nil) >>True
Checking  (2) map(Z,cons(U,V)) => cons(Z[U],map(Z,V))
 (fun map>cons)
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta U)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in U] 
 (fun map=map) subterm comparison of args w. Mul Mul
 (meta Z)[is acc in Z,cons(U,V)] [is acc in Z] 
 (meta V)[is acc in Z,cons(U,V)] [is positive in cons(U,V)] [is acc in V]  >>True
Checking  (11) levels(node(Y3,U3)) => cons(cons(Y3,nil),combine(nil,map(levels,U3)))
 (fun levels>cons)
 (fun levels>cons)
 (meta Y3)[is acc in node(Y3,U3)] [is positive in node(Y3,U3)] [is acc in Y3] 
 (fun levels>nil)
 (fun levels>combine)
 (fun levels>nil)
 (fun levels>map)
 (fun levels=levels) subterm comparison of args w. Mul Mul
 (meta U3)[is acc in node(Y3,U3)] [is positive in node(Y3,U3)] [is acc in U3]  >>True
#SN!
******** Signature ********
 append : (a,a) -> a
 combine : (a,a) -> a
 cons : (a,a) -> a
 levels : a -> a
 map : ((a -> a),a) -> a
 nil : a
 node : (a,a) -> a
 zip : (a,a) -> a
******** Computation Rules ********
 (1)  map(F,nil) => nil
 (2)  map(Z,cons(U,V)) => cons(Z[U],map(Z,V))
 (3)  append(W,nil) => W
 (4)  append(nil,P) => P
 (5)  append(cons(X1,Y1),U1) => cons(X1,append(Y1,U1))
 (6)  zip(nil,V1) => V1
 (7)  zip(W1,nil) => W1
 (8)  zip(cons(P1,X2),cons(Y2,U2)) => cons(append(P1,Y2),zip(X2,U2))
 (9)  combine(V2,nil) => V2
 (10)  combine(W2,cons(P2,X3)) => combine(zip(W2,P2),X3)
 (11)  levels(node(Y3,U3)) => cons(cons(Y3,nil),combine(nil,map(levels,U3)))

YES