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

...
Input TRS:
    1: f(0(),1(),X) -> f(s(X),X,X)
    2: f(Y,U,s(V)) -> s(f(0(),1(),V))
    3: _(X1,X2) -> X1
    4: _(X1,X2) -> X2
Number of strict rules: 4
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
   #1: #f(Y,U,s(V)) -> #f(0(),1(),V)
   #2: #f(0(),1(),X) -> #f(s(X),X,X)
Number of SCCs: 1, DPs: 2
  SCC { #1 #2 }
POLO(Sum)... succeeded.
      1 	w: 1
      s 	w: x1 + 2
      _ 	w: 0
      f 	w: 0
      0 	w: 1
      #f 	w: x3
      #_ 	w: 0
    USABLE RULES: { }
    Removed DPs: #1
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(I,nil) => nil
 (4)  map(J,cons(X1,Y1)) => cons(J[X1],map(J,Y1))
 (5)  filter(G1,nil) => nil
 (6)  filter(H1,cons(W1,P1)) => filter2(H1[W1],H1,W1,P1)
 (7)  filter2(true,F2,Y2,U2) => cons(Y2,filter(F2,U2))
 (8)  filter2(false,H2,W2,P2) => filter(H2,P2)


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

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

Try again using status Mul
Checking  (1) f(0,1,X) => f(s(X),X,X)
 (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(I,nil) => nil
 (fun map>nil) >>True
Checking  (4) map(J,cons(X1,Y1)) => cons(J[X1],map(J,Y1))
 (fun map>cons)
 (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] 
 (fun map=map) subterm comparison of args w. LR LR
 (meta J)[is acc in J,cons(X1,Y1)] [is acc in J] 
 (meta Y1)[is acc in J,cons(X1,Y1)] [is positive in cons(X1,Y1)] [is acc in Y1]  >>True
Checking  (5) filter(G1,nil) => nil
 (fun filter>nil) >>True
Checking  (6) filter(H1,cons(W1,P1)) => filter2(H1[W1],H1,W1,P1)
 (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1]
 (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] 
 (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] 
 (meta P1)[is acc in H1,cons(W1,P1)] [is positive in cons(W1,P1)] [is acc in P1]  >>True
Checking  (7) filter2(true,F2,Y2,U2) => cons(Y2,filter(F2,U2))
 (fun filter2>cons)
 (meta Y2)[is acc in true,F2,Y2,U2] [is positive in true] [is acc in Y2] 
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta F2)[is acc in true,F2,Y2,U2] [is positive in true] [is acc in F2] 
 (meta U2)[is acc in true,F2,Y2,U2] [is positive in true] [is acc in U2]  >>True
Checking  (8) filter2(false,H2,W2,P2) => filter(H2,P2)
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta H2)[is acc in false,H2,W2,P2] [is positive in false] [is acc in H2] 
 (meta P2)[is acc in false,H2,W2,P2] [is positive in false] [is acc in P2]  >>True
#SN!
******** Signature ********
 0 : a
 1 : a
 cons : (c,d) -> d
 f : (a,a,a) -> a
 false : b
 filter : ((c -> b),d) -> d
 filter2 : (b,(c -> b),c,d) -> d
 map : ((c -> c),d) -> d
 nil : d
 s : a -> a
 true : b
******** Computation Rules ********
 (1)  f(0,1,X) => f(s(X),X,X)
 (2)  f(Y,U,s(V)) => s(f(0,1,V))
 (3)  map(I,nil) => nil
 (4)  map(J,cons(X1,Y1)) => cons(J[X1],map(J,Y1))
 (5)  filter(G1,nil) => nil
 (6)  filter(H1,cons(W1,P1)) => filter2(H1[W1],H1,W1,P1)
 (7)  filter2(true,F2,Y2,U2) => cons(Y2,filter(F2,U2))
 (8)  filter2(false,H2,W2,P2) => filter(H2,P2)

YES