/export/starexec/sandbox/solver/bin/starexec_run_hrs /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: perfectp(0()) -> false()
    2: perfectp(s(X)) -> f(X,s(0()),s(X),s(X))
    3: f(0(),U,0(),Y) -> true()
    4: f(0(),W,s(P),V) -> false()
    5: f(s(Y1),0(),U1,X1) -> f(Y1,X1,minus(U1,s(Y1)),X1)
    6: f(s(W1),s(P1),X2,V1) -> if(le(W1,P1),f(s(W1),minus(P1,W1),X2,V1),f(W1,V1,X2,V1))
    7: _(X1,X2) -> X1
    8: _(X1,X2) -> X2
Number of strict rules: 8
Direct POLO(bPol) ... failed.
Uncurrying f
1: perfectp(0()) -> false()
2: perfectp(s(X)) -> f(X,s(0()),s(X),s(X))
3: f^1_0(U,0(),Y) -> true()
4: f^1_0(W,s(P),V) -> false()
5: f^1_s(Y1,0(),U1,X1) -> f(Y1,X1,minus(U1,s(Y1)),X1)
6: f^1_s(W1,s(P1),X2,V1) -> if(le(W1,P1),f^1_s(W1,minus(P1,W1),X2,V1),f(W1,V1,X2,V1))
7: _(X1,X2) -> X1
8: _(X1,X2) -> X2
9: f(0(),_3,_4,_5) ->= f^1_0(_3,_4,_5)
10: f(s(_1),_4,_5,_6) ->= f^1_s(_1,_4,_5,_6)
Number of strict rules: 8
Direct POLO(bPol) ... failed.
Dependency Pairs:
   #1: #perfectp(s(X)) -> #f(X,s(0()),s(X),s(X))
   #2: #f^1_s(W1,s(P1),X2,V1) -> #f^1_s(W1,minus(P1,W1),X2,V1)
   #3: #f^1_s(W1,s(P1),X2,V1) -> #f(W1,V1,X2,V1)
   #4: #f(0(),_3,_4,_5) ->? #f^1_0(_3,_4,_5)
   #5: #f(s(_1),_4,_5,_6) ->? #f^1_s(_1,_4,_5,_6)
   #6: #f^1_s(Y1,0(),U1,X1) -> #f(Y1,X1,minus(U1,s(Y1)),X1)
