/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: f(g(X)) -> g(f(f(X)))
    2: f(h(Y)) -> h(g(Y))
    3: _(X1,X2) -> X1
    4: _(X1,X2) -> X2
Number of strict rules: 4
Direct POLO(bPol) ... removes: 4 3
      h 	w: x1 + 8856
      _ 	w: 2 * x1 + x2 + 1
      f 	w: x1
      g 	w: x1
Number of strict rules: 2
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
   #1: #f(g(X)) -> #f(f(X))
   #2: #f(g(X)) -> #f(X)
Number of SCCs: 1, DPs: 2
  SCC { #1 #2 }
POLO(Sum)... succeeded.
      h 	w: 1
      _ 	w: 0
      f 	w: x1
      #f 	w: x1
      g 	w: x1 + 1237
    USABLE RULES: { 1 2 }
    Removed DPs: #1 #2
Number of SCCs: 0, DPs: 0

...
Input TRS:
    1: f(g(X)) -> g(f(f(X)))
    2: f(h(Y)) -> h(g(Y))
    3: _(X1,X2) -> X1
    4: _(X1,X2) -> X2
Number of strict rules: 4
Direct POLO(bPol) ... removes: 4 3
      h 	w: x1 + 8856
      _ 	w: 2 * x1 + x2 + 1
      f 	w: x1
      g 	w: x1
Number of strict rules: 2
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
   #1: #f(g(X)) -> #f(f(X))
   #2: #f(g(X)) -> #f(X)
Number of SCCs: 1, DPs: 2
  SCC { #1 #2 }
POLO(Sum)... succeeded.
      h 	w: 1
      _ 	w: 0
      f 	w: x1
      #f 	w: x1
      g 	w: x1 + 1237
    USABLE RULES: { 1 2 }
    Removed DPs: #1 #2
Number of SCCs: 0, DPs: 0
>>YES

******** Signature ********
 map : ((c -> c),d) -> d
 nil : d
 cons : (c,d) -> d
 filter : ((c -> b),d) -> d
 filter2 : (b,(c -> b),c,d) -> d
 true : b
 false : b
******** Computation rules ********
 (3)  map(G,nil) => nil
 (4)  map(H,cons(W,P)) => cons(H[W],map(H,P))
 (5)  filter(F1,nil) => nil
 (6)  filter(Z1,cons(U1,V1)) => filter2(Z1[U1],Z1,U1,V1)
 (7)  filter2(true,I1,P1,X2) => cons(P1,filter(I1,X2))
 (8)  filter2(false,Z2,U2,V2) => filter(Z2,V2)


******** General Schema criterion ********
Found constructors: cons, false, g, h, nil, true
Checking type order >>OK
Checking positivity of constructors >>OK
Checking function dependency >>Regared as equal: filter2, filter
Checking  (1) f(g(X)) => g(f(f(X)))
 (fun f>g)
 (fun f=f) subterm comparison of args w. LR LR >>False

Try again using status RL
Checking  (1) f(g(X)) => g(f(f(X)))
 (fun f>g)
 (fun f=f) subterm comparison of args w. RL RL >>False

Try again using status Mul
Checking  (1) f(g(X)) => g(f(f(X)))
 (fun f>g)
 (fun f=f) subterm comparison of args w. Mul Mul >>False
Found constructors: nil, cons, true, false
Checking type order >>OK
Checking positivity of constructors >>OK
Checking function dependency >>Regared as equal: filter2, filter
Checking  (3) map(G,nil) => nil
 (fun map>nil) >>True
Checking  (4) map(H,cons(W,P)) => cons(H[W],map(H,P))
 (fun map>cons)
 (meta H)[is acc in H,cons(W,P)] [is acc in H] 
 (meta W)[is acc in H,cons(W,P)] [is positive in cons(W,P)] [is acc in W] 
 (fun map=map) subterm comparison of args w. LR LR
 (meta H)[is acc in H,cons(W,P)] [is acc in H] 
 (meta P)[is acc in H,cons(W,P)] [is positive in cons(W,P)] [is acc in P]  >>True
Checking  (5) filter(F1,nil) => nil
 (fun filter>nil) >>True
Checking  (6) filter(Z1,cons(U1,V1)) => filter2(Z1[U1],Z1,U1,V1)
 (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1]
 (meta Z1)[is acc in Z1,cons(U1,V1)] [is acc in Z1] 
 (meta U1)[is acc in Z1,cons(U1,V1)] [is positive in cons(U1,V1)] [is acc in U1] 
 (meta Z1)[is acc in Z1,cons(U1,V1)] [is acc in Z1] 
 (meta U1)[is acc in Z1,cons(U1,V1)] [is positive in cons(U1,V1)] [is acc in U1] 
 (meta V1)[is acc in Z1,cons(U1,V1)] [is positive in cons(U1,V1)] [is acc in V1]  >>True
Checking  (7) filter2(true,I1,P1,X2) => cons(P1,filter(I1,X2))
 (fun filter2>cons)
 (meta P1)[is acc in true,I1,P1,X2] [is positive in true] [is acc in P1] 
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta I1)[is acc in true,I1,P1,X2] [is positive in true] [is acc in I1] 
 (meta X2)[is acc in true,I1,P1,X2] [is positive in true] [is acc in X2]  >>True
Checking  (8) filter2(false,Z2,U2,V2) => filter(Z2,V2)
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta Z2)[is acc in false,Z2,U2,V2] [is positive in false] [is acc in Z2] 
 (meta V2)[is acc in false,Z2,U2,V2] [is positive in false] [is acc in V2]  >>True
#SN!
******** Signature ********
 cons : (c,d) -> d
 f : a -> a
 false : b
 filter : ((c -> b),d) -> d
 filter2 : (b,(c -> b),c,d) -> d
 g : a -> a
 h : a -> a
 map : ((c -> c),d) -> d
 nil : d
 true : b
******** Computation Rules ********
 (1)  f(g(X)) => g(f(f(X)))
 (2)  f(h(Y)) => h(g(Y))
 (3)  map(G,nil) => nil
 (4)  map(H,cons(W,P)) => cons(H[W],map(H,P))
 (5)  filter(F1,nil) => nil
 (6)  filter(Z1,cons(U1,V1)) => filter2(Z1[U1],Z1,U1,V1)
 (7)  filter2(true,I1,P1,X2) => cons(P1,filter(I1,X2))
 (8)  filter2(false,Z2,U2,V2) => filter(Z2,V2)

YES