/export/starexec/sandbox2/solver/bin/starexec_run_hrs /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE 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: if(true(),X,Y) -> X 2: if(false(),U,V) -> V 3: lt(s(W),s(P)) -> lt(W,P) 4: lt(0(),s(X1)) -> true() 5: lt(Y1,0()) -> false() 6: eq(U1,U1) -> true() 7: eq(s(V1),0()) -> false() 8: eq(0(),s(W1)) -> false() 9: merge(P1,nil()) -> P1 10: merge(nil(),X2) -> X2 11: merge(cons(Y2,U2),cons(V2,W2)) -> if(lt(Y2,V2),cons(Y2,merge(U2,cons(V2,W2))),if(eq(Y2,V2),cons(Y2,merge(U2,W2)),cons(V2,merge(cons(Y2,U2),W2)))) 12: mult(0(),V3) -> 0() 13: mult(s(W3),P3) -> plus(P3,mult(W3,P3)) 14: plus(0(),X4) -> 0() 15: plus(s(Y4),U4) -> s(plus(Y4,U4)) 16: _(X1,X2) -> X1 17: _(X1,X2) -> X2 Number of strict rules: 17 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #mult(s(W3),P3) -> #plus(P3,mult(W3,P3)) #2: #mult(s(W3),P3) -> #mult(W3,P3) #3: #merge(cons(Y2,U2),cons(V2,W2)) -> #if(lt(Y2,V2),cons(Y2,merge(U2,cons(V2,W2))),if(eq(Y2,V2),cons(Y2,merge(U2,W2)),cons(V2,merge(cons(Y2,U2),W2)))) #4: #merge(cons(Y2,U2),cons(V2,W2)) -> #lt(Y2,V2) #5: #merge(cons(Y2,U2),cons(V2,W2)) -> #merge(U2,cons(V2,W2)) #6: #merge(cons(Y2,U2),cons(V2,W2)) -> #if(eq(Y2,V2),cons(Y2,merge(U2,W2)),cons(V2,merge(cons(Y2,U2),W2))) #7: #merge(cons(Y2,U2),cons(V2,W2)) -> #eq(Y2,V2) #8: #merge(cons(Y2,U2),cons(V2,W2)) -> #merge(U2,W2) #9: #merge(cons(Y2,U2),cons(V2,W2)) -> #merge(cons(Y2,U2),W2) #10: #lt(s(W),s(P)) -> #lt(W,P) #11: #plus(s(Y4),U4) -> #plus(Y4,U4) Number of SCCs: 4, DPs: 6 SCC { #2 } POLO(Sum)... succeeded. merge w: 0 s w: x1 + 1 #lt w: 0 #plus w: 0 eq w: 0 false w: 0 #merge w: 0 _ w: 0 true w: 0 #eq w: 0 mult w: 0 if w: 0 0 w: 0 nil w: 0 #_ w: 0 plus w: 0 cons w: 0 #if w: 0 lt w: 0 #mult w: x1 USABLE RULES: { } Removed DPs: #2 Number of SCCs: 3, DPs: 5 SCC { #11 } POLO(Sum)... succeeded. merge w: 0 s w: x1 + 1 #lt w: 0 #plus w: x1 eq w: 0 false w: 0 #merge w: 0 _ w: 0 true w: 0 #eq w: 0 mult w: 0 if w: 0 0 w: 0 nil w: 0 #_ w: 0 plus w: 0 cons w: 0 #if w: 0 lt w: 0 #mult w: 0 USABLE RULES: { } Removed DPs: #11 Number of SCCs: 2, DPs: 4 SCC { #10 } POLO(Sum)... succeeded. merge w: 0 s w: x1 + 1 #lt w: x2 #plus w: 0 eq w: 0 false w: 0 #merge w: 0 _ w: 0 true w: 0 #eq w: 0 mult w: 0 if w: 0 0 w: 0 nil w: 0 #_ w: 0 plus w: 0 cons w: 0 #if w: 0 lt w: 0 #mult w: 0 USABLE RULES: { } Removed DPs: #10 Number of SCCs: 1, DPs: 3 SCC { #5 #8 #9 } POLO(Sum)... succeeded. merge w: 0 s w: 1 #lt w: 0 #plus w: 0 eq w: 0 false w: 0 #merge w: x2 _ w: 0 true w: 0 #eq w: 0 mult w: 0 if w: 0 0 w: 0 nil w: 0 #_ w: 0 plus w: 0 cons w: x2 + 1 #if w: 0 lt w: 0 #mult w: 0 USABLE RULES: { } Removed DPs: #8 #9 Number of SCCs: 1, DPs: 1 SCC { #5 } POLO(Sum)... succeeded. merge w: 0 s w: 1 #lt w: 0 #plus w: 0 eq w: 0 false w: 0 #merge w: x1 _ w: 0 true w: 0 #eq w: 0 mult w: 0 if w: 0 0 w: 0 nil w: 0 #_ w: 0 plus w: 0 cons w: x2 + 1 #if w: 0 lt w: 0 #mult w: 0 USABLE RULES: { } Removed DPs: #5 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: if(true(),X,Y) -> X 2: if(false(),U,V) -> V 3: lt(s(W),s(P)) -> lt(W,P) 4: lt(0(),s(X1)) -> true() 5: lt(Y1,0()) -> false() 6: eq(U1,U1) -> true() 7: eq(s(V1),0()) -> false() 8: eq(0(),s(W1)) -> false() 9: merge(P1,nil()) -> P1 10: merge(nil(),X2) -> X2 11: merge(cons(Y2,U2),cons(V2,W2)) -> if(lt(Y2,V2),cons(Y2,merge(U2,cons(V2,W2))),if(eq(Y2,V2),cons(Y2,merge(U2,W2)),cons(V2,merge(cons(Y2,U2),W2)))) 12: mult(0(),V3) -> 0() 13: mult(s(W3),P3) -> plus(P3,mult(W3,P3)) 14: plus(0(),X4) -> 0() 15: plus(s(Y4),U4) -> s(plus(Y4,U4)) 16: _(X1,X2) -> X1 17: _(X1,X2) -> X2 Number of strict rules: 17 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #mult(s(W3),P3) -> #plus(P3,mult(W3,P3)) #2: #mult(s(W3),P3) -> #mult(W3,P3) #3: #merge(cons(Y2,U2),cons(V2,W2)) -> #if(lt(Y2,V2),cons(Y2,merge(U2,cons(V2,W2))),if(eq(Y2,V2),cons(Y2,merge(U2,W2)),cons(V2,merge(cons(Y2,U2),W2)))) #4: #merge(cons(Y2,U2),cons(V2,W2)) -> #lt(Y2,V2) #5: #merge(cons(Y2,U2),cons(V2,W2)) -> #merge(U2,cons(V2,W2)) #6: #merge(cons(Y2,U2),cons(V2,W2)) -> #if(eq(Y2,V2),cons(Y2,merge(U2,W2)),cons(V2,merge(cons(Y2,U2),W2))) #7: #merge(cons(Y2,U2),cons(V2,W2)) -> #eq(Y2,V2) #8: #merge(cons(Y2,U2),cons(V2,W2)) -> #merge(U2,W2) #9: #merge(cons(Y2,U2),cons(V2,W2)) -> #merge(cons(Y2,U2),W2) #10: #lt(s(W),s(P)) -> #lt(W,P) #11: #plus(s(Y4),U4) -> #plus(Y4,U4) Number of SCCs: 4, DPs: 6 SCC { #2 } POLO(Sum)... succeeded. merge w: 0 s w: x1 + 1 #lt w: 0 #plus w: 0 eq w: 0 false w: 0 #merge w: 0 _ w: 0 true w: 0 #eq w: 0 mult w: 0 if w: 0 0 w: 0 nil w: 0 #_ w: 0 plus w: 0 cons w: 0 #if w: 0 lt w: 0 #mult w: x1 USABLE RULES: { } Removed DPs: #2 Number of SCCs: 3, DPs: 5 SCC { #11 } POLO(Sum)... succeeded. merge w: 0 s w: x1 + 1 #lt w: 0 #plus w: x1 eq w: 0 false w: 0 #merge w: 0 _ w: 0 true w: 0 #eq w: 0 mult w: 0 if w: 0 0 w: 0 nil w: 0 #_ w: 0 plus w: 0 cons w: 0 #if w: 0 lt w: 0 #mult w: 0 USABLE RULES: { } Removed DPs: #11 Number of SCCs: 2, DPs: 4 SCC { #10 } POLO(Sum)... succeeded. merge w: 0 s w: x1 + 1 #lt w: x2 #plus w: 0 eq w: 0 false w: 0 #merge w: 0 _ w: 0 true w: 0 #eq w: 0 mult w: 0 if w: 0 0 w: 0 nil w: 0 #_ w: 0 plus w: 0 cons w: 0 #if w: 0 lt w: 0 #mult w: 0 USABLE RULES: { } Removed DPs: #10 Number of SCCs: 1, DPs: 3 SCC { #5 #8 #9 } POLO(Sum)... succeeded. merge w: 0 s w: 1 #lt w: 0 #plus w: 0 eq w: 0 false w: 0 #merge w: x2 _ w: 0 true w: 0 #eq w: 0 mult w: 0 if w: 0 0 w: 0 nil w: 0 #_ w: 0 plus w: 0 cons w: x2 + 1 #if w: 0 lt w: 0 #mult w: 0 USABLE RULES: { } Removed DPs: #8 #9 Number of SCCs: 1, DPs: 1 SCC { #5 } POLO(Sum)... succeeded. merge w: 0 s w: 1 #lt w: 0 #plus w: 0 eq w: 0 false w: 0 #merge w: x1 _ w: 0 true w: 0 #eq w: 0 mult w: 0 if w: 0 0 w: 0 nil w: 0 #_ w: 0 plus w: 0 cons w: x2 + 1 #if w: 0 lt w: 0 #mult w: 0 USABLE RULES: { } Removed DPs: #5 Number of SCCs: 0, DPs: 0 >>YES ******** Signature ******** hamming : c cons : (b,c) -> c s : b -> b 0 : b merge : (c,c) -> c list1 : c list2 : c list3 : c map : ((b -> b),c) -> c nil : c mult : (b,b) -> b ******** Computation rules ******** (21) hamming => cons(s(0),merge(list1,merge(list2,list3))) (12) map(J2,nil) => nil (13) map(F3,cons(Y3,U3)) => cons(F3[Y3],map(F3,U3)) (18) list1 => map(mult(s(s(0))),hamming) (19) list2 => map(mult(s(s(s(0)))),hamming) (20) list3 => map(mult(s(s(s(s(s(0)))))),hamming) ******** 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: hamming, list3 Checking (1) if(true,X,Y) => X (meta X)[is acc in true,X,Y] [is positive in true] [is acc in X] >>True Checking (2) if(false,U,V) => V (meta V)[is acc in false,U,V] [is positive in false] [is acc in V] >>True Checking (3) lt(s(W),s(P)) => lt(W,P) (fun lt=lt) subterm comparison of args w. LR LR (meta W)[is acc in s(W),s(P)] [is positive in s(W)] [is acc in W] (meta P)[is acc in s(W),s(P)] [is positive in s(W)] [is positive in s(P)] [is acc in P] >>True Checking (4) lt(0,s(X1)) => true (fun lt>true) >>True Checking (5) lt(Y1,0) => false (fun lt>false) >>True Checking (6) eq(U1,U1) => true (fun eq>true) >>True Checking (7) eq(s(V1),0) => false (fun eq>false) >>True Checking (8) eq(0,s(W1)) => false (fun eq>false) >>True Checking (9) merge(P1,nil) => P1 (meta P1)[is acc in P1,nil] [is acc in P1] >>True Checking (10) merge(nil,X2) => X2 (meta X2)[is acc in nil,X2] [is positive in nil] [is acc in X2] >>True Checking (11) merge(cons(Y2,U2),cons(V2,W2)) => if(lt(Y2,V2),cons(Y2,merge(U2,cons(V2,W2))),if(eq(Y2,V2),cons(Y2,merge(U2,W2)),cons(V2,merge(cons(Y2,U2),W2)))) (fun merge>if) (fun merge>lt) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (fun merge>cons) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (fun merge=merge) subterm comparison of args w. LR LR (meta U2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in U2] (fun merge>cons) (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (meta W2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in W2] (fun merge>if) (fun merge>eq) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (fun merge>cons) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (fun merge=merge) subterm comparison of args w. LR LR (meta U2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in U2] (meta W2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in W2] (fun merge>cons) (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (fun merge=merge) subterm comparison of args w. LR LR (fun merge>cons) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (meta U2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in U2] (meta W2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in W2] >>True Checking (12) map(J2,nil) => nil (fun map>nil) >>True Checking (13) map(F3,cons(Y3,U3)) => cons(F3[Y3],map(F3,U3)) (fun map>cons) (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] (fun map=map) subterm comparison of args w. LR LR (meta F3)[is acc in F3,cons(Y3,U3)] [is acc in F3] (meta U3)[is acc in F3,cons(Y3,U3)] [is positive in cons(Y3,U3)] [is acc in U3] >>True Checking (14) mult(0,V3) => 0 (fun mult>0) >>True Checking (15) mult(s(W3),P3) => P3 + mult(W3,P3) (fun mult>plus) (meta P3)[is acc in s(W3),P3] [is positive in s(W3)] [is acc in P3] (fun mult=mult) subterm comparison of args w. LR LR (meta W3)[is acc in s(W3),P3] [is positive in s(W3)] [is acc in W3] (meta P3)[is acc in s(W3),P3] [is positive in s(W3)] [is acc in P3] >>True Checking (16) 0 + X4 => 0 (fun plus>0) >>True Checking (17) s(Y4) + U4 => s(Y4 + U4) (fun plus>s) (fun plus=plus) subterm comparison of args w. LR LR (meta Y4)[is acc in s(Y4),U4] [is positive in s(Y4)] [is acc in Y4] (meta U4)[is acc in s(Y4),U4] [is positive in s(Y4)] [is acc in U4] >>True Checking (18) list1 => map(mult(s(s(0))),hamming) (fun list1>map) (fun list1>mult) (fun list1>s) (fun list1>s) (fun list1>0) (fun list1>hamming) >>True Checking (19) list2 => map(mult(s(s(s(0)))),hamming) (fun list2>map) (fun list2>mult) (fun list2>s) (fun list2>s) (fun list2>s) (fun list2>0) (fun list2>hamming) >>True Checking (20) list3 => map(mult(s(s(s(s(s(0)))))),hamming) (fun list3>map) (fun list3>mult) (fun list3>s) (fun list3>s) (fun list3>s) (fun list3>s) (fun list3>s) (fun list3>0) (fun list3=hamming) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) if(true,X,Y) => X (meta X)[is acc in true,X,Y] [is positive in true] [is acc in X] >>True Checking (2) if(false,U,V) => V (meta V)[is acc in false,U,V] [is positive in false] [is acc in V] >>True Checking (3) lt(s(W),s(P)) => lt(W,P) (fun lt=lt) subterm comparison of args w. RL RL (meta W)[is acc in s(W),s(P)] [is positive in s(W)] [is acc in W] (meta P)[is acc in s(W),s(P)] [is positive in s(W)] [is positive in s(P)] [is acc in P] >>True Checking (4) lt(0,s(X1)) => true (fun lt>true) >>True Checking (5) lt(Y1,0) => false (fun lt>false) >>True Checking (6) eq(U1,U1) => true (fun eq>true) >>True Checking (7) eq(s(V1),0) => false (fun eq>false) >>True Checking (8) eq(0,s(W1)) => false (fun eq>false) >>True Checking (9) merge(P1,nil) => P1 (meta P1)[is acc in P1,nil] [is acc in P1] >>True Checking (10) merge(nil,X2) => X2 (meta X2)[is acc in nil,X2] [is positive in nil] [is acc in X2] >>True Checking (11) merge(cons(Y2,U2),cons(V2,W2)) => if(lt(Y2,V2),cons(Y2,merge(U2,cons(V2,W2))),if(eq(Y2,V2),cons(Y2,merge(U2,W2)),cons(V2,merge(cons(Y2,U2),W2)))) (fun merge>if) (fun merge>lt) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (fun merge>cons) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (fun merge=merge) subterm comparison of args w. RL RL (meta U2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in U2] (fun merge>cons) (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (meta W2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in W2] (fun merge>if) (fun merge>eq) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (fun merge>cons) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (fun merge=merge) subterm comparison of args w. RL RL (meta U2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in U2] (meta W2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in W2] (fun merge>cons) (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (fun merge=merge) subterm comparison of args w. RL RL (fun merge>cons) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (meta U2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in U2] (meta W2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in W2] >>True Checking (12) map(J2,nil) => nil (fun map>nil) >>True Checking (13) map(F3,cons(Y3,U3)) => cons(F3[Y3],map(F3,U3)) (fun map>cons) (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] (fun map=map) subterm comparison of args w. RL RL (meta F3)[is acc in F3,cons(Y3,U3)] [is acc in F3] (meta U3)[is acc in F3,cons(Y3,U3)] [is positive in cons(Y3,U3)] [is acc in U3] >>True Checking (14) mult(0,V3) => 0 (fun mult>0) >>True Checking (15) mult(s(W3),P3) => P3 + mult(W3,P3) (fun mult>plus) (meta P3)[is acc in s(W3),P3] [is positive in s(W3)] [is acc in P3] (fun mult=mult) subterm comparison of args w. RL RL (meta W3)[is acc in s(W3),P3] [is positive in s(W3)] [is acc in W3] (meta P3)[is acc in s(W3),P3] [is positive in s(W3)] [is acc in P3] >>True Checking (16) 0 + X4 => 0 (fun plus>0) >>True Checking (17) s(Y4) + U4 => s(Y4 + U4) (fun plus>s) (fun plus=plus) subterm comparison of args w. RL RL (meta Y4)[is acc in s(Y4),U4] [is positive in s(Y4)] [is acc in Y4] (meta U4)[is acc in s(Y4),U4] [is positive in s(Y4)] [is acc in U4] >>True Checking (18) list1 => map(mult(s(s(0))),hamming) (fun list1>map) (fun list1>mult) (fun list1>s) (fun list1>s) (fun list1>0) (fun list1>hamming) >>True Checking (19) list2 => map(mult(s(s(s(0)))),hamming) (fun list2>map) (fun list2>mult) (fun list2>s) (fun list2>s) (fun list2>s) (fun list2>0) (fun list2>hamming) >>True Checking (20) list3 => map(mult(s(s(s(s(s(0)))))),hamming) (fun list3>map) (fun list3>mult) (fun list3>s) (fun list3>s) (fun list3>s) (fun list3>s) (fun list3>s) (fun list3>0) (fun list3=hamming) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) if(true,X,Y) => X (meta X)[is acc in true,X,Y] [is positive in true] [is acc in X] >>True Checking (2) if(false,U,V) => V (meta V)[is acc in false,U,V] [is positive in false] [is acc in V] >>True Checking (3) lt(s(W),s(P)) => lt(W,P) (fun lt=lt) subterm comparison of args w. Mul Mul (meta W)[is acc in s(W),s(P)] [is positive in s(W)] [is acc in W] (meta P)[is acc in s(W),s(P)] [is positive in s(W)] [is positive in s(P)] [is acc in P] >>True Checking (4) lt(0,s(X1)) => true (fun lt>true) >>True Checking (5) lt(Y1,0) => false (fun lt>false) >>True Checking (6) eq(U1,U1) => true (fun eq>true) >>True Checking (7) eq(s(V1),0) => false (fun eq>false) >>True Checking (8) eq(0,s(W1)) => false (fun eq>false) >>True Checking (9) merge(P1,nil) => P1 (meta P1)[is acc in P1,nil] [is acc in P1] >>True Checking (10) merge(nil,X2) => X2 (meta X2)[is acc in nil,X2] [is positive in nil] [is acc in X2] >>True Checking (11) merge(cons(Y2,U2),cons(V2,W2)) => if(lt(Y2,V2),cons(Y2,merge(U2,cons(V2,W2))),if(eq(Y2,V2),cons(Y2,merge(U2,W2)),cons(V2,merge(cons(Y2,U2),W2)))) (fun merge>if) (fun merge>lt) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (fun merge>cons) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (fun merge=merge) subterm comparison of args w. Mul Mul (meta U2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in U2] (fun merge>cons) (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (meta W2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in W2] (fun merge>if) (fun merge>eq) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (fun merge>cons) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (fun merge=merge) subterm comparison of args w. Mul Mul (meta U2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in U2] (meta W2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in W2] (fun merge>cons) (meta V2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in V2] (fun merge=merge) subterm comparison of args w. Mul Mul (fun merge>cons) (meta Y2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in Y2] (meta U2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is acc in U2] (meta W2)[is acc in cons(Y2,U2),cons(V2,W2)] [is positive in cons(Y2,U2)] [is positive in cons(V2,W2)] [is acc in W2] >>True Checking (12) map(J2,nil) => nil (fun map>nil) >>True Checking (13) map(F3,cons(Y3,U3)) => cons(F3[Y3],map(F3,U3)) (fun map>cons) (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] (fun map=map) subterm comparison of args w. Mul Mul (meta F3)[is acc in F3,cons(Y3,U3)] [is acc in F3] (meta U3)[is acc in F3,cons(Y3,U3)] [is positive in cons(Y3,U3)] [is acc in U3] >>True Checking (14) mult(0,V3) => 0 (fun mult>0) >>True Checking (15) mult(s(W3),P3) => P3 + mult(W3,P3) (fun mult>plus) (meta P3)[is acc in s(W3),P3] [is positive in s(W3)] [is acc in P3] (fun mult=mult) subterm comparison of args w. Mul Mul (meta W3)[is acc in s(W3),P3] [is positive in s(W3)] [is acc in W3] (meta P3)[is acc in s(W3),P3] [is positive in s(W3)] [is acc in P3] >>True Checking (16) 0 + X4 => 0 (fun plus>0) >>True Checking (17) s(Y4) + U4 => s(Y4 + U4) (fun plus>s) (fun plus=plus) subterm comparison of args w. Mul Mul (meta Y4)[is acc in s(Y4),U4] [is positive in s(Y4)] [is acc in Y4] (meta U4)[is acc in s(Y4),U4] [is positive in s(Y4)] [is acc in U4] >>True Checking (18) list1 => map(mult(s(s(0))),hamming) (fun list1>map) (fun list1>mult) (fun list1>s) (fun list1>s) (fun list1>0) (fun list1>hamming) >>True Checking (19) list2 => map(mult(s(s(s(0)))),hamming) (fun list2>map) (fun list2>mult) (fun list2>s) (fun list2>s) (fun list2>s) (fun list2>0) (fun list2>hamming) >>True Checking (20) list3 => map(mult(s(s(s(s(s(0)))))),hamming) (fun list3>map) (fun list3>mult) (fun list3>s) (fun list3>s) (fun list3>s) (fun list3>s) (fun list3>s) (fun list3>0) (fun list3=hamming) subterm comparison of args w. Mul Mul >>False Found constructors: cons, s, 0, merge, nil, mult Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>Regared as equal: list3, hamming Checking (21) hamming => cons(s(0),merge(list1,merge(list2,list3))) (fun hamming>cons) (fun hamming>s) (fun hamming>0) (fun hamming>merge) (fun hamming>list1) (fun hamming>merge) (fun hamming>list2) (fun hamming=list3) subterm comparison of args w. LR LR >>False Try again using status RL Checking (21) hamming => cons(s(0),merge(list1,merge(list2,list3))) (fun hamming>cons) (fun hamming>s) (fun hamming>0) (fun hamming>merge) (fun hamming>list1) (fun hamming>merge) (fun hamming>list2) (fun hamming=list3) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (21) hamming => cons(s(0),merge(list1,merge(list2,list3))) (fun hamming>cons) (fun hamming>s) (fun hamming>0) (fun hamming>merge) (fun hamming>list1) (fun hamming>merge) (fun hamming>list2) (fun hamming=list3) subterm comparison of args w. Mul Mul >>False #No idea.. ******** Signature ******** 0 : b cons : (b,c) -> c eq : (b,b) -> a false : a hamming : c if : (a,c,c) -> c list1 : c list2 : c list3 : c lt : (b,b) -> a map : ((b -> b),c) -> c merge : (c,c) -> c mult : (b,b) -> b nil : c plus : (b,b) -> b s : b -> b true : a ******** Computation Rules ******** (1) if(true,X,Y) => X (2) if(false,U,V) => V (3) lt(s(W),s(P)) => lt(W,P) (4) lt(0,s(X1)) => true (5) lt(Y1,0) => false (6) eq(U1,U1) => true (7) eq(s(V1),0) => false (8) eq(0,s(W1)) => false (9) merge(P1,nil) => P1 (10) merge(nil,X2) => X2 (11) merge(cons(Y2,U2),cons(V2,W2)) => if(lt(Y2,V2),cons(Y2,merge(U2,cons(V2,W2))),if(eq(Y2,V2),cons(Y2,merge(U2,W2)),cons(V2,merge(cons(Y2,U2),W2)))) (12) map(J2,nil) => nil (13) map(F3,cons(Y3,U3)) => cons(F3[Y3],map(F3,U3)) (14) mult(0,V3) => 0 (15) mult(s(W3),P3) => P3 + mult(W3,P3) (16) 0 + X4 => 0 (17) s(Y4) + U4 => s(Y4 + U4) (18) list1 => map(mult(s(s(0))),hamming) (19) list2 => map(mult(s(s(s(0)))),hamming) (20) list3 => map(mult(s(s(s(s(s(0)))))),hamming) (21) hamming => cons(s(0),merge(list1,merge(list2,list3))) MAYBE