/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: g(h(g(X))) -> g(X)
    2: g(g(Y)) -> g(h(g(Y)))
    3: h(h(U)) -> h(f(h(U),U))
    4: _(X1,X2) -> X1
    5: _(X1,X2) -> X2
Number of strict rules: 5
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
   #1: #g(g(Y)) -> #g(h(g(Y)))
   #2: #g(g(Y)) -> #h(g(Y))
   #3: #h(h(U)) -> #h(f(h(U),U))
Number of SCCs: 0, DPs: 0

...
Input TRS:
    1: g(h(g(X))) -> g(X)
    2: g(g(Y)) -> g(h(g(Y)))
    3: h(h(U)) -> h(f(h(U),U))
    4: _(X1,X2) -> X1
    5: _(X1,X2) -> X2
Number of strict rules: 5
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
   #1: #g(g(Y)) -> #g(h(g(Y)))
   #2: #g(g(Y)) -> #h(g(Y))
   #3: #h(h(U)) -> #h(f(h(U),U))
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 ********
 (4)  map(H,nil) => nil
 (5)  map(I,cons(P,X1)) => cons(I[P],map(I,X1))
 (6)  filter(Z1,nil) => nil
 (7)  filter(G1,cons(V1,W1)) => filter2(G1[V1],G1,V1,W1)
 (8)  filter2(true,J1,X2,Y2) => cons(X2,filter(J1,Y2))
 (9)  filter2(false,G2,V2,W2) => filter(G2,W2)


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

Try again using status RL
Checking  (1) g(h(g(X))) => g(X)
 (fun g=g) subterm comparison of args w. RL RL
 (meta X)[is acc in h(g(X))] [is positive in h(g(X))] [is positive in g(X)] [is acc in X]  >>True
Checking  (2) g(g(Y)) => g(h(g(Y)))
 (fun g=g) subterm comparison of args w. RL RL >>False

Try again using status Mul
Checking  (1) g(h(g(X))) => g(X)
 (fun g=g) subterm comparison of args w. Mul Mul
 (meta X)[is acc in h(g(X))] [is positive in h(g(X))] [is positive in g(X)] [is acc in X]  >>True
Checking  (2) g(g(Y)) => g(h(g(Y)))
 (fun g=g) 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  (4) map(H,nil) => nil
 (fun map>nil) >>True
Checking  (5) map(I,cons(P,X1)) => cons(I[P],map(I,X1))
 (fun map>cons)
 (meta I)[is acc in I,cons(P,X1)] [is acc in I] 
 (meta P)[is acc in I,cons(P,X1)] [is positive in cons(P,X1)] [is acc in P] 
 (fun map=map) subterm comparison of args w. LR LR
 (meta I)[is acc in I,cons(P,X1)] [is acc in I] 
 (meta X1)[is acc in I,cons(P,X1)] [is positive in cons(P,X1)] [is acc in X1]  >>True
Checking  (6) filter(Z1,nil) => nil
 (fun filter>nil) >>True
Checking  (7) filter(G1,cons(V1,W1)) => filter2(G1[V1],G1,V1,W1)
 (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1]
 (meta G1)[is acc in G1,cons(V1,W1)] [is acc in G1] 
 (meta V1)[is acc in G1,cons(V1,W1)] [is positive in cons(V1,W1)] [is acc in V1] 
 (meta G1)[is acc in G1,cons(V1,W1)] [is acc in G1] 
 (meta V1)[is acc in G1,cons(V1,W1)] [is positive in cons(V1,W1)] [is acc in V1] 
 (meta W1)[is acc in G1,cons(V1,W1)] [is positive in cons(V1,W1)] [is acc in W1]  >>True
Checking  (8) filter2(true,J1,X2,Y2) => cons(X2,filter(J1,Y2))
 (fun filter2>cons)
 (meta X2)[is acc in true,J1,X2,Y2] [is positive in true] [is acc in X2] 
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta J1)[is acc in true,J1,X2,Y2] [is positive in true] [is acc in J1] 
 (meta Y2)[is acc in true,J1,X2,Y2] [is positive in true] [is acc in Y2]  >>True
Checking  (9) filter2(false,G2,V2,W2) => filter(G2,W2)
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta G2)[is acc in false,G2,V2,W2] [is positive in false] [is acc in G2] 
 (meta W2)[is acc in false,G2,V2,W2] [is positive in false] [is acc in W2]  >>True
#SN!
******** Signature ********
 cons : (c,d) -> d
 f : (a,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)  g(h(g(X))) => g(X)
 (2)  g(g(Y)) => g(h(g(Y)))
 (3)  h(h(U)) => h(f(h(U),U))
 (4)  map(H,nil) => nil
 (5)  map(I,cons(P,X1)) => cons(I[P],map(I,X1))
 (6)  filter(Z1,nil) => nil
 (7)  filter(G1,cons(V1,W1)) => filter2(G1[V1],G1,V1,W1)
 (8)  filter2(true,J1,X2,Y2) => cons(X2,filter(J1,Y2))
 (9)  filter2(false,G2,V2,W2) => filter(G2,W2)

YES