/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(nil(),U) -> U
    2: append(cons(X,Y),U) -> cons(X,append(Y,U))
    3: reverse(nil()) -> nil()
    4: shuffle(nil()) -> nil()
    5: shuffle(cons(X,Y)) -> cons(X,shuffle(reverse(Y)))
    6: mirror(nil()) -> nil()
    7: mirror(cons(X,Y)) -> append(cons(X,mirror(Y)),cons(X,nil()))
    8: _(X1,X2) -> X1
    9: _(X1,X2) -> X2
Number of strict rules: 9
Direct POLO(bPol) ... removes: 4 8 9 6
      mirror	w: 2 * x1 + 975
      reverse	w: x1
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: x1 + 1143
      append	w: x1 + x2
      nil	w: 0
      cons	w: 2 * x1 + x2
Number of strict rules: 5
Direct POLO(bPol) ... removes: 3 5
      mirror	w: 2 * x1 + 9726
      reverse	w: x1 + 841
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: 2 * x1 + 1143
      append	w: x1 + x2
      nil	w: 0
      cons	w: 2 * x1 + x2 + 1683
Number of strict rules: 3
Direct POLO(bPol) ... failed.
Uncurrying append
1: append^1_nil(U) -> U
2: append^1_cons(X,Y,U) -> cons(X,append(Y,U))
7: mirror(cons(X,Y)) -> append^1_cons(X,mirror(Y),cons(X,nil()))
10: append(cons(_1,_2),_3) ->= append^1_cons(_1,_2,_3)
11: append(nil(),_1) ->= append^1_nil(_1)
Number of strict rules: 3
Direct POLO(bPol) ... failed.
Dependency Pairs:
   #1: #append^1_cons(X,Y,U) -> #append(Y,U)
   #2: #append(nil(),_1) ->? #append^1_nil(_1)
   #3: #mirror(cons(X,Y)) -> #append^1_cons(X,mirror(Y),cons(X,nil()))
   #4: #mirror(cons(X,Y)) -> #mirror(Y)
   #5: #append(cons(_1,_2),_3) ->? #append^1_cons(_1,_2,_3)
