/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/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: app(nil(),X) -> X
    2: app(cons(Y,U),V) -> cons(Y,app(U,V))
    3: reverse(nil()) -> nil()
    4: reverse(cons(W,P)) -> app(reverse(P),cons(W,nil()))
    5: shuffle(nil()) -> nil()
    6: shuffle(cons(X1,Y1)) -> cons(X1,shuffle(reverse(Y1)))
    7: _(X1,X2) -> X1
    8: _(X1,X2) -> X2
Number of strict rules: 8
Direct POLO(bPol) ... removes: 8 5 7
      reverse	w: x1
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: x1 + 6284
      nil	w: 0
      cons	w: 2 * x1 + x2 + 1889
      app	w: x1 + x2
Number of strict rules: 5
Direct POLO(bPol) ... removes: 6
      reverse	w: x1
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: 2 * x1 + 2276
      nil	w: 0
      cons	w: 2 * x1 + x2 + 8587
      app	w: x1 + x2
Number of strict rules: 4
Direct POLO(bPol) ... removes: 3
      reverse	w: x1 + 1595
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: x1 + 2276
      nil	w: 0
      cons	w: 2 * x1 + x2 + 7579
      app	w: x1 + x2
Number of strict rules: 3
Direct POLO(bPol) ... removes: 4 1
      reverse	w: 2 * x1 + 3541
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: 2 * x1 + 328
      nil	w: 1920
      cons	w: 2 * x1 + x2 + 3895
      app	w: x1 + x2 + 1974
Number of strict rules: 1
Direct POLO(bPol) ... removes: 2
      reverse	w: 2 * x1 + 3541
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: 2 * x1 + 328
      nil	w: 1920
      cons	w: 2 * x1 + x2 + 7081
      app	w: 2 * x1 + x2 + 1620
Number of strict rules: 0

...
Input TRS:
    1: app(nil(),X) -> X
    2: app(cons(Y,U),V) -> cons(Y,app(U,V))
    3: reverse(nil()) -> nil()
    4: reverse(cons(W,P)) -> app(reverse(P),cons(W,nil()))
    5: shuffle(nil()) -> nil()
    6: shuffle(cons(X1,Y1)) -> cons(X1,shuffle(reverse(Y1)))
    7: _(X1,X2) -> X1
    8: _(X1,X2) -> X2
Number of strict rules: 8
Direct POLO(bPol) ... removes: 8 5 7
      reverse	w: x1
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: x1 + 6284
      nil	w: 0
      cons	w: 2 * x1 + x2 + 1889
      app	w: x1 + x2
Number of strict rules: 5
Direct POLO(bPol) ... removes: 6
      reverse	w: x1
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: 2 * x1 + 2276
      nil	w: 0
      cons	w: 2 * x1 + x2 + 8587
      app	w: x1 + x2
Number of strict rules: 4
Direct POLO(bPol) ... removes: 3
      reverse	w: x1 + 1595
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: x1 + 2276
      nil	w: 0
      cons	w: 2 * x1 + x2 + 7579
      app	w: x1 + x2
Number of strict rules: 3
Direct POLO(bPol) ... removes: 4 1
      reverse	w: 2 * x1 + 3541
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: 2 * x1 + 328
      nil	w: 1920
      cons	w: 2 * x1 + x2 + 3895
      app	w: x1 + x2 + 1974
Number of strict rules: 1
Direct POLO(bPol) ... removes: 2
      reverse	w: 2 * x1 + 3541
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: 2 * x1 + 328
      nil	w: 1920
      cons	w: 2 * x1 + x2 + 7081
      app	w: 2 * x1 + x2 + 1620
Number of strict rules: 0
>>YES

******** Signature ********
 map : ((nat -> nat),list) -> list
 nil : list
 cons : (nat,list) -> list
******** Computation rules ********
 (7)  map(G1,nil) => nil
 (8)  map(H1,cons(W1,P1)) => cons(H1[W1],map(H1,P1))


******** General Schema criterion ********
Found constructors: cons, nil
Checking type order >>OK
Checking positivity of constructors >>OK
Checking function dependency >>OK
Checking  (1) nil@X => X
 (meta X)[is acc in nil,X] [is positive in nil] [is acc in X]  >>True
Checking  (2) cons(Y,U)@V => cons(Y,U@V)
 (fun app>cons)
 (meta Y)[is acc in cons(Y,U),V] [is positive in cons(Y,U)] [is acc in Y] 
 (fun app=app) subterm comparison of args w. LR LR
 (meta U)[is acc in cons(Y,U),V] [is positive in cons(Y,U)] [is acc in U] 
 (meta V)[is acc in cons(Y,U),V] [is positive in cons(Y,U)] [is acc in V]  >>True
Checking  (3) reverse(nil) => nil
 (fun reverse>nil) >>True
Checking  (4) reverse(cons(W,P)) => reverse(P)@cons(W,nil)
 (fun reverse>app)
 (fun reverse=reverse) subterm comparison of args w. LR LR
 (meta P)[is acc in cons(W,P)] [is positive in cons(W,P)] [is acc in P] 
 (fun reverse>cons)
 (meta W)[is acc in cons(W,P)] [is positive in cons(W,P)] [is acc in W] 
 (fun reverse>nil) >>True
