/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: if(true(),X,Y) -> X 2: if(false(),U,V) -> V 3: sub(W,0()) -> W 4: sub(s(P),s(X1)) -> sub(P,X1) 5: gtr(0(),Y1) -> false() 6: gtr(s(U1),0()) -> true() 7: gtr(s(V1),s(W1)) -> gtr(V1,W1) 8: d(P1,0()) -> true() 9: d(s(X2),s(Y2)) -> if(gtr(X2,Y2),false(),d(s(X2),sub(Y2,X2))) 10: len(nil()) -> 0() 11: len(cons(U2,V2)) -> s(len(V2)) 12: _(X1,X2) -> X1 13: _(X1,X2) -> X2 Number of strict rules: 13 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #d(s(X2),s(Y2)) -> #if(gtr(X2,Y2),false(),d(s(X2),sub(Y2,X2))) #2: #d(s(X2),s(Y2)) -> #gtr(X2,Y2) #3: #d(s(X2),s(Y2)) -> #d(s(X2),sub(Y2,X2)) #4: #d(s(X2),s(Y2)) -> #sub(Y2,X2) #5: #len(cons(U2,V2)) -> #len(V2) #6: #gtr(s(V1),s(W1)) -> #gtr(V1,W1) #7: #sub(s(P),s(X1)) -> #sub(P,X1) Number of SCCs: 4, DPs: 4 SCC { #5 } POLO(Sum)... succeeded. d w: 0 #len w: x1 s w: 0 #gtr w: 0 false w: 0 gtr w: 0 _ w: 0 sub w: 0 true w: 0 #sub w: 0 if w: 0 0 w: 0 nil w: 0 #d w: 0 #_ w: 0 cons w: x2 + 1 #if w: 0 len w: 0 USABLE RULES: { } Removed DPs: #5 Number of SCCs: 3, DPs: 3 SCC { #7 } POLO(Sum)... succeeded. d w: 0 #len w: 0 s w: x1 + 1 #gtr w: 0 false w: 0 gtr w: 0 _ w: 0 sub w: 0 true w: 0 #sub w: x1 if w: 0 0 w: 0 nil w: 0 #d w: 0 #_ w: 0 cons w: 1 #if w: 0 len w: 0 USABLE RULES: { } Removed DPs: #7 Number of SCCs: 2, DPs: 2 SCC { #6 } POLO(Sum)... succeeded. d w: 0 #len w: 0 s w: x1 + 1 #gtr w: x2 false w: 0 gtr w: 0 _ w: 0 sub w: 0 true w: 0 #sub w: 0 if w: 0 0 w: 0 nil w: 0 #d w: 0 #_ w: 0 cons w: 1 #if w: 0 len w: 0 USABLE RULES: { } Removed DPs: #6 Number of SCCs: 1, DPs: 1 SCC { #3 } POLO(Sum)... succeeded. d w: 0 #len w: 0 s w: x1 + 2 #gtr w: 0 false w: 0 gtr w: 0 _ w: 0 sub w: x1 + 1 true w: 0 #sub w: 0 if w: 0 0 w: 1 nil w: 0 #d w: x2 #_ w: 0 cons w: 1 #if w: 0 len w: 0 USABLE RULES: { 3 4 } Removed DPs: #3 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: if(true(),X,Y) -> X 2: if(false(),U,V) -> V 3: sub(W,0()) -> W 4: sub(s(P),s(X1)) -> sub(P,X1) 5: gtr(0(),Y1) -> false() 6: gtr(s(U1),0()) -> true() 7: gtr(s(V1),s(W1)) -> gtr(V1,W1) 8: d(P1,0()) -> true() 9: d(s(X2),s(Y2)) -> if(gtr(X2,Y2),false(),d(s(X2),sub(Y2,X2))) 10: len(nil()) -> 0() 11: len(cons(U2,V2)) -> s(len(V2)) 12: _(X1,X2) -> X1 13: _(X1,X2) -> X2 Number of strict rules: 13 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #d(s(X2),s(Y2)) -> #if(gtr(X2,Y2),false(),d(s(X2),sub(Y2,X2))) #2: #d(s(X2),s(Y2)) -> #gtr(X2,Y2) #3: #d(s(X2),s(Y2)) -> #d(s(X2),sub(Y2,X2)) #4: #d(s(X2),s(Y2)) -> #sub(Y2,X2) #5: #len(cons(U2,V2)) -> #len(V2) #6: #gtr(s(V1),s(W1)) -> #gtr(V1,W1) #7: #sub(s(P),s(X1)) -> #sub(P,X1) Number of SCCs: 4, DPs: 4 SCC { #5 } POLO(Sum)... succeeded. d w: 0 #len w: x1 s w: 0 #gtr w: 0 false w: 0 gtr w: 0 _ w: 0 sub w: 0 true w: 0 #sub w: 0 if w: 0 0 w: 0 nil w: 0 #d w: 0 #_ w: 0 cons w: x2 + 1 #if w: 0 len w: 0 USABLE RULES: { } Removed DPs: #5 Number of SCCs: 3, DPs: 3 SCC { #7 } POLO(Sum)... succeeded. d w: 0 #len w: 0 s w: x1 + 1 #gtr w: 0 false w: 0 gtr w: 0 _ w: 0 sub w: 0 true w: 0 #sub w: x1 if w: 0 0 w: 0 nil w: 0 #d w: 0 #_ w: 0 cons w: 1 #if w: 0 len w: 0 USABLE RULES: { } Removed DPs: #7 Number of SCCs: 2, DPs: 2 SCC { #6 } POLO(Sum)... succeeded. d w: 0 #len w: 0 s w: x1 + 1 #gtr w: x2 false w: 0 gtr w: 0 _ w: 0 sub w: 0 true w: 0 #sub w: 0 if w: 0 0 w: 0 nil w: 0 #d w: 0 #_ w: 0 cons w: 1 #if w: 0 len w: 0 USABLE RULES: { } Removed DPs: #6 Number of SCCs: 1, DPs: 1 SCC { #3 } POLO(Sum)... succeeded. d w: 0 #len w: 0 s w: x1 + 2 #gtr w: 0 false w: 0 gtr w: 0 _ w: 0 sub w: x1 + 1 true w: 0 #sub w: 0 if w: 0 0 w: 1 nil w: 0 #d w: x2 #_ w: 0 cons w: 1 #if w: 0 len w: 0 USABLE RULES: { 3 4 } Removed DPs: #3 Number of SCCs: 0, DPs: 0 >>YES ******** Signature ******** filter : ((b -> c),c) -> c nil : c cons : (b,c) -> c if : (c,c,c) -> c ******** Computation rules ******** (12) filter(I2,nil) => nil (13) filter(J2,cons(X3,Y3)) => if(J2[X3],cons(X3,filter(J2,Y3)),filter(J2,Y3)) ******** General Schema criterion ******** Found constructors: 0, cons, false, nil, s, true Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK 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) sub(W,0) => W (meta W)[is acc in W,0] [is acc in W] >>True Checking (4) sub(s(P),s(X1)) => sub(P,X1) (fun sub=sub) subterm comparison of args w. LR LR (meta P)[is acc in s(P),s(X1)] [is positive in s(P)] [is acc in P] (meta X1)[is acc in s(P),s(X1)] [is positive in s(P)] [is positive in s(X1)] [is acc in X1] >>True Checking (5) gtr(0,Y1) => false (fun gtr>false) >>True Checking (6) gtr(s(U1),0) => true (fun gtr>true) >>True Checking (7) gtr(s(V1),s(W1)) => gtr(V1,W1) (fun gtr=gtr) subterm comparison of args w. LR LR (meta V1)[is acc in s(V1),s(W1)] [is positive in s(V1)] [is acc in V1] (meta W1)[is acc in s(V1),s(W1)] [is positive in s(V1)] [is positive in s(W1)] [is acc in W1] >>True Checking (8) d(P1,0) => true (fun d>true) >>True Checking (9) d(s(X2),s(Y2)) => if(gtr(X2,Y2),false,d(s(X2),sub(Y2,X2))) (fun d>if) (fun d>gtr) (meta X2)[is acc in s(X2),s(Y2)] [is positive in s(X2)] [is acc in X2] (meta Y2)[is acc in s(X2),s(Y2)] [is positive in s(X2)] [is positive in s(Y2)] [is acc in Y2] (fun d>false) (fun d=d) 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) sub(W,0) => W (meta W)[is acc in W,0] [is acc in W] >>True Checking (4) sub(s(P),s(X1)) => sub(P,X1) (fun sub=sub) subterm comparison of args w. RL RL (meta P)[is acc in s(P),s(X1)] [is positive in s(P)] [is acc in P] (meta X1)[is acc in s(P),s(X1)] [is positive in s(P)] [is positive in s(X1)] [is acc in X1] >>True Checking (5) gtr(0,Y1) => false (fun gtr>false) >>True Checking (6) gtr(s(U1),0) => true (fun gtr>true) >>True Checking (7) gtr(s(V1),s(W1)) => gtr(V1,W1) (fun gtr=gtr) subterm comparison of args w. RL RL (meta V1)[is acc in s(V1),s(W1)] [is positive in s(V1)] [is acc in V1] (meta W1)[is acc in s(V1),s(W1)] [is positive in s(V1)] [is positive in s(W1)] [is acc in W1] >>True Checking (8) d(P1,0) => true (fun d>true) >>True Checking (9) d(s(X2),s(Y2)) => if(gtr(X2,Y2),false,d(s(X2),sub(Y2,X2))) (fun d>if) (fun d>gtr) (meta X2)[is acc in s(X2),s(Y2)] [is positive in s(X2)] [is acc in X2] (meta Y2)[is acc in s(X2),s(Y2)] [is positive in s(X2)] [is positive in s(Y2)] [is acc in Y2] (fun d>false) (fun d=d) 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) sub(W,0) => W (meta W)[is acc in W,0] [is acc in W] >>True Checking (4) sub(s(P),s(X1)) => sub(P,X1) (fun sub=sub) subterm comparison of args w. Mul Mul (meta P)[is acc in s(P),s(X1)] [is positive in s(P)] [is acc in P] (meta X1)[is acc in s(P),s(X1)] [is positive in s(P)] [is positive in s(X1)] [is acc in X1] >>True Checking (5) gtr(0,Y1) => false (fun gtr>false) >>True Checking (6) gtr(s(U1),0) => true (fun gtr>true) >>True Checking (7) gtr(s(V1),s(W1)) => gtr(V1,W1) (fun gtr=gtr) subterm comparison of args w. Mul Mul (meta V1)[is acc in s(V1),s(W1)] [is positive in s(V1)] [is acc in V1] (meta W1)[is acc in s(V1),s(W1)] [is positive in s(V1)] [is positive in s(W1)] [is acc in W1] >>True Checking (8) d(P1,0) => true (fun d>true) >>True Checking (9) d(s(X2),s(Y2)) => if(gtr(X2,Y2),false,d(s(X2),sub(Y2,X2))) (fun d>if) (fun d>gtr) (meta X2)[is acc in s(X2),s(Y2)] [is positive in s(X2)] [is acc in X2] (meta Y2)[is acc in s(X2),s(Y2)] [is positive in s(X2)] [is positive in s(Y2)] [is acc in Y2] (fun d>false) (fun d=d) subterm comparison of args w. Mul Mul >>False Found constructors: nil, cons, if Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK Checking (12) filter(I2,nil) => nil (fun filter>nil) >>True Checking (13) filter(J2,cons(X3,Y3)) => if(J2[X3],cons(X3,filter(J2,Y3)),filter(J2,Y3)) (fun filter>if) (meta J2)[is acc in J2,cons(X3,Y3)] [is acc in J2] (meta X3)[is acc in J2,cons(X3,Y3)] [is positive in cons(X3,Y3)] [is acc in X3] (fun filter>cons) (meta X3)[is acc in J2,cons(X3,Y3)] [is positive in cons(X3,Y3)] [is acc in X3] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta J2)[is acc in J2,cons(X3,Y3)] [is acc in J2] (meta Y3)[is acc in J2,cons(X3,Y3)] [is positive in cons(X3,Y3)] [is acc in Y3] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta J2)[is acc in J2,cons(X3,Y3)] [is acc in J2] (meta Y3)[is acc in J2,cons(X3,Y3)] [is positive in cons(X3,Y3)] [is acc in Y3] >>True #SN! ******** Signature ******** 0 : a cons : (b,c) -> c d : (a,a) -> c false : c filter : ((b -> c),c) -> c gtr : (a,a) -> c if : (c,c,c) -> c len : c -> a nil : c s : a -> a sub : (a,a) -> a true : c ******** Computation Rules ******** (1) if(true,X,Y) => X (2) if(false,U,V) => V (3) sub(W,0) => W (4) sub(s(P),s(X1)) => sub(P,X1) (5) gtr(0,Y1) => false (6) gtr(s(U1),0) => true (7) gtr(s(V1),s(W1)) => gtr(V1,W1) (8) d(P1,0) => true (9) d(s(X2),s(Y2)) => if(gtr(X2,Y2),false,d(s(X2),sub(Y2,X2))) (10) len(nil) => 0 (11) len(cons(U2,V2)) => s(len(V2)) (12) filter(I2,nil) => nil (13) filter(J2,cons(X3,Y3)) => if(J2[X3],cons(X3,filter(J2,Y3)),filter(J2,Y3)) YES