/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: f(a()) -> f(b())
    2: g(b()) -> g(a())
    3: _(X1,X2) -> X1
    4: _(X1,X2) -> X2
Number of strict rules: 4
Direct POLO(bPol) ... removes: 4 3
      a 	w: 2
      b 	w: 2
      _ 	w: 2 * x1 + x2 + 1
      f 	w: x1 + 8855
      g 	w: x1 + 449
Number of strict rules: 2
Direct POLO(bPol) ... failed.
Uncurrying f g
1: f^1_a() -> f^1_b()
2: g^1_b() -> g^1_a()
5: g(a()) ->= g^1_a()
6: g(b()) ->= g^1_b()
7: f(a()) ->= f^1_a()
8: f(b()) ->= f^1_b()
Number of strict rules: 2
Direct POLO(bPol) ... removes: 8 1 5 7 6 2
      a 	w: 7720
      g^1_b	w: 1
      b 	w: 1
      g^1_a	w: 0
      f^1_b	w: 0
      _ 	w: x1 + x2
      f 	w: 2 * x1 + 1
      f^1_a	w: 1
      g 	w: 2 * x1 + 2437
Number of strict rules: 0

...
Input TRS:
    1: f(a()) -> f(b())
    2: g(b()) -> g(a())
    3: _(X1,X2) -> X1
    4: _(X1,X2) -> X2
Number of strict rules: 4
Direct POLO(bPol) ... removes: 4 3
      a 	w: 2
      b 	w: 2
      _ 	w: 2 * x1 + x2 + 1
      f 	w: x1 + 8855
      g 	w: x1 + 449
Number of strict rules: 2
Direct POLO(bPol) ... failed.
Uncurrying f g
1: f^1_a() -> f^1_b()
2: g^1_b() -> g^1_a()
5: g(a()) ->= g^1_a()
6: g(b()) ->= g^1_b()
7: f(a()) ->= f^1_a()
8: f(b()) ->= f^1_b()
Number of strict rules: 2
Direct POLO(bPol) ... removes: 8 1 5 7 6 2
      a 	w: 7720
      g^1_b	w: 1
      b 	w: 1
      g^1_a	w: 0
      f^1_b	w: 0
      _ 	w: x1 + x2
      f 	w: 2 * x1 + 1
      f^1_a	w: 1
      g 	w: 2 * x1 + 2437
Number of strict rules: 0
>>YES

******** Signature ********
 map : ((e -> e),f) -> f
 nil : f
 cons : (e,f) -> f
 filter : ((e -> d),f) -> f
 filter2 : (d,(e -> d),e,f) -> f
 true : d
 false : d
******** Computation rules ********
 (3)  map(F,nil) => nil
 (4)  map(Z,cons(U,V)) => cons(Z[U],map(Z,V))
 (5)  filter(I,nil) => nil
 (6)  filter(J,cons(X1,Y1)) => filter2(J[X1],J,X1,Y1)
 (7)  filter2(true,G1,V1,W1) => cons(V1,filter(G1,W1))
 (8)  filter2(false,J1,X2,Y2) => filter(J1,Y2)


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

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

Try again using status Mul
Checking  (1) f(a) => f(b)
 (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(F,nil) => nil
 (fun map>nil) >>True
Checking  (4) 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  (5) filter(I,nil) => nil
 (fun filter>nil) >>True
Checking  (6) filter(J,cons(X1,Y1)) => filter2(J[X1],J,X1,Y1)
 (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1]
 (meta J)[is acc in J,cons(X1,Y1)] [is acc in J] 
 (meta X1)[is acc in J,cons(X1,Y1)] [is positive in cons(X1,Y1)] [is acc in X1] 
 (meta J)[is acc in J,cons(X1,Y1)] [is acc in J] 
 (meta X1)[is acc in J,cons(X1,Y1)] [is positive in cons(X1,Y1)] [is acc in X1] 
 (meta Y1)[is acc in J,cons(X1,Y1)] [is positive in cons(X1,Y1)] [is acc in Y1]  >>True
Checking  (7) filter2(true,G1,V1,W1) => cons(V1,filter(G1,W1))
 (fun filter2>cons)
 (meta V1)[is acc in true,G1,V1,W1] [is positive in true] [is acc in V1] 
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta G1)[is acc in true,G1,V1,W1] [is positive in true] [is acc in G1] 
 (meta W1)[is acc in true,G1,V1,W1] [is positive in true] [is acc in W1]  >>True
Checking  (8) filter2(false,J1,X2,Y2) => filter(J1,Y2)
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta J1)[is acc in false,J1,X2,Y2] [is positive in false] [is acc in J1] 
 (meta Y2)[is acc in false,J1,X2,Y2] [is positive in false] [is acc in Y2]  >>True
#SN!
******** Signature ********
 a : a
 b : a
 cons : (e,f) -> f
 f : a -> b
 false : d
 filter : ((e -> d),f) -> f
 filter2 : (d,(e -> d),e,f) -> f
 g : a -> c
 map : ((e -> e),f) -> f
 nil : f
 true : d
******** Computation Rules ********
 (1)  f(a) => f(b)
 (2)  g(b) => g(a)
 (3)  map(F,nil) => nil
 (4)  map(Z,cons(U,V)) => cons(Z[U],map(Z,V))
 (5)  filter(I,nil) => nil
 (6)  filter(J,cons(X1,Y1)) => filter2(J[X1],J,X1,Y1)
 (7)  filter2(true,G1,V1,W1) => cons(V1,filter(G1,W1))
 (8)  filter2(false,J1,X2,Y2) => filter(J1,Y2)

YES