Number of SCCs: 2, DPs: 3
  SCC { #4 }
POLO(Sum)... succeeded.
      mirror	w: 0
      append^1_cons	w: 0
      #append	w: 0
      #mirror	w: x1
      #append^1_cons	w: 0
      #append^1_nil	w: 0
      reverse	w: 0
      _ 	w: 0
      shuffle	w: 0
      append	w: 0
      nil	w: 0
      cons	w: x2 + 1
      append^1_nil	w: 0
    USABLE RULES: { }
    Removed DPs: #4
Number of SCCs: 1, DPs: 2
  SCC { #1 #5 }
POLO(Sum)... succeeded.
      mirror	w: 0
      append^1_cons	w: 0
      #append	w: x1
      #mirror	w: 0
      #append^1_cons	w: x2 + 1
      #append^1_nil	w: 0
      reverse	w: 0
      _ 	w: 0
      shuffle	w: 0
      append	w: 0
      nil	w: 0
      cons	w: x1 + x2 + 2
      append^1_nil	w: 0
    USABLE RULES: { }
    Removed DPs: #1 #5
Number of SCCs: 0, DPs: 0

...
Input TRS:
    1: append(nil(),U) -> U
    2: append(cons(X,Y),U) -> cons(X,append(Y,U))
    3: reverse(nil()) -> nil()
    4: shuffle(nil()) -> nil()
    5: shuffle(cons(X,Y)) -> cons(X,shuffle(reverse(Y)))
    6: mirror(nil()) -> nil()
    7: mirror(cons(X,Y)) -> append(cons(X,mirror(Y)),cons(X,nil()))
    8: _(X1,X2) -> X1
    9: _(X1,X2) -> X2
Number of strict rules: 9
Direct POLO(bPol) ... removes: 4 8 9 6
      mirror	w: 2 * x1 + 975
      reverse	w: x1
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: x1 + 1143
      append	w: x1 + x2
      nil	w: 0
      cons	w: 2 * x1 + x2
Number of strict rules: 5
Direct POLO(bPol) ... removes: 3 5
      mirror	w: 2 * x1 + 9726
      reverse	w: x1 + 841
      _ 	w: x1 + 2 * x2 + 1
      shuffle	w: 2 * x1 + 1143
      append	w: x1 + x2
      nil	w: 0
      cons	w: 2 * x1 + x2 + 1683
Number of strict rules: 3
Direct POLO(bPol) ... failed.
Uncurrying append
1: append^1_nil(U) -> U
2: append^1_cons(X,Y,U) -> cons(X,append(Y,U))
7: mirror(cons(X,Y)) -> append^1_cons(X,mirror(Y),cons(X,nil()))
10: append(cons(_1,_2),_3) ->= append^1_cons(_1,_2,_3)
11: append(nil(),_1) ->= append^1_nil(_1)
Number of strict rules: 3
Direct POLO(bPol) ... failed.
Dependency Pairs:
   #1: #append^1_cons(X,Y,U) -> #append(Y,U)
   #2: #append(nil(),_1) ->? #append^1_nil(_1)
   #3: #mirror(cons(X,Y)) -> #append^1_cons(X,mirror(Y),cons(X,nil()))
   #4: #mirror(cons(X,Y)) -> #mirror(Y)
   #5: #append(cons(_1,_2),_3) ->? #append^1_cons(_1,_2,_3)
Number of SCCs: 2, DPs: 3
  SCC { #4 }
POLO(Sum)... succeeded.
      mirror	w: 0
      append^1_cons	w: 0
      #append	w: 0
      #mirror	w: x1
      #append^1_cons	w: 0
      #append^1_nil	w: 0
      reverse	w: 0
      _ 	w: 0
      shuffle	w: 0
      append	w: 0
      nil	w: 0
      cons	w: x2 + 1
      append^1_nil	w: 0
    USABLE RULES: { }
    Removed DPs: #4
Number of SCCs: 1, DPs: 2
  SCC { #1 #5 }
POLO(Sum)... succeeded.
      mirror	w: 0
      append^1_cons	w: 0
      #append	w: x1
      #mirror	w: 0
      #append^1_cons	w: x2 + 1
      #append^1_nil	w: 0
      reverse	w: 0
      _ 	w: 0
      shuffle	w: 0
      append	w: 0
      nil	w: 0
      cons	w: x1 + x2 + 2
      append^1_nil	w: 0
    USABLE RULES: { }
    Removed DPs: #1 #5
Number of SCCs: 0, DPs: 0
>>YES

******** Signature ********
 map : ((nat -> nat),list) -> list
 nil : list
 cons : (nat,list) -> list
******** Computation rules ********
 (8)  map(H,nil) => nil
 (9)  map(H,cons(X,Y)) => cons(H[X],map(H,Y))


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

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

Try again using status Mul
Checking  (1) append(nil,U) => U
 (meta U)[is acc in nil,U] [is positive in nil] [is acc in U]  >>True
Checking  (2) append(cons(X,Y),U) => cons(X,append(Y,U))
 (fun append>cons)
 (meta X)[is acc in cons(X,Y),U] [is positive in cons(X,Y)] [is acc in X] 
 (fun append=append) subterm comparison of args w. Mul Mul
 (meta Y)[is acc in cons(X,Y),U] [is positive in cons(X,Y)] [is acc in Y] 
 (meta U)[is acc in cons(X,Y),U] [is positive in cons(X,Y)] [is acc in U]  >>True
Checking  (3) reverse(nil) => nil
 (fun reverse>nil) >>True
Checking  (4) shuffle(nil) => nil
 (fun shuffle>nil) >>True
Checking  (5) shuffle(cons(X,Y)) => cons(X,shuffle(reverse(Y)))
 (fun shuffle>cons)
 (meta X)[is acc in cons(X,Y)] [is positive in cons(X,Y)] [is acc in X] 
 (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  (8) map(H,nil) => nil
 (fun map>nil) >>True
Checking  (9) map(H,cons(X,Y)) => cons(H[X],map(H,Y))
 (fun map>cons)
 (meta H)[is acc in H,cons(X,Y)] [is acc in H] 
 (meta X)[is acc in H,cons(X,Y)] [is positive in cons(X,Y)] [is acc in X] 
 (fun map=map) subterm comparison of args w. LR LR
 (meta H)[is acc in H,cons(X,Y)] [is acc in H] 
 (meta Y)[is acc in H,cons(X,Y)] [is positive in cons(X,Y)] [is acc in Y]  >>True
#SN!
******** Signature ********
 append : (list,list) -> list
 cons : (nat,list) -> list
 map : ((nat -> nat),list) -> list
 mirror : list -> list
 nil : list
 reverse : list -> list
 shuffle : list -> list
******** Computation Rules ********
 (1)  append(nil,U) => U
 (2)  append(cons(X,Y),U) => cons(X,append(Y,U))
 (3)  reverse(nil) => nil
 (4)  shuffle(nil) => nil
 (5)  shuffle(cons(X,Y)) => cons(X,shuffle(reverse(Y)))
 (6)  mirror(nil) => nil
 (7)  mirror(cons(X,Y)) => append(cons(X,mirror(Y)),cons(X,nil))
 (8)  map(H,nil) => nil
 (9)  map(H,cons(X,Y)) => cons(H[X],map(H,Y))

YES