/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: minus(0(),X) -> 0() 2: minus(s(Y),0()) -> s(Y) 3: minus(s(U),s(V)) -> minus(U,V) 4: le(0(),W) -> true() 5: le(s(P),0()) -> false() 6: le(s(X1),s(Y1)) -> le(X1,Y1) 7: if(true(),U1,V1) -> U1 8: if(false(),W1,P1) -> P1 9: perfectp(0()) -> false() 10: perfectp(s(X2)) -> f(X2,s(0()),s(X2),s(X2)) 11: f(0(),U2,0(),Y2) -> true() 12: f(0(),W2,s(P2),V2) -> false() 13: f(s(Y3),0(),U3,X3) -> f(Y3,X3,minus(U3,s(Y3)),X3) 14: f(s(W3),s(P3),X4,V3) -> if(le(W3,P3),f(s(W3),minus(P3,W3),X4,V3),f(W3,V3,X4,V3)) 15: _(X1,X2) -> X1 16: _(X1,X2) -> X2 Number of strict rules: 16 Direct POLO(bPol) ... failed. Uncurrying f 1: minus(0(),X) -> 0() 2: minus(s(Y),0()) -> s(Y) 3: minus(s(U),s(V)) -> minus(U,V) 4: le(0(),W) -> true() 5: le(s(P),0()) -> false() 6: le(s(X1),s(Y1)) -> le(X1,Y1) 7: if(true(),U1,V1) -> U1 8: if(false(),W1,P1) -> P1 9: perfectp(0()) -> false() 10: perfectp(s(X2)) -> f(X2,s(0()),s(X2),s(X2)) 11: f^1_0(U2,0(),Y2) -> true() 12: f^1_0(W2,s(P2),V2) -> false() 13: f^1_s(Y3,0(),U3,X3) -> f(Y3,X3,minus(U3,s(Y3)),X3) 14: f^1_s(W3,s(P3),X4,V3) -> if(le(W3,P3),f^1_s(W3,minus(P3,W3),X4,V3),f(W3,V3,X4,V3)) 15: _(X1,X2) -> X1 16: _(X1,X2) -> X2 17: f(0(),_3,_4,_5) ->= f^1_0(_3,_4,_5) 18: f(s(_1),_4,_5,_6) ->= f^1_s(_1,_4,_5,_6) Number of strict rules: 16 Direct POLO(bPol) ... failed. Dependency Pairs: #1: #le(s(X1),s(Y1)) -> #le(X1,Y1) #2: #f^1_s(Y3,0(),U3,X3) -> #f(Y3,X3,minus(U3,s(Y3)),X3) #3: #f^1_s(Y3,0(),U3,X3) -> #minus(U3,s(Y3)) #4: #f^1_s(W3,s(P3),X4,V3) -> #if(le(W3,P3),f^1_s(W3,minus(P3,W3),X4,V3),f(W3,V3,X4,V3)) #5: #f^1_s(W3,s(P3),X4,V3) -> #le(W3,P3) #6: #f^1_s(W3,s(P3),X4,V3) -> #f^1_s(W3,minus(P3,W3),X4,V3) #7: #f^1_s(W3,s(P3),X4,V3) -> #minus(P3,W3) #8: #f^1_s(W3,s(P3),X4,V3) -> #f(W3,V3,X4,V3) #9: #perfectp(s(X2)) -> #f(X2,s(0()),s(X2),s(X2)) #10: #f(0(),_3,_4,_5) ->? #f^1_0(_3,_4,_5) #11: #minus(s(U),s(V)) -> #minus(U,V) #12: #f(s(_1),_4,_5,_6) ->? #f^1_s(_1,_4,_5,_6) Number of SCCs: 3, DPs: 6 SCC { #1 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 1 #le w: x1 + x2 minus w: 0 #f^1_s w: 0 #perfectp w: 0 false w: 0 _ w: 0 true w: 0 f w: 0 0 w: 0 if w: 0 #f w: 0 #minus w: 0 #f^1_0 w: 0 #_ w: 0 #if w: 0 perfectp w: 0 f^1_0 w: 0 f^1_s w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 2, DPs: 5 SCC { #11 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 1 #le w: 0 minus w: 0 #f^1_s w: 0 #perfectp w: 0 false w: 0 _ w: 0 true w: 0 f w: 0 0 w: 0 if w: 0 #f w: 0 #minus w: x1 #f^1_0 w: 0 #_ w: 0 #if w: 0 perfectp w: 0 f^1_0 w: 0 f^1_s w: 0 USABLE RULES: { } Removed DPs: #11 Number of SCCs: 1, DPs: 4 SCC { #2 #6 #8 #12 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 4 #le w: 0 minus w: x2 + 1 #f^1_s w: x1 + x4 + 1 #perfectp w: 0 false w: 0 _ w: 0 true w: 0 f w: 0 0 w: 2 if w: 0 #f w: x1 + x4 #minus w: 0 #f^1_0 w: 0 #_ w: 0 #if w: 0 perfectp w: 0 f^1_0 w: 0 f^1_s w: 0 USABLE RULES: { } Removed DPs: #2 #8 #12 Number of SCCs: 1, DPs: 1 SCC { #6 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 2 #le w: 0 minus w: x1 + 1 #f^1_s w: x2 + 1 #perfectp w: 0 false w: 0 _ w: 0 true w: 0 f w: 0 0 w: 8856 if w: 0 #f w: 0 #minus w: 0 #f^1_0 w: 0 #_ w: 0 #if w: 0 perfectp w: 0 f^1_0 w: 0 f^1_s w: 0 USABLE RULES: { 1..3 } Removed DPs: #6 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: minus(0(),X) -> 0() 2: minus(s(Y),0()) -> s(Y) 3: minus(s(U),s(V)) -> minus(U,V) 4: le(0(),W) -> true() 5: le(s(P),0()) -> false() 6: le(s(X1),s(Y1)) -> le(X1,Y1) 7: if(true(),U1,V1) -> U1 8: if(false(),W1,P1) -> P1 9: perfectp(0()) -> false() 10: perfectp(s(X2)) -> f(X2,s(0()),s(X2),s(X2)) 11: f(0(),U2,0(),Y2) -> true() 12: f(0(),W2,s(P2),V2) -> false() 13: f(s(Y3),0(),U3,X3) -> f(Y3,X3,minus(U3,s(Y3)),X3) 14: f(s(W3),s(P3),X4,V3) -> if(le(W3,P3),f(s(W3),minus(P3,W3),X4,V3),f(W3,V3,X4,V3)) 15: _(X1,X2) -> X1 16: _(X1,X2) -> X2 Number of strict rules: 16 Direct POLO(bPol) ... failed. Uncurrying f 1: minus(0(),X) -> 0() 2: minus(s(Y),0()) -> s(Y) 3: minus(s(U),s(V)) -> minus(U,V) 4: le(0(),W) -> true() 5: le(s(P),0()) -> false() 6: le(s(X1),s(Y1)) -> le(X1,Y1) 7: if(true(),U1,V1) -> U1 8: if(false(),W1,P1) -> P1 9: perfectp(0()) -> false() 10: perfectp(s(X2)) -> f(X2,s(0()),s(X2),s(X2)) 11: f^1_0(U2,0(),Y2) -> true() 12: f^1_0(W2,s(P2),V2) -> false() 13: f^1_s(Y3,0(),U3,X3) -> f(Y3,X3,minus(U3,s(Y3)),X3) 14: f^1_s(W3,s(P3),X4,V3) -> if(le(W3,P3),f^1_s(W3,minus(P3,W3),X4,V3),f(W3,V3,X4,V3)) 15: _(X1,X2) -> X1 16: _(X1,X2) -> X2 17: f(0(),_3,_4,_5) ->= f^1_0(_3,_4,_5) 18: f(s(_1),_4,_5,_6) ->= f^1_s(_1,_4,_5,_6) Number of strict rules: 16 Direct POLO(bPol) ... failed. Dependency Pairs: #1: #le(s(X1),s(Y1)) -> #le(X1,Y1) #2: #f^1_s(Y3,0(),U3,X3) -> #f(Y3,X3,minus(U3,s(Y3)),X3) #3: #f^1_s(Y3,0(),U3,X3) -> #minus(U3,s(Y3)) #4: #f^1_s(W3,s(P3),X4,V3) -> #if(le(W3,P3),f^1_s(W3,minus(P3,W3),X4,V3),f(W3,V3,X4,V3)) #5: #f^1_s(W3,s(P3),X4,V3) -> #le(W3,P3) #6: #f^1_s(W3,s(P3),X4,V3) -> #f^1_s(W3,minus(P3,W3),X4,V3) #7: #f^1_s(W3,s(P3),X4,V3) -> #minus(P3,W3) #8: #f^1_s(W3,s(P3),X4,V3) -> #f(W3,V3,X4,V3) #9: #perfectp(s(X2)) -> #f(X2,s(0()),s(X2),s(X2)) #10: #f(0(),_3,_4,_5) ->? #f^1_0(_3,_4,_5) #11: #minus(s(U),s(V)) -> #minus(U,V) #12: #f(s(_1),_4,_5,_6) ->? #f^1_s(_1,_4,_5,_6) Number of SCCs: 3, DPs: 6 SCC { #1 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 1 #le w: x1 + x2 minus w: 0 #f^1_s w: 0 #perfectp w: 0 false w: 0 _ w: 0 true w: 0 f w: 0 0 w: 0 if w: 0 #f w: 0 #minus w: 0 #f^1_0 w: 0 #_ w: 0 #if w: 0 perfectp w: 0 f^1_0 w: 0 f^1_s w: 0 USABLE RULES: { } Removed DPs: #1 Number of SCCs: 2, DPs: 5 SCC { #11 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 1 #le w: 0 minus w: 0 #f^1_s w: 0 #perfectp w: 0 false w: 0 _ w: 0 true w: 0 f w: 0 0 w: 0 if w: 0 #f w: 0 #minus w: x1 #f^1_0 w: 0 #_ w: 0 #if w: 0 perfectp w: 0 f^1_0 w: 0 f^1_s w: 0 USABLE RULES: { } Removed DPs: #11 Number of SCCs: 1, DPs: 4 SCC { #2 #6 #8 #12 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 4 #le w: 0 minus w: x2 + 1 #f^1_s w: x1 + x4 + 1 #perfectp w: 0 false w: 0 _ w: 0 true w: 0 f w: 0 0 w: 2 if w: 0 #f w: x1 + x4 #minus w: 0 #f^1_0 w: 0 #_ w: 0 #if w: 0 perfectp w: 0 f^1_0 w: 0 f^1_s w: 0 USABLE RULES: { } Removed DPs: #2 #8 #12 Number of SCCs: 1, DPs: 1 SCC { #6 } POLO(Sum)... succeeded. le w: 0 s w: x1 + 2 #le w: 0 minus w: x1 + 1 #f^1_s w: x2 + 1 #perfectp w: 0 false w: 0 _ w: 0 true w: 0 f w: 0 0 w: 8856 if w: 0 #f w: 0 #minus w: 0 #f^1_0 w: 0 #_ w: 0 #if w: 0 perfectp w: 0 f^1_0 w: 0 f^1_s w: 0 USABLE RULES: { 1..3 } Removed DPs: #6 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 ******** (15) map(Z4,nil) => nil (16) map(G4,cons(V4,W4)) => cons(G4[V4],map(G4,W4)) (17) filter(J4,nil) => nil (18) filter(F5,cons(Y5,U5)) => filter2(F5[Y5],F5,Y5,U5) (19) filter2(true,H5,W5,P5) => cons(W5,filter(H5,P5)) (20) filter2(false,F6,Y6,U6) => filter(F6,U6) ******** General Schema criterion ******** Found constructors: 0, cons, false, nil, s, true Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>Regared as equal: filter2, filter Checking (1) minus(0,X) => 0 (fun minus>0) >>True Checking (2) minus(s(Y),0) => s(Y) (fun minus>s) (meta Y)[is acc in s(Y),0] [is positive in s(Y)] [is acc in Y] >>True Checking (3) minus(s(U),s(V)) => minus(U,V) (fun minus=minus) subterm comparison of args w. LR LR (meta U)[is acc in s(U),s(V)] [is positive in s(U)] [is acc in U] (meta V)[is acc in s(U),s(V)] [is positive in s(U)] [is positive in s(V)] [is acc in V] >>True Checking (4) le(0,W) => true (fun le>true) >>True Checking (5) le(s(P),0) => false (fun le>false) >>True Checking (6) le(s(X1),s(Y1)) => le(X1,Y1) (fun le=le) subterm comparison of args w. LR LR (meta X1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is acc in X1] (meta Y1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is positive in s(Y1)] [is acc in Y1] >>True Checking (7) if(true,U1,V1) => U1 (meta U1)[is acc in true,U1,V1] [is positive in true] [is acc in U1] >>True Checking (8) if(false,W1,P1) => P1 (meta P1)[is acc in false,W1,P1] [is positive in false] [is acc in P1] >>True Checking (9) perfectp(0) => false (fun perfectp>false) >>True Checking (10) perfectp(s(X2)) => f(X2,s(0),s(X2),s(X2)) (fun perfectp>f) (meta X2)[is acc in s(X2)] [is positive in s(X2)] [is acc in X2] (fun perfectp>s) (fun perfectp>0) (fun perfectp>s) (meta X2)[is acc in s(X2)] [is positive in s(X2)] [is acc in X2] (fun perfectp>s) (meta X2)[is acc in s(X2)] [is positive in s(X2)] [is acc in X2] >>True Checking (11) f(0,U2,0,Y2) => true (fun f>true) >>True Checking (12) f(0,W2,s(P2),V2) => false (fun f>false) >>True Checking (13) f(s(Y3),0,U3,X3) => f(Y3,X3,minus(U3,s(Y3)),X3) (fun f=f) subterm comparison of args w. LR LR (meta Y3)[is acc in s(Y3),0,U3,X3] [is positive in s(Y3)] [is acc in Y3] (meta X3)[is acc in s(Y3),0,U3,X3] [is positive in s(Y3)] [is positive in 0] [is acc in X3] (fun f>minus) (meta U3)[is acc in s(Y3),0,U3,X3] [is positive in s(Y3)] [is positive in 0] [is acc in U3] (fun f>s) (meta Y3)[is acc in s(Y3),0,U3,X3] [is positive in s(Y3)] [is acc in Y3] (meta X3)[is acc in s(Y3),0,U3,X3] [is positive in s(Y3)] [is positive in 0] [is acc in X3] >>True Checking (14) f(s(W3),s(P3),X4,V3) => if(le(W3,P3),f(s(W3),minus(P3,W3),X4,V3),f(W3,V3,X4,V3)) (fun f>if) (fun f>le) (meta W3)[is acc in s(W3),s(P3),X4,V3] [is positive in s(W3)] [is acc in W3] (meta P3)[is acc in s(W3),s(P3),X4,V3] [is positive in s(W3)] [is positive in s(P3)] [is acc in P3] (fun f=f) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) minus(0,X) => 0 (fun minus>0) >>True Checking (2) minus(s(Y),0) => s(Y) (fun minus>s) (meta Y)[is acc in s(Y),0] [is positive in s(Y)] [is acc in Y] >>True Checking (3) minus(s(U),s(V)) => minus(U,V) (fun minus=minus) subterm comparison of args w. RL RL (meta U)[is acc in s(U),s(V)] [is positive in s(U)] [is acc in U] (meta V)[is acc in s(U),s(V)] [is positive in s(U)] [is positive in s(V)] [is acc in V] >>True Checking (4) le(0,W) => true (fun le>true) >>True Checking (5) le(s(P),0) => false (fun le>false) >>True Checking (6) le(s(X1),s(Y1)) => le(X1,Y1) (fun le=le) subterm comparison of args w. RL RL (meta X1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is acc in X1] (meta Y1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is positive in s(Y1)] [is acc in Y1] >>True Checking (7) if(true,U1,V1) => U1 (meta U1)[is acc in true,U1,V1] [is positive in true] [is acc in U1] >>True Checking (8) if(false,W1,P1) => P1 (meta P1)[is acc in false,W1,P1] [is positive in false] [is acc in P1] >>True Checking (9) perfectp(0) => false (fun perfectp>false) >>True Checking (10) perfectp(s(X2)) => f(X2,s(0),s(X2),s(X2)) (fun perfectp>f) (meta X2)[is acc in s(X2)] [is positive in s(X2)] [is acc in X2] (fun perfectp>s) (fun perfectp>0) (fun perfectp>s) (meta X2)[is acc in s(X2)] [is positive in s(X2)] [is acc in X2] (fun perfectp>s) (meta X2)[is acc in s(X2)] [is positive in s(X2)] [is acc in X2] >>True Checking (11) f(0,U2,0,Y2) => true (fun f>true) >>True Checking (12) f(0,W2,s(P2),V2) => false (fun f>false) >>True Checking (13) f(s(Y3),0,U3,X3) => f(Y3,X3,minus(U3,s(Y3)),X3) (fun f=f) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) minus(0,X) => 0 (fun minus>0) >>True Checking (2) minus(s(Y),0) => s(Y) (fun minus>s) (meta Y)[is acc in s(Y),0] [is positive in s(Y)] [is acc in Y] >>True Checking (3) minus(s(U),s(V)) => minus(U,V) (fun minus=minus) subterm comparison of args w. Mul Mul (meta U)[is acc in s(U),s(V)] [is positive in s(U)] [is acc in U] (meta V)[is acc in s(U),s(V)] [is positive in s(U)] [is positive in s(V)] [is acc in V] >>True Checking (4) le(0,W) => true (fun le>true) >>True Checking (5) le(s(P),0) => false (fun le>false) >>True Checking (6) le(s(X1),s(Y1)) => le(X1,Y1) (fun le=le) subterm comparison of args w. Mul Mul (meta X1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is acc in X1] (meta Y1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is positive in s(Y1)] [is acc in Y1] >>True Checking (7) if(true,U1,V1) => U1 (meta U1)[is acc in true,U1,V1] [is positive in true] [is acc in U1] >>True Checking (8) if(false,W1,P1) => P1 (meta P1)[is acc in false,W1,P1] [is positive in false] [is acc in P1] >>True Checking (9) perfectp(0) => false (fun perfectp>false) >>True Checking (10) perfectp(s(X2)) => f(X2,s(0),s(X2),s(X2)) (fun perfectp>f) (meta X2)[is acc in s(X2)] [is positive in s(X2)] [is acc in X2] (fun perfectp>s) (fun perfectp>0) (fun perfectp>s) (meta X2)[is acc in s(X2)] [is positive in s(X2)] [is acc in X2] (fun perfectp>s) (meta X2)[is acc in s(X2)] [is positive in s(X2)] [is acc in X2] >>True Checking (11) f(0,U2,0,Y2) => true (fun f>true) >>True Checking (12) f(0,W2,s(P2),V2) => false (fun f>false) >>True Checking (13) f(s(Y3),0,U3,X3) => f(Y3,X3,minus(U3,s(Y3)),X3) (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 (15) map(Z4,nil) => nil (fun map>nil) >>True Checking (16) map(G4,cons(V4,W4)) => cons(G4[V4],map(G4,W4)) (fun map>cons) (meta G4)[is acc in G4,cons(V4,W4)] [is acc in G4] (meta V4)[is acc in G4,cons(V4,W4)] [is positive in cons(V4,W4)] [is acc in V4] (fun map=map) subterm comparison of args w. LR LR (meta G4)[is acc in G4,cons(V4,W4)] [is acc in G4] (meta W4)[is acc in G4,cons(V4,W4)] [is positive in cons(V4,W4)] [is acc in W4] >>True Checking (17) filter(J4,nil) => nil (fun filter>nil) >>True Checking (18) filter(F5,cons(Y5,U5)) => filter2(F5[Y5],F5,Y5,U5) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (meta F5)[is acc in F5,cons(Y5,U5)] [is acc in F5] (meta Y5)[is acc in F5,cons(Y5,U5)] [is positive in cons(Y5,U5)] [is acc in Y5] (meta F5)[is acc in F5,cons(Y5,U5)] [is acc in F5] (meta Y5)[is acc in F5,cons(Y5,U5)] [is positive in cons(Y5,U5)] [is acc in Y5] (meta U5)[is acc in F5,cons(Y5,U5)] [is positive in cons(Y5,U5)] [is acc in U5] >>True Checking (19) filter2(true,H5,W5,P5) => cons(W5,filter(H5,P5)) (fun filter2>cons) (meta W5)[is acc in true,H5,W5,P5] [is positive in true] [is acc in W5] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta H5)[is acc in true,H5,W5,P5] [is positive in true] [is acc in H5] (meta P5)[is acc in true,H5,W5,P5] [is positive in true] [is acc in P5] >>True Checking (20) filter2(false,F6,Y6,U6) => filter(F6,U6) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta F6)[is acc in false,F6,Y6,U6] [is positive in false] [is acc in F6] (meta U6)[is acc in false,F6,Y6,U6] [is positive in false] [is acc in U6] >>True #SN! ******** Signature ******** 0 : a cons : (c,d) -> d f : (a,a,a,a) -> b false : b filter : ((c -> b),d) -> d filter2 : (b,(c -> b),c,d) -> d if : (b,b,b) -> b le : (a,a) -> b map : ((c -> c),d) -> d minus : (a,a) -> a nil : d perfectp : a -> b s : a -> a true : b ******** Computation Rules ******** (1) minus(0,X) => 0 (2) minus(s(Y),0) => s(Y) (3) minus(s(U),s(V)) => minus(U,V) (4) le(0,W) => true (5) le(s(P),0) => false (6) le(s(X1),s(Y1)) => le(X1,Y1) (7) if(true,U1,V1) => U1 (8) if(false,W1,P1) => P1 (9) perfectp(0) => false (10) perfectp(s(X2)) => f(X2,s(0),s(X2),s(X2)) (11) f(0,U2,0,Y2) => true (12) f(0,W2,s(P2),V2) => false (13) f(s(Y3),0,U3,X3) => f(Y3,X3,minus(U3,s(Y3)),X3) (14) f(s(W3),s(P3),X4,V3) => if(le(W3,P3),f(s(W3),minus(P3,W3),X4,V3),f(W3,V3,X4,V3)) (15) map(Z4,nil) => nil (16) map(G4,cons(V4,W4)) => cons(G4[V4],map(G4,W4)) (17) filter(J4,nil) => nil (18) filter(F5,cons(Y5,U5)) => filter2(F5[Y5],F5,Y5,U5) (19) filter2(true,H5,W5,P5) => cons(W5,filter(H5,P5)) (20) filter2(false,F6,Y6,U6) => filter(F6,U6) YES