Number of SCCs: 1, DPs: 3
  SCC { #3 #5 #6 }
POLO(Sum)... succeeded.
      le	w: 0
      s 	w: x1 + 2
      minus	w: x2
      #f^1_s	w: x1 + 1
      #perfectp	w: 0
      false	w: 0
      _ 	w: 0
      true	w: 0
      f 	w: 0
      0 	w: 1
      if	w: 0
      #f 	w: x1
      #f^1_0	w: 0
      #_ 	w: 0
      perfectp	w: 0
      f^1_0	w: 0
      f^1_s	w: 0
    USABLE RULES: { }
    Removed DPs: #3 #5 #6
Number of SCCs: 0, DPs: 0

...
Input TRS:
    1: perfectp(0()) -> false()
    2: perfectp(s(X)) -> f(X,s(0()),s(X),s(X))
    3: f(0(),U,0(),Y) -> true()
    4: f(0(),W,s(P),V) -> false()
    5: f(s(Y1),0(),U1,X1) -> f(Y1,X1,minus(U1,s(Y1)),X1)
    6: f(s(W1),s(P1),X2,V1) -> if(le(W1,P1),f(s(W1),minus(P1,W1),X2,V1),f(W1,V1,X2,V1))
    7: _(X1,X2) -> X1
    8: _(X1,X2) -> X2
Number of strict rules: 8
Direct POLO(bPol) ... failed.
Uncurrying f
1: perfectp(0()) -> false()
2: perfectp(s(X)) -> f(X,s(0()),s(X),s(X))
3: f^1_0(U,0(),Y) -> true()
4: f^1_0(W,s(P),V) -> false()
5: f^1_s(Y1,0(),U1,X1) -> f(Y1,X1,minus(U1,s(Y1)),X1)
6: f^1_s(W1,s(P1),X2,V1) -> if(le(W1,P1),f^1_s(W1,minus(P1,W1),X2,V1),f(W1,V1,X2,V1))
7: _(X1,X2) -> X1
8: _(X1,X2) -> X2
9: f(0(),_3,_4,_5) ->= f^1_0(_3,_4,_5)
10: f(s(_1),_4,_5,_6) ->= f^1_s(_1,_4,_5,_6)
Number of strict rules: 8
Direct POLO(bPol) ... failed.
Dependency Pairs:
   #1: #perfectp(s(X)) -> #f(X,s(0()),s(X),s(X))
   #2: #f^1_s(W1,s(P1),X2,V1) -> #f^1_s(W1,minus(P1,W1),X2,V1)
   #3: #f^1_s(W1,s(P1),X2,V1) -> #f(W1,V1,X2,V1)
   #4: #f(0(),_3,_4,_5) ->? #f^1_0(_3,_4,_5)
   #5: #f(s(_1),_4,_5,_6) ->? #f^1_s(_1,_4,_5,_6)
   #6: #f^1_s(Y1,0(),U1,X1) -> #f(Y1,X1,minus(U1,s(Y1)),X1)
Number of SCCs: 1, DPs: 3
  SCC { #3 #5 #6 }
POLO(Sum)... succeeded.
      le	w: 0
      s 	w: x1 + 2
      minus	w: x2
      #f^1_s	w: x1 + 1
      #perfectp	w: 0
      false	w: 0
      _ 	w: 0
      true	w: 0
      f 	w: 0
      0 	w: 1
      if	w: 0
      #f 	w: x1
      #f^1_0	w: 0
      #_ 	w: 0
      perfectp	w: 0
      f^1_0	w: 0
      f^1_s	w: 0
    USABLE RULES: { }
    Removed DPs: #3 #5 #6
Number of SCCs: 0, DPs: 0
>>YES

******** Signature ********
 map : ((d -> d),e) -> e
 nil : e
 cons : (d,e) -> e
 filter : ((d -> c),e) -> e
 filter2 : (c,(d -> c),d,e) -> e
 true : c
 false : c
******** Computation rules ********
 (7)  map(Z2,nil) => nil
 (8)  map(G2,cons(V2,W2)) => cons(G2[V2],map(G2,W2))
 (9)  filter(J2,nil) => nil
 (10)  filter(F3,cons(Y3,U3)) => filter2(F3[Y3],F3,Y3,U3)
 (11)  filter2(true,H3,W3,P3) => cons(W3,filter(H3,P3))
 (12)  filter2(false,F4,Y4,U4) => filter(F4,U4)


******** General Schema criterion ********
Found constructors: 0, cons, false, if, le, minus, nil, s, true
Checking type order >>OK
Checking positivity of constructors >>OK
Checking function dependency >>Regared as equal: filter2, filter
Checking  (1) perfectp(0) => false
 (fun perfectp>false) >>True
Checking  (2) perfectp(s(X)) => f(X,s(0),s(X),s(X))
 (fun perfectp>f)
 (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] 
 (fun perfectp>s)
 (fun perfectp>0)
 (fun perfectp>s)
 (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] 
 (fun perfectp>s)
 (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X]  >>True
Checking  (3) f(0,U,0,Y) => true
 (fun f>true) >>True
Checking  (4) f(0,W,s(P),V) => false
 (fun f>false) >>True
Checking  (5) f(s(Y1),0,U1,X1) => f(Y1,X1,minus(U1,s(Y1)),X1)
 (fun f=f) subterm comparison of args w. LR LR
 (meta Y1)[is acc in s(Y1),0,U1,X1] [is positive in s(Y1)] [is acc in Y1] 
 (meta X1)[is acc in s(Y1),0,U1,X1] [is positive in s(Y1)] [is positive in 0] [is acc in X1] 
 (fun f>minus)
 (meta U1)[is acc in s(Y1),0,U1,X1] [is positive in s(Y1)] [is positive in 0] [is acc in U1] 
 (fun f>s)
 (meta Y1)[is acc in s(Y1),0,U1,X1] [is positive in s(Y1)] [is acc in Y1] 
 (meta X1)[is acc in s(Y1),0,U1,X1] [is positive in s(Y1)] [is positive in 0] [is acc in X1]  >>True
Checking  (6) f(s(W1),s(P1),X2,V1) => if(le(W1,P1),f(s(W1),minus(P1,W1),X2,V1),f(W1,V1,X2,V1))
 (fun f>if)
 (fun f>le)
 (meta W1)[is acc in s(W1),s(P1),X2,V1] [is positive in s(W1)] [is acc in W1] 
 (meta P1)[is acc in s(W1),s(P1),X2,V1] [is positive in s(W1)] [is positive in s(P1)] [is acc in P1] 
 (fun f=f) subterm comparison of args w. LR LR >>False

Try again using status RL
Checking  (1) perfectp(0) => false
 (fun perfectp>false) >>True
Checking  (2) perfectp(s(X)) => f(X,s(0),s(X),s(X))
 (fun perfectp>f)
 (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] 
 (fun perfectp>s)
 (fun perfectp>0)
 (fun perfectp>s)
 (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] 
 (fun perfectp>s)
 (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X]  >>True
Checking  (3) f(0,U,0,Y) => true
 (fun f>true) >>True
Checking  (4) f(0,W,s(P),V) => false
 (fun f>false) >>True
Checking  (5) f(s(Y1),0,U1,X1) => f(Y1,X1,minus(U1,s(Y1)),X1)
 (fun f=f) subterm comparison of args w. RL RL >>False

Try again using status Mul
Checking  (1) perfectp(0) => false
 (fun perfectp>false) >>True
Checking  (2) perfectp(s(X)) => f(X,s(0),s(X),s(X))
 (fun perfectp>f)
 (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] 
 (fun perfectp>s)
 (fun perfectp>0)
 (fun perfectp>s)
 (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] 
 (fun perfectp>s)
 (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X]  >>True
Checking  (3) f(0,U,0,Y) => true
 (fun f>true) >>True
Checking  (4) f(0,W,s(P),V) => false
 (fun f>false) >>True
Checking  (5) f(s(Y1),0,U1,X1) => f(Y1,X1,minus(U1,s(Y1)),X1)
 (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  (7) map(Z2,nil) => nil
 (fun map>nil) >>True
Checking  (8) map(G2,cons(V2,W2)) => cons(G2[V2],map(G2,W2))
 (fun map>cons)
 (meta G2)[is acc in G2,cons(V2,W2)] [is acc in G2] 
 (meta V2)[is acc in G2,cons(V2,W2)] [is positive in cons(V2,W2)] [is acc in V2] 
 (fun map=map) subterm comparison of args w. LR LR
 (meta G2)[is acc in G2,cons(V2,W2)] [is acc in G2] 
 (meta W2)[is acc in G2,cons(V2,W2)] [is positive in cons(V2,W2)] [is acc in W2]  >>True
Checking  (9) filter(J2,nil) => nil
 (fun filter>nil) >>True
Checking  (10) filter(F3,cons(Y3,U3)) => filter2(F3[Y3],F3,Y3,U3)
 (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1]
 (meta F3)[is acc in F3,cons(Y3,U3)] [is acc in F3] 
 (meta Y3)[is acc in F3,cons(Y3,U3)] [is positive in cons(Y3,U3)] [is acc in Y3] 
 (meta F3)[is acc in F3,cons(Y3,U3)] [is acc in F3] 
 (meta Y3)[is acc in F3,cons(Y3,U3)] [is positive in cons(Y3,U3)] [is acc in Y3] 
 (meta U3)[is acc in F3,cons(Y3,U3)] [is positive in cons(Y3,U3)] [is acc in U3]  >>True
Checking  (11) filter2(true,H3,W3,P3) => cons(W3,filter(H3,P3))
 (fun filter2>cons)
 (meta W3)[is acc in true,H3,W3,P3] [is positive in true] [is acc in W3] 
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta H3)[is acc in true,H3,W3,P3] [is positive in true] [is acc in H3] 
 (meta P3)[is acc in true,H3,W3,P3] [is positive in true] [is acc in P3]  >>True
Checking  (12) filter2(false,F4,Y4,U4) => filter(F4,U4)
 (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2]
 (meta F4)[is acc in false,F4,Y4,U4] [is positive in false] [is acc in F4] 
 (meta U4)[is acc in false,F4,Y4,U4] [is positive in false] [is acc in U4]  >>True
#SN!
******** Signature ********
 0 : b
 cons : (d,e) -> e
 f : (b,b,b,b) -> c
 false : c
 filter : ((d -> c),e) -> e
 filter2 : (c,(d -> c),d,e) -> e
 if : (a,c,c) -> c
 le : (b,b) -> a
 map : ((d -> d),e) -> e
 minus : (b,b) -> b
 nil : e
 perfectp : b -> c
 s : b -> b
 true : c
******** Computation Rules ********
 (1)  perfectp(0) => false
 (2)  perfectp(s(X)) => f(X,s(0),s(X),s(X))
 (3)  f(0,U,0,Y) => true
 (4)  f(0,W,s(P),V) => false
 (5)  f(s(Y1),0,U1,X1) => f(Y1,X1,minus(U1,s(Y1)),X1)
 (6)  f(s(W1),s(P1),X2,V1) => if(le(W1,P1),f(s(W1),minus(P1,W1),X2,V1),f(W1,V1,X2,V1))
 (7)  map(Z2,nil) => nil
 (8)  map(G2,cons(V2,W2)) => cons(G2[V2],map(G2,W2))
 (9)  filter(J2,nil) => nil
 (10)  filter(F3,cons(Y3,U3)) => filter2(F3[Y3],F3,Y3,U3)
 (11)  filter2(true,H3,W3,P3) => cons(W3,filter(H3,P3))
 (12)  filter2(false,F4,Y4,U4) => filter(F4,U4)

YES