Checking  (5) shuffle(nil) => nil
 (fun shuffle>nil) >>True
Checking  (6) shuffle(cons(X1,Y1)) => cons(X1,shuffle(reverse(Y1)))
 (fun shuffle>cons)
 (meta X1)[is acc in cons(X1,Y1)] [is positive in cons(X1,Y1)] [is acc in X1] 
 (fun shuffle=shuffle) subterm comparison of args w. LR LR >>False

Try again using status RL
Checking  (1) nil@X => X
 (meta X)[is acc in nil,X] [is positive in nil] [is acc in X]  >>True
Checking  (2) cons(Y,U)@V => cons(Y,U@V)
 (fun app>cons)
 (meta Y)[is acc in cons(Y,U),V] [is positive in cons(Y,U)] [is acc in Y] 
 (fun app=app) subterm comparison of args w. RL RL
 (meta U)[is acc in cons(Y,U),V] [is positive in cons(Y,U)] [is acc in U] 
 (meta V)[is acc in cons(Y,U),V] [is positive in cons(Y,U)] [is acc in V]  >>True
Checking  (3) reverse(nil) => nil
 (fun reverse>nil) >>True
Checking  (4) reverse(cons(W,P)) => reverse(P)@cons(W,nil)
 (fun reverse>app)
 (fun reverse=reverse) subterm comparison of args w. RL RL
 (meta P)[is acc in cons(W,P)] [is positive in cons(W,P)] [is acc in P] 
 (fun reverse>cons)
 (meta W)[is acc in cons(W,P)] [is positive in cons(W,P)] [is acc in W] 
 (fun reverse>nil) >>True
Checking  (5) shuffle(nil) => nil
 (fun shuffle>nil) >>True
Checking  (6) shuffle(cons(X1,Y1)) => cons(X1,shuffle(reverse(Y1)))
 (fun shuffle>cons)
 (meta X1)[is acc in cons(X1,Y1)] [is positive in cons(X1,Y1)] [is acc in X1] 
 (fun shuffle=shuffle) subterm comparison of args w. RL RL >>False

Try again using status Mul
Checking  (1) nil@X => X
 (meta X)[is acc in nil,X] [is positive in nil] [is acc in X]  >>True
Checking  (2) cons(Y,U)@V => cons(Y,U@V)
 (fun app>cons)
 (meta Y)[is acc in cons(Y,U),V] [is positive in cons(Y,U)] [is acc in Y] 
 (fun app=app) subterm comparison of args w. Mul Mul
 (meta U)[is acc in cons(Y,U),V] [is positive in cons(Y,U)] [is acc in U] 
 (meta V)[is acc in cons(Y,U),V] [is positive in cons(Y,U)] [is acc in V]  >>True
Checking  (3) reverse(nil) => nil
 (fun reverse>nil) >>True
Checking  (4) reverse(cons(W,P)) => reverse(P)@cons(W,nil)
 (fun reverse>app)
 (fun reverse=reverse) subterm comparison of args w. Mul Mul
 (meta P)[is acc in cons(W,P)] [is positive in cons(W,P)] [is acc in P] 
 (fun reverse>cons)
 (meta W)[is acc in cons(W,P)] [is positive in cons(W,P)] [is acc in W] 
 (fun reverse>nil) >>True
Checking  (5) shuffle(nil) => nil
 (fun shuffle>nil) >>True
Checking  (6) shuffle(cons(X1,Y1)) => cons(X1,shuffle(reverse(Y1)))
 (fun shuffle>cons)
 (meta X1)[is acc in cons(X1,Y1)] [is positive in cons(X1,Y1)] [is acc in X1] 
 (fun shuffle=shuffle) subterm comparison of args w. Mul Mul >>False
Found constructors: nil, cons
Checking type order >>OK
Checking positivity of constructors >>OK
Checking function dependency >>OK
Checking  (7) map(G1,nil) => nil
 (fun map>nil) >>True
Checking  (8) map(H1,cons(W1,P1)) => cons(H1[W1],map(H1,P1))
 (fun map>cons)
 (meta H1)[is acc in H1,cons(W1,P1)] [is acc in H1] 
 (meta W1)[is acc in H1,cons(W1,P1)] [is positive in cons(W1,P1)] [is acc in W1] 
 (fun map=map) subterm comparison of args w. LR LR
 (meta H1)[is acc in H1,cons(W1,P1)] [is acc in H1] 
 (meta P1)[is acc in H1,cons(W1,P1)] [is positive in cons(W1,P1)] [is acc in P1]  >>True
#SN!
******** Signature ********
 app : (list,list) -> list
 cons : (nat,list) -> list
 map : ((nat -> nat),list) -> list
 nil : list
 reverse : list -> list
 shuffle : list -> list
******** Computation Rules ********
 (1)  nil@X => X
 (2)  cons(Y,U)@V => cons(Y,U@V)
 (3)  reverse(nil) => nil
 (4)  reverse(cons(W,P)) => reverse(P)@cons(W,nil)
 (5)  shuffle(nil) => nil
 (6)  shuffle(cons(X1,Y1)) => cons(X1,shuffle(reverse(Y1)))
 (7)  map(G1,nil) => nil
 (8)  map(H1,cons(W1,P1)) => cons(H1[W1],map(H1,P1))